Prove that a set is infinite if and only if it is equipotent to a proper subset.

elementary-set-theoryset-theory

Prove that a set $X$ is infinite if and only if it is equipotent to a proper subset $H$.

Proof.

Suppose $X$ is equipotent to a proper subset $H$. Then there exists a bijection $f: H \to X$. Toward a contradiction, suppose $X$ is finite.

Since $X$ is finite, $H$ is finite. Moreover, we can write

$$X = \{x_1, x_2, \dots, x_n\} \hspace{1cm} H = \{h_1, h_2, \dots, h_m\}$$

Since $f$ is injective, $h_j \neq h_k$ implies $f(h_j) \neq f(h_k)$. But recall that $H$ is proper, so $\exists \, x_i \in X \setminus H$.


But at this point, I get stuck. Intuitively, I understand that this can not be a bijection, but I'm having trouble showing this.

I have already read Proof that a set is infinite if and only if it has an infinite proper subset and this post does not provide an actual proof answer or assumes that the set is countable.

Best Answer

We want to prove that:
(1) X is equipotent to a proper subset H if and only if (2) X is an infinite set.

Note: X is equipotent to H $\begin{smallmatrix} def \\ \iff \\ \space \end{smallmatrix}$ there is a bijection between X and H $\begin{smallmatrix} def \\ \iff \\ \space \end{smallmatrix}$ |X|=|H| (they have the same cardinality)

H is a proper subset of X $\begin{smallmatrix} def \\ \iff \\ \space \end{smallmatrix}$ H $\subsetneq$ X.

Proof

(1)$\Rightarrow$(2) Assume by contradiction that X is finite. Since there exist a bijection $f:X\rightarrow H$ then by definition of cardinality $|X|=|H|$. But H is a subset of X which is proper so $\forall h \in H : h \in X$ but $\exists x \in X : x \notin H$. Hence H has at least one element less than X, so $|H|<|X|$ - contradiction.

(2)$\Rightarrow$(1) To prove this direction in (ZF) we need the condition "X is a Dedekind-infinite set" instead of just an infinite set. However, we can prove it in (ZF + ACw) applying the axiom of countable choice:

enter image description here

In wikipedia you can find the proof that every infinite set is Dedekind-infinite in (ZF + ACw).