ERRATA LIST for Set Theory by Abhijit Dasgupta

Please download to get full document.

View again

of 4
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

Extension: PDF | Download: 0

Share
Related documents
Description
ERRATA LIST for Set Theory by Abhijit Dasgupta
Tags
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 definition of addition given in Section 2.10 (using primitiverecursion) is based ultimately on Theorem 146 (Basic Principle of RecursiveDefinition). The proof of Theorem 146 assumes that the ordering relation <  on  N  has already been defined. But the definition of ordering on  N  givenearlier (Definition 61) had presupposed addition itself, resulting in  circular reasoning. The proof of Theorem 146 can be corrected by defining the set  I  n  of thefirst  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 figure, 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 figures”. ã  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 definition for  Φ : Insteadof   x  it should be  h ( x ). ã  p. 166 : The displayed sentence “ The Suslin Problem. Is a CCC ... ” isall in italics, but the first 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 : Definition 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 Definitions* Recall that we had “defined” 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 definition! 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 justification for its existence.Similarly, multiplication of natural numbers was “defined” by recursion equationswithout proper justification.Dedekindintroduced a general method, known as  primitive recursion,  whichpro-vides such justification. It assures the  existence and uniqueness  of functions whichare defined 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 definition, from which the existence and uniqueness for the sum and productfunctions can be immediately derived. Principles of Recursive Definition The following  Basic Principle of Recursive Definition  is perhaps the simplest yetvery useful result for defining functions recursively. Theorem 146 (Basic Principle of Recursive Definition).  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 infinite 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 first  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 Definitions* 43 We first 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 defined 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 fix this  v  for the rest of thisstep,anddefine  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 finishes 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 define  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   satisfies therecursion equations of the theorem.  ⊓⊔ To handle functions of multiple variables, the following theorem is used. Theorem 147 (GeneralPrincipleofRecursiveDefinition). 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 defined 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 definition, 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 significant 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 finite sequences (strings) of elements from Y. Given anyG :  Y  ∗ → Y there is a unique f   :  N  → Y such that 
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks