Thursday 25 April 2013

elementary set theory - Show that $mathbb{N}$ is infinite



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



Proof. By contradiction: assume that exists a bijeciton $f$ from $\mathbb N$ to $I_n = \{1, \dots, n-1\}$. We know that $f{\restriction_{I_n}}$ is injective and its image is a proper subset of $I_n$. From here, we can show that, by restricting the codomain of $f{\restriction_{I_n}}$ to $f{\restriction_{I_n}}(I_n)$, we obtain a bijection from a proper subset of $I_n$, that is, $f{\restriction_{I_n}}(I_n)$, to $I_n$ itself. But this is a contradiction. $\square$



Is it a correct proof?



EDIT: I'm using Peano's definition for $\mathbb N$, where $I_n$ is the set $\{0, S(0), \dots, S^{n-1}(0)\}$. For infinite set, I mean a set for which there is no bijection between it and any $I_n$, $n \in \mathbb N$.


Answer




Yes. Your proof is correct.



Indeed, if $f\colon\Bbb N\to\{0,\ldots,n-1\}$ is injective, then restricting the function to $\{0,\ldots,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 $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...