I'm stuck one the following exercise:
"Let $X$ be a set. Show that $X$ is infinite if and only if there exists a proper subset $Y$ of $X$ which has the same cardinality as $X$."
I've managed to prove the leftward implication, but not the rightward one; I do know it requires the Axiom of Choice, which in the text is stated as follows:
"Let $I$ be a set, and for each $\alpha \in I$, let $X_{\alpha}$ be a non-empty set.
Then $\prod _{\alpha \in I} X_{\alpha}$ is also non-empty.
In other words, there exists a function $(x_{\alpha})_{\alpha \in I}$ which assigns to each $\alpha \in I$ an element $x_\alpha \in X_\alpha$."
where:
- $\prod _{\alpha \in I} X_{\alpha}:=\{(x_{\alpha})_{\alpha \in I} \in (\bigcup_{\beta \in I} X_\beta)^I: x_\alpha \in X_\alpha \forall \alpha \in I \}$;
- $(\bigcup_{\beta \in I} X_\beta)^I $ is the set of all functions $(x_{\alpha})_{\alpha \in I}$ which assign an element $x_\alpha \in \bigcup_{\beta \in I} X_\beta$ to each $\alpha \in I$;
but I haven't been able to use it to carry out this proof; the most I have been able to prove with this axiom is the fact that if $X$ is an infinite set then it contains a countable subset.
So, I would appreciate any hints about how to carry out this proof.
Best regards,
lorenzo.
note:
-
in the text I'm using the definition of finite and infinite set is as follows:
DEF.(Finite and infinite set) A set is $finite$ iff it has cardinality $n$ for some natural number $n$; otherwise, the set is called $infinite$;
-
I've read If A is infinite, does there have to exist a subset of A that is equivalent to A? but I didn't completely understand the proof given there (especially the "Now we're done:… which is a proper subset of $A$." part.
-
the Schroder-Bernstein theorem is introduced later in the book and therefore I can't use it in this proof.
Best Answer
If you've shown $X$ contains a countable subset $A = \{ a_1, a_2, \dots \}$, then you can throw away $a_1$ in the following way.
By the inclusion map, $X \setminus \{ a_1 \}$ clearly injects into $X$. Conversely, $X$ injects into $X \setminus \{ a_1 \}$: $a_n \mapsto a_{n+1}$, and any other $x \mapsto x$ (if $x$ isn't any $a_i$).
Therefore, by Schröder-Bernstein, there is a bijection between the two, although actually this is massive overkill: an explicit bijection is
$$f: X \to X \setminus \{ a_1 \}$$ by $$a_i \mapsto a_{i+1}; x \mapsto x$$