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,…,n−1}. We know that f↾In is injective and its image is a proper subset of In. From here, we can show that, by restricting the codomain of f↾In to f↾In(In), we obtain a bijection from a proper subset of In, that is, f↾In(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),…,Sn−1(0)}. For infinite set, I mean a set for which there is no bijection between it and any In, n∈N.
Answer
Yes. Your proof is correct.
Indeed, if f:N→{0,…,n−1} 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