How to prove that a set is infinite iff it is Dedekind infinite?

I need to prove the following:

A set $X$ is infinite if and only if it is equipotent to a proper subset of itself

Here, $X$ is defined to be infinite if $|X|$ is not a non-negative integer or equivalently, there is no bijection $\mathbb{N}_n \rightarrow X$ for $n\in \mathbb{Z}^\ge$.

My attempt:

The given statement is equivalent to:

$X$ is equipotent to a proper subset of itself $\Leftrightarrow$ $X$ is infinite

Case '$\Rightarrow$':

$X$ is equipotent to a proper subset of itself means that if $A \subset X$, then there exists a bijection $A\rightarrow X$. Therefore, $|A|=|X|$.

But $A\subset X$ implies $|A|<|X|$

This is a contradiction but I am not doing a proof by contradiction so I this outcome is strange to me.

I know that $|A|<|X|$ then no bijection $A \rightarrow X$ can exist. But the bijection must exist since we assumed $A$ and $X$ are equipotent. How do I resolve this and complete the proof?

Case '$\Leftarrow$'

I am stumped by the solution provided: The main problem I have is the inductive proof showing that $A$ is a denumerable subset.

In the base case, the set $A$ has only 1 element, namely $a_1$, so, I don't see how it is possible to build a bijection $\mathbb{Z}^+\rightarrow \{x_1\}$

I don't even understand the inductive step as I don't know when the inductive hypothesis is used. In fact, I am not able to discern what the inductive hypothesis is.

It would be helpful if some one could explain how this proof is trying to show the existence of a denumberable subset for any given indefinite set as well as state what the $P(n), P(k)$ and $P(k+1)$ for this proof by induction are.

• $A \subset X$ does not imply $|A| < |X|$, consider for example $X = \mathbb{N}$ and $A = \{2 n \mid n \in \mathbb{N}\}$. Aug 27 '14 at 20:52
• The proof that an infinite set contains a denumerable set is hiding an application of choice under the carpet, and so it is confusing. Furthermore, the set $A$ in that part of the proof is not what you think the set $A$ is. Aug 27 '14 at 20:54
• @Andrej: My experience from last year was that students were even more confused when you tried to explain to them why this might fail without the axiom of choice (at least in a naive set theory course, before being properly comfortable with the axiom). Next year I am going to take another approach, let's see how it'll work out. Aug 27 '14 at 21:04
• I wrote down the proof as I would (and will) teach it to my first years. We'll see how it goes. Also, I think we need to be honest with the students about choice. If we sweep it under the carpet, how will they ever learn to detect it? Aug 27 '14 at 21:52
• @Andrej: Between Azriel Levy as the professor, and the mini course I did in the exercise sessions (which only at the end of the semester I learned were much beyond the syllabus), I don't think either of us swept choice under the rug. Aug 28 '14 at 3:26

I am going to replace some definitions by obviously equivalent ones. The benefit will be that the proofs are easier to understand. I am writing down very detailed proofs that you would not normally find in a college-level math textbook.

Definition: For $n \in \mathbb{N}$ define $[n] = \{k \in \mathbb{N} \mid k < n\}$.

Definition: The image of a map $f : X \to Y$ is the set $\mathrm{im}(f) = \{y \in Y \mid \exists x \in X \,.\, f(x) = y\}$.

Definition: A set $X$ is infinite when for every $n \in \mathbb{N}$ and every map $f : [n] \to X$ there is some $x \in X$ which is not in the image of $f$.

Lemma 1: An infinite set $X$ contains an element.

Proof. Because $X$ is infinite there is $x \in X$ which is not in the image of the unique map $ \to X$. QED.

Lemma 2: If $X$ is infinite then there exists a map $c$ such that $c(n,f) \in X \setminus \mathrm{im}(f)$ for every $n \in \mathbb{N}$ and every $f : [n] \to X$.

Proof. For every $n \in \mathbb{N}$ and $f : [n] \to X$ the set $X \setminus \mathrm{im}(f)$ contains an element because $X$ is infinite. By the axiom of choice there exists a choice map $c$ such that $c(n,f) \in X \setminus \mathrm{im}(f)$ for all $n$ and $f$. QED.

Here is an informal explanation of the map $c$. Given an infinite set $X$ and any elements $x_0, \ldots, x_{n-1} \in X$, we may view the tuple $(x_0, \ldots, x_n)$ as a map $f : [n] \to X$ where $f(k) = x_k$. By a slight abuse of notation we can then write $c(n,f)$ as $c(x_0, \ldots, x_{n-1})$. Now we see that $c$ accepts finitely many elements of $X$ and returns an element in $X$ which is different from all of them.

Proposition 1: If $X$ is infinite then there exists an injective map $i : \mathbb{N} \to X$.

Proof. By Lemma 1 there is $x \in X$ and let $c$ be the map from Lemma 2. Define $i$ by recursion: \begin{align*} i(0) &= x \\ i(n) &= c(i(0), \ldots, i(n-1)) \qquad\qquad \text{for $n \geq 1$} \end{align*} Clearly, $i$ is injective because $i(n)$ is chosen so that it is different from $i(0), i(1), \ldots, i(n-1)$. QED.

Proposition 2: If $X$ is infinite then it is in bijection with some proper subset $Y \subseteq X$.

Proof. Suppose $X$ is infinite. We seek a proper subset $Y \subseteq X$ and a bijection $f : X \to Y$. Let $i$ be the map from Proposition 1. Define $$Y = X \setminus \{i(0)\}$$ and define $b : X \to Y$ by $$b(x) = \begin{cases} x & \text{if x \not\in \mathrm{im}(i)}\\ i(n+1) & \text{if x = i(n) for a (unique) n \in \mathbb{N}} \end{cases}$$ in words, $b$ takes $i(0)$ to $i(1)$, $i(1)$ to $i(2)$, and so on, and does not move elements which are outside the image of $i$. Clearly, $b$ is injective because $i$ is. It is surjective because the only element not in the image of $b$ is $i(0)$. QED.

Proposition 3: If $X$ is a set and $b : X \to Y$ a bijection from $X$ to a proper subset $Y \subseteq X$, then there is an injective map $j : \mathbb{N} \to X$.

Proof. Because $Y$ is a proper subset there exists $x \in X \setminus Y$. We define a map $j : \mathbb{N} \to X$ by recursion: \begin{align*} j(0) &= x \\ j(n) &= b(j(n-1)) \qquad\qquad\text{for $n \geq 1$} \end{align*} To prove that $j$ is injective, it suffices to verify that $j(m) \neq j(n)$ for all $m < n$. We do this by induction on $m$:

• if $m = 0$ then $j(0) = x$ is different from $j(n) = b(j(n-1))$ because $b(j(n-1)) \in Y$ and $x \not\in Y$.

• for the induction step, suppose we had $j(m) = j(n)$ for some $0 < m < n$. Then we would have $b(j(m-1)) = j(m) = j(n) = b(j(n-1))$ and because $b$ is a bijection it would follow that $j(m-1) = j(n-1)$, which is impossible by the induction hypothesis for $m-1$. Therefore it must be the case that $j(m) \neq j(n)$.

QED.

Theorem: A set is infinite if, and only if, it is equipotent with some proper subset.

Proof. If $X$ is infinite then we apply Propostion 2 to get a proper subset $Y \subseteq X$ which is equipotent with $X$.

Conversely, suppose we have a bijection $b : X \to Y$ for a proper subset $Y \subseteq X$. By Proposition 3 there is an injective map $j : \mathbb{N} \to X$. To see that $X$ is infinite, consider any $n \in \mathbb{N}$ and $f : [n] \to X$. There are $n+1$ distinct elements $j(0), j(1), \ldots, j(n) \in X$, and so at least one of them is not in $\mathrm{im}(f)$ because $\mathrm{im}(f)$ has at most $n$ elements. QED.

• Thank you for this really detailed answer. It clarified alot of my doubts and helped to understand the other answers. I just need some clarification on Proposition 1. Can $i$ be surjective too? I know that the assumption that $X$ is infinite means that there is no bijection $\mathbb{N}_n \rightarrow X$ for some $n\in \mathbb{N}$. But it does not say anything about a bijection $\mathbb{N} \rightarrow X$ Aug 30 '14 at 4:49
• If $X$ is countably infinite then of course there is a bijection $b : \mathbb{N} \to X$ (by definition of "countably infinite"), but the proof of Proposition 1 need not produce such a bijection: it could happen that the $i$ we get from the proof is not surjective, even though some other map $b : \mathbb{N} \to X$ is surjective. Aug 30 '14 at 8:19
• Also, there are infnite sets $X$ such that there is no bijection from $\mathbb{N}$ to $X$. These are called uncountable. I don't know how much you already know, perhaps you already knew that. Aug 30 '14 at 8:20

Let me address quickly the first part of the proof, $\Rightarrow$. You don't need to do it by contradiction. You can show that if $f\colon X\to A$ is a bijection, where $A$ is a proper subset of $X$, then there is an injection from $\Bbb N$ into $X$, and therefore $X$ is infinite.

To your second question, perhaps it would have been better to say "recursive construction", since many people only see "induction" as a method for proving statements and not for constructing mathematical objects (which they would say is a recursive definition).

The inductive step says, suppose that $\{a_1,\ldots,a_k\}$ is a defined set, let's define $\{a_1,\ldots,a_k,a_{k+1}\}$. How do we define it? We simply choose an element from $X\setminus\{a_1,\ldots,a_k\}$. Why can we do it? Because $X$ is infinite and we only removed a finite set from $X$.

You might argue, what is $a_{k+1}$? Which element is it? Well, you can't quite pinpoint that element, because you have to make some arbitrary choice and you have to appeal to the axiom of choice. Namely, we first fix some "black box operation" that given a non-empty subset of $X$, it will give us back an element of that subset. And then we use this black box to choose $a_{k+1}$.

So no one is constructing a bijection between an infinite set and a singleton. We construct an infinite set, then we show that this set is denumerable. But that's quite simple because we literally chose for each $n$ a different element, so the map $k\mapsto a_k$ is necessarily an injection.

• Can you also comment on the base case? I am still seeing it as constructing a bijection between an infinite set, $\mathbb{Z}^+$ to $\{a_1\}$ Aug 27 '14 at 21:38
• Why? If the induction merely constructs a set, not a bijection; and the induction hypothesis is that a set of size $k$ has been constructed. Do you really need me to spell out the base case? Aug 28 '14 at 3:49

In the case $\Rightarrow$ you are actually arguing by contradiction. Note that $A\subset X, A\ne X\implies |A|< |X|$ if $X$ is finite. In other case you may have $|A|=|X|.$ For example, $\mathbb{N}\subset \mathbb{Z}.$

Now consider the case $\Leftarrow.$ The denumerable subset $A$ is constructed by induction. You start consider any element in $X,$ say $a_1,$ and you have the subset $A_1.$ Now, you assume you have constructed a subset $A_k$ with $k$ different elements. (This is the induction hypothesis, $P(k)$.) Now from $A_k$ you construct a set $A_{k+1}$ with $k+1$ different elements (that is, you prove $P(k+1)$. Note that $A\ne A_k$ for any $k.$ It is $A=\bigcup_{k\in \mathbb{N}} A_k.$

• how is $A_1$ denumerable? Is $P(n)$ "For any $n\ge1$, we can construct a denumerable set, $A$, such that $A\subset X$, where $X$ is an infinite set"? Aug 27 '14 at 21:17
• $P(n)$ is "there exists a finite subset of $X$ with exactly $n$ different elements".
– mfl
Aug 27 '14 at 22:51
• Please correct me if i'm wrong. Your the denumerable subset $A$ is constructed on the basis of Principle of Generalized Recursive Construction (wikiwand.com/en/Transfinite_induction#/Transfinite_recursion)? Sep 4 '18 at 3:38