# How do I prove that for any set $A$, $|A| < |\mathbb{N}|$ implies that $A$ is finite?

Here's what I've tried so far.

Let $A$ be a set and suppose $|A| < |\mathbb{N}|$. By the definition of less than for cardinalities (I'm reading out of Hrbacek's Introduction to Set Theory), this means that there exists a one-to-one function $f$ from $A$ onto a subset of $\mathbb{N}$, but there does not exist a one-to-one function from $A$ onto $\mathbb{N}$ itself.

In the book, finite is defined as in bijection with a natural number $n \in \mathbb{N}$. The natural numbers are defined in a weird way:

$$0 = \varnothing$$

$$1 = \{0\} = \{\varnothing\}$$

$$2 = \{0,1\}$$

$$3 = \{0,1,2\}$$

... and so on ad infinitum.

My intuition is this: I want to show that $A$ is in one-to-one correspondence with a finite subset of $\mathbb{N}$, and once I've done this it's trivial to show that $A$ is finite itself (the composition of bijections is a bijection, so $A$ is in bijection with some $n \in \mathbb{N}$, and we're done). I just have no idea how to find the correspondence with a finite subset of $\mathbb{N}$.

If I show that any infinite (infinite is simply defined as not finite) subset of $\mathbb{N}$ is in bijection with $\mathbb{N}$ itself, this would work ...

• This has been asked before. What you want to show is that for any infinite set $A$, $\aleph_0\leqslant \# A$. This can be proven using the axiom of choice. – Pedro Tamaroff Dec 17 '14 at 2:33
• @PedroTamaroff what is $\#A$? EDIT: Are you sure this requires the Axiom of Choice? – Vincent Luo Dec 17 '14 at 2:36
• Consider the following argument: since $A\neq \varnothing$, there is $x_0\in A$. Since $A$ is infinite, there is $x_1\in A\smallsetminus x_0$. Since $A$ is infinite, there is $x_2\in A\smallsetminus \{x_0,x_1\}$. Since $A$ is infinite, $\ldots$. Then $x_i\longleftrightarrow i$ is a bijection, i.e. there is a subset $A'\subseteq A$ equipotent with $\Bbb N$. – Pedro Tamaroff Dec 17 '14 at 2:37
• Then there is a bijection between $A$ and $\mathbb{N}$ via the function that takes $\{x_0, x_1 ... x_n\}$ to $n$? – Vincent Luo Dec 17 '14 at 2:39
• @PedroTamaroff Okay I think this works, the recursion part seems a bit non-rigorous but it makes complete intuitive sense to me – Vincent Luo Dec 17 '14 at 2:40

Given an infinite set of $$A$$ we can define an injection from $$A$$ to $$\mathbb N$$ by the inclusion mapping. define the injective map from $$\mathbb N$$ to $$A$$ where $$1$$ goes to the minimum element of $$\mathbb A$$, where $$2$$ goes to the minimum element of $$A\setminus f(1)$$ and in general map $$n$$ to the minimum element of $$A\setminus \{f(i)|1\leq i\leq(n-1)\}$$.

So if you have an infinite subset of $$\mathbb N$$ it has the same cardinality as $$\mathbb N$$

• Oh, I thought I could do that, sorry I haven't taken set theory yet. – Jorge Fernández Hidalgo Dec 17 '14 at 2:58
• You can prove that $A$ can be well-ordered. Define the order $\prec$ over $A$ such that $x\prec y$ iff $i(x)<i(y)$, where $i$ is an injection from $A$ to $\Bbb{N}$. – Hanul Jeon Dec 17 '14 at 2:58
• I was just using the order on $\mathbb N$ – Jorge Fernández Hidalgo Dec 17 '14 at 2:59
• $A$ is well ordered using the induced order from $\mathbb{N}$. – copper.hat Dec 17 '14 at 3:00
• You could even avoid Cantor-Bernstein by noting that the function mapping $f(n)$ to the minimum of $A\setminus\{f(i)\mid i<n\}$ is a bijection. – Asaf Karagila Dec 17 '14 at 5:54

Let $f:A \to \mathbb{N}$ be an injection. Consider the following recursively defined function $g:D\subseteq \mathbb{N} \to A$:

$$\DeclareMathOperator*{\argmin}{argmin} g(n) = \argmin_{a\in A\setminus\{g(k)|k<n\}}(f(a))$$

Notice that $g$ is a bijection from its domain of definition $D$ to $A$, so $D$ cannot equal all of $\mathbb{N}$ (since $|A| < |\mathbb{N}|$). Therefore there exists some $n = \min(\mathbb{N}\setminus D)$. Observe that $D = \{0, \ldots, n-1\} = n$. So $g$ is a bijection from $n$ to $A$, so $A$ is finite.