Question

Show that a set S is infinite if and only if there is a proper subset A of S such that there is a one-to-one correspondence between A and S.

Short answer

S is infinite if and only if there is a proper subset A of S such that there is a one-to-one correspondence between A and S.

Step-by-step solution

Step: 1

Suppose S is infinite, and take a countably infinite subset $T=\left\{s_0,s_1,\dots \right\}$of S. Then there exist the map $\varphi :S\to S$ such that$\varphi \left(x\right)=x\mathrm{\forall }x\notin T\text{and}\varphi \left(s_i\right)=s_{i+1}$ and for elements of the subset T.

Step: 2

The map$\varphi$ is not surjective, so S is infinite. Since $S\supseteq T=\left\{t_1,t_2,t_3,..\right\}$

$\begin{array}{r}{t}_1\leftrightarrow t_2\\ t_2\leftrightarrow t_4\\ t_3\leftrightarrow t_6\\ t_4\leftrightarrow t_8\\ t_5\leftrightarrow t_{10}\end{array}$

and for $s\in S\mathrm{\setminus }T,s\leftrightarrow s$

Step: 3

This a one-to-one correspondence between S and a proper subset of S. The proper subset contains as a member everything that appears to the right of the arrows above.