Thursday, 25 April 2013

elementary set theory - Show that mathbbN is infinite



I've tried to show that N is an infinite set.



Proof. By contradiction: assume that exists a bijeciton f from N to In={1,,n1}. We know that fIn is injective and its image is a proper subset of In. From here, we can show that, by restricting the codomain of fIn to fIn(In), we obtain a bijection from a proper subset of In, that is, fIn(In), to In itself. But this is a contradiction.



Is it a correct proof?



EDIT: I'm using Peano's definition for N, where In is the set {0,S(0),,Sn1(0)}. For infinite set, I mean a set for which there is no bijection between it and any In, nN.


Answer




Yes. Your proof is correct.



Indeed, if f:N{0,,n1} is injective, then restricting the function to {0,,n} would be an injection from a finite set into a proper subset, which is a contradiction to the pigeonhole principle.



One can argue in several other ways, e.g. using Peano axioms, or other axioms from which you can obtain (in a second-order) the natural numbers in a relatively natural way. These ways lend themselves to slightly different proofs. But your suggested proof is correct, and is a fairly standard proof in elementary set theory courses.


No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...