ERRATA LIST for Set Theory by Abhijit Dasgupta

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Instruction manuals

Published:

Views: 0 | Pages: 4

Share
Related documents
Description
ERRATA LIST for Set Theory by Abhijit Dasgupta
Tags

mathematics

Transcript
ERRATA LIST FOR SET THEORY LAST UPDATED: 23 FEBRUARY 2015 The following is the list of errata for the book  Set Theory: With an Introduction to Real Point Sets,  by Abhijit Dasgupta, Birkh¨auser/Springer, 2014 (ISBN 978-1-4614-8853-8, hardcover). ã  p. ix : Add the following sentence at the end of the top paragraph: “In par-ticular,  the postscript chapters fall outside the main development followed in the book. ã  p. 9 : Line before Problem 16: “ xRu  and  uRy ” should be “ xRu  and  uSy ”. ã  pp. 42–43: Error in the proof of Theorem 146: The author wishes to thank Dr. Christoph Lamm for noticing this error. The rigorous deﬁnition of addition given in Section 2.10 (using primitiverecursion) is based ultimately on Theorem 146 (Basic Principle of RecursiveDeﬁnition). The proof of Theorem 146 assumes that the ordering relation <  on  N  has already been deﬁned. But the deﬁnition of ordering on  N  givenearlier (Deﬁnition 61) had presupposed addition itself, resulting in  circular reasoning. The proof of Theorem 146 can be corrected by deﬁning the set  I  n  of theﬁrst  n  natural numbers  without presupposing the ordering relation   < .  Acomplete replacement for pages 42–43 with this correction to the proof of Theorem 146 appears at the end of this errata list. ã  p. 49 : After the ﬁgure, remove the extra space (indentation) preceding thephrase “if both legs ...”. ã  p. 60 : Top line of text: Two union symbols after  { 0 }  are missing: In eachcase, “ { 0 }{ ” should become “ { 0 } ∪ { ”. ã  p. 83 : Item 2 in “ Informal discussion ”: “...called bounded if we have − a < x < a  for some real number  a ” should be changed to: “...calledbounded if there is a real number  a  such that  − a < x < a  for all  x  ∈  E  .” ã  p. 92 : Paragraph after Problem 290, second line: “congruence and similar-ity mappings” should be “congruence and similarity of geometric ﬁgures”. ã  p. 97 : Problem 313:  12 ( m + n )( m + n − 1)+ m  should be  12 ( m + n − 2)( m + n −  1) + m , and similarly, the displayed formula should become  m,n  →  ( m + n −  2)( m + n −  1)2 + m ã  p. 111 : After Theorem 350, add the following sentence: “By Theorem 350,the cardinal comparison symbols    and  ≤  become equivalent, and so wecan (and henceforth will) use them interchangeably.” 1  2 LAST UPDATED: 23 FEBRUARY 2015 ã  p. 124 : Problem 418, last clause in the casewise deﬁnition for  Φ : Insteadof   x  it should be  h ( x ). ã  p. 166 : The displayed sentence “ The Suslin Problem. Is a CCC ... ” isall in italics, but the ﬁrst three words should be upright bold, as in: “ TheSuslin Problem .  Is a CCC ... ”. ã  p. 207 : In Theorem 714 part 1, change “ but   X  ( α )   X  ( µ )  for   α < µ ” to“ but   X  ( α )  X  ( µ )  for all   α < µ ”. ã  p. 249 :  Proof (of Theorem 877, Outline) : In 5th line of the proof, “with( c,d )  ∩ E  α   =  ∅  ...” should be “with ( c,d )  ∩ E  α  =  ∅  ...”. ã  p. 323 : In Problem 1126, Hint: “ B E   :=  ∪ n ∈ E  A n  ∪ n ∈ E   A n  ...” shouldbe “ B E   :=  ∩ n ∈ E  A n  ∪ n ∈ E   A n  ...” ã  p. 347 : Deﬁnition 1185:  p   =  q   should be  x   =  y . ã  p. 420 : End of proof of Proposition 1335: “ ≥  m ∗ ( A ) + m ∗ ( B )” should be“ ≥  m ∗ ( A ) + m ∗ ( B )  − ǫ ”. ã  p. 431 : –  Change index entry “absolutism, 67” to “absolutism, 67, 70” –  Under the index entry for “axiom of”: ∗  Change subentry “choice, 13, 77, 90–94, 208–210” to “choice,13, 90–94, 208–210, 224–225” ∗  Change subentry “dependent choice (DC), 77, 101” to “depen-dent choice (DC), 101” ã  p. 432 : –  Under the index entry for “axiom of”: ∗  Change subentry “foundation, 393–395, 421” to “foundation,393–394, 421” ∗  Change subentry “replacement, 376–377, 421” to “replacement,376–377, 409, 421” –  Change index entry “Bernstein sets, 298–299, 335, 345–346, 408” to“Bernstein sets, 298–299, 335, 346, 402, 408”  42 2 The Dedekind-Peano Axioms 2.10 Recursive Deﬁnitions* Recall that we had “deﬁned” addition of natural numbers by the following  recursionequations : m +1 : =  S  ( m ) ,  and  m + S  ( n ) : =  S  ( m + n ) . But this is not an explicit deﬁnition! We took it for granted (as was done in the work of Peano) that a two-place function + (the mapping ( m , n )  →  m + n ) satisfying theabove equations exists, without giving any rigorous justiﬁcation for its existence.Similarly, multiplication of natural numbers was “deﬁned” by recursion equationswithout proper justiﬁcation.Dedekindintroduced a general method, known as  primitive recursion,  whichpro-vides such justiﬁcation. It assures the  existence and uniqueness  of functions whichare deﬁned implicitly using recursion equations having forms similar to the ones foraddition and multiplication.We will formulate and prove a general version of Dedekind’s principle of recur-sive deﬁnition, from which the existence and uniqueness for the sum and productfunctions can be immediately derived. Principles of Recursive Deﬁnition The following  Basic Principle of Recursive Deﬁnition  is perhaps the simplest yetvery useful result for deﬁning functions recursively. Theorem 146 (Basic Principle of Recursive Deﬁnition).  If Y is a set, a  ∈  Y, and h :  Y   → Y, then there is a unique f   :  N  → Y such that  f   (1)  = a ,  and f   ( S  ( n ))  =  h (  f   ( n ))  for all n  ∈  N . Informally, this says that given  a  ∈  Y   and  h :  Y   →  Y  , we can form the inﬁnite se-quence   a , h ( a ) , h ( h ( a )) ,. . .  . Proof.  The uniqueness of the function  f   can be established by an easy and routineinduction, so let us prove existence.A subset  I   of   N  will be called an  initial set   if for all  k   ∈  N , if   S  ( k  )  ∈  I   then  k   ∈  I  .By routine induction, we can establish the following: ã  { 1 }  is an initial set, and every non-empty initial set contains 1 as a member. ã  If   I   is an initial set with  k   ∈  I   then  I  ∪{ S  ( k  ) }  is also an initial set. ã  For each  n  ∈  N , there is a unique initial set  I   such that  n  ∈  I   but  S  ( n )    I  .Let  I  n  denote the unique initial set containing  n  but not  S  ( n ). It follows that  I  1 = { 1 } ,and  I  S ( n )  =  I  n  ∪{ S  ( n ) }  for all  n  ∈  N . (Informally,  I  n  =  { 1 , 2 ,. . . , n } , the set of ﬁrst  n natural numbers.) The proof will use  functions u :  I  n  → Y having domain I  n . Let us say that a function  u is partially h-recursive with domain I  n  if   u :  I  n  → Y  , u (1)  = a , and  u ( S  ( k  ))  =  h ( u ( k  )) for all  k   such that  S  ( k  )  ∈  I  n .  2.10 Recursive Deﬁnitions* 43 We ﬁrst prove by induction that for every  n  ∈  N  there is a unique partially  h -recursive  u  with domain  I  n .Basis step ( n = 1): Let  v :  { 1 } → Y   be deﬁned by setting  v (1)  = a . Then  v  is par-tially  h -recursive with domain  I  1 . Moreover, if  u , u ′ :  I  1  → Y   are partially  h -recursivefunctions with domain  I  1 , then u (1) = a = u ′ (1), so u = u ′ since 1 is the only elementin their domain  I  1  = { 1 } . So there is a unique partially  h -recursive  v  with domain  I  1 ,establishing the basis step.Induction step: Suppose that  n  ∈  N  is such that there is a unique partially  h -recursive  v  with domain  I  n  (induction hypothesis). We ﬁx this  v  for the rest of thisstep,anddeﬁne  w :  I  S ( n )  → Y   bysetting  w ( k  ) : = v ( k  ) for  k   ∈  I  n  and  w ( k  ) : = h ( v ( n ))if   k   =  S  ( n ). Then  w  is easily seen to be partially  h -recursive with domain  I  S ( n ) .Moreover, if   u , u ′ :  I  S ( n )  → Y   are partially  h -recursive with domain  I  S ( n ) , then therestrictions  u ↾  I  n and  u ′ ↾  I  n are partially  h -recursive with domain  I  n , so they must beidentical by induction hypothesis, i.e.  u ( k  )  = u ′ ( k  ) for  k   ∈  I  n . In particular,  u ( n )  = u ′ ( n ), so  u ( S  ( n )) = h ( u ( n )) = h ( u ′ ( n )) = u ′ ( S  ( n )), which gives  u = u ′ . Hence thereis a unique partially  h -recursive  w  with domain  I  S ( n ) , which ﬁnishes the inductionstep.Thus for each  n  there is a unique partially  h -recursive function with domain  I  n ;let us denote this function by  u n .Now deﬁne  f   :  N  → Y   by setting:  f   ( n ) : = u n ( n ) . First,  f   (1)  =  a  since  u 1 (1)  =  a . Next, the restriction of   u S ( n )  to  I  n  equals  u n  (byuniqueness,sincetherestrictionispartially  h -recursive),so u S ( n ) ( n ) = u n ( n ).Hence  f   ( S  ( n ))  =  u S ( n ) ( S  ( n ))  =  h ( u S ( n ) ( n ))  =  h ( u n ( n ))  =  h (  f   ( n )). Thus  f   satisﬁes therecursion equations of the theorem.  ⊓⊔ To handle functions of multiple variables, the following theorem is used. Theorem 147 (GeneralPrincipleofRecursiveDeﬁnition). Forany  g :  X   → Y and h :  X   × N × Y   → Y, there is a unique function f   :  X   × N → Y such that for all x  ∈  X and n  ∈  N : f   (  x , 1)  = g (  x )  and f   (  x , S  ( n ))  =  h (  x , n ,  f   (  x , n )) . Here  f   is being deﬁned by recursion on the second variable  n , that is,  n  is the variable of recursion  ranging over  N , while  x  is a  parameter   ranging over the set  X  .This is the most general form of recursive deﬁnition, where both the parameters (in  X  ) and the values (in  Y  ) come from arbitrary sets. Proof.  The proof is essentially the same as that of Theorem 146, since the additionalparameter does not play any signiﬁcant role in the recursion. The details are left asan exercise for the reader.  ⊓⊔ Theorem 148 (Course of Values Recursion).  Let Y be a non-empty set and Y  ∗ denote the set of all ﬁnite sequences (strings) of elements from Y. Given anyG :  Y  ∗ → Y there is a unique f   :  N  → Y such that
Recommended

12 pages

page

18 pages

70 pages

59 pages

10 pages

36 pages

12 pages

12 pages

4 pages

5 pages

4 pages

14 pages

1 page

The Re-Creation of the European City: Urban Shopping List for Secondary Cities. By Beatriz Ramo/STAR

14 pages

View more...

Entrance mats 