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.
Best Answer
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 $[0] \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.