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