Call a set finite if there is a bijection of the set with some natural number, and call a set infinite if there is an injection of the set of natural numbers into that set.

How do you prove that sets which are not finite are infinite? Does it require using the Axiom of Choice?


I'm going to give this a go - apologies in advance if there are errors. I assume you're relatively fluent with ordinals (i.e. thinking of numbers as sets, etc.)

Let $A$ be the set in question. If $n$ is any natural number then by assumption $A$ is not in bijection with $n$; the Law of Trichotomy (which requires Choice, I believe) then implies that either $A<n$ or $n<A$.

If $A<n$ there is an injection of $A$ into $n$, which is then a bijection onto its image - but its image, being a subset of $n$, is in bijection with some (smaller) natural number, and this contradicts the assumption on $A$.

Therefore $n<A$ for every natural number $n$; in other words we have injections $n \hookrightarrow A$ for all $n \in \mathbb{N}$. Furthermore we can choose these injections so that they commute with the natural inclusions $n \hookrightarrow m$ for $n<m$.

Now define our map $f: \mathbb{N} \rightarrow A$ by setting $f \vert_n$ equal to the chosen injection $n \hookrightarrow A$, for all natural numbers $n \subseteq \mathbb{N}$. This is well-defined because of the commutativity assumption in the previous paragraph.

Finally, $f$ is an injection: for if $a,b \in \mathbb{N}$ with $f(a) = f(b)$, then we can choose $n$ bigger than both $a$ and $b$, and then: \begin{equation*} f \vert_n(a) = f(a) = f(b) f \vert_n(b) \end{equation*} And therefore $a=b$ by injectivity of $f\vert_n$.

  • $\begingroup$ If you are going to invoke the law of trichotomy, it's much much simpler to just say that either $|A|\leq|\Bbb N|$ or $|\Bbb N|<|A|$. And then just show that a non-finite subset of $\Bbb N$ is infinite. $\endgroup$ – Asaf Karagila Oct 9 '14 at 19:19
  • $\begingroup$ Aha, very nice! Thanks for pointing that out - I think the resulting proof is quite elegant. $\endgroup$ – Navid Nabijou Oct 12 '14 at 16:52

Yes you do need the Axiom of Choice, together with a suitable Recursion Theorem.

Let $A$ be non-finite and let a choice function $\,\,f: \mathscr P(A)\smallsetminus\{\varnothing\}\to A$, such that $f(B)\in B$.

Let $a_0\in A$ and call a relation $R\subset \mathbb N\times A$ acceptable if $(0,a_0)\in R$, and if $$ (0,a_0), \ldots, (n,a_n)\in R, $$ then $\,(n+1,a_{n+1})\in R$, where $a_{n+1}=f(A\smallsetminus\{a_0,\ldots,a_n\})$.

Finally, set $G=\cap\{R\subset\mathbb N\times A : R\,\,\text{is acceptable}\},$ and show that $G$ is a function $G:\mathbb N\to A$, which is 1-1.

  • $\begingroup$ maybe you can avoid the recursion using Zorn $\endgroup$ – Exodd Oct 9 '14 at 18:58
  • $\begingroup$ Correct. But I am under the impression that the OP wants to see how the AC is used. $\endgroup$ – Yiorgos S. Smyrlis Oct 9 '14 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.