Let $X$ be an infinite set. It follows (and viceversa) that there exists a bijection from $X$ to a proper subset of $X$. In particular, there exists an injection from $X$ into a proper subset of $X$. Now let $f_0:X \longrightarrow X_1$ be an injection into a proper subset $X_1 \subset X$, and let $f_1:X_1 \longrightarrow X_2$ be an injection into a proper subset $X_2 \subset X_1$, and so on, so that $\{f_\alpha \hspace4pt|\hspace4pt \alpha \in J \}$ is an indexed set of maps with the property that $f_\alpha:X_\alpha\longrightarrow X_{\alpha+1}$ is an injection into a proper subset $X_{\alpha+1} \subset X_\alpha$. The idea is that we get a sequence of proper subsets

$$X \supset X_1 \supset X_2 \supset \cdots \supset X_\alpha \supset X_{\alpha+1} \supset \cdots$$

chained together by injections.

In this sequence of subsets, is it possible to (eventually) arrive at a subset $X_\alpha \subset X$ whose cardinality is strictly smaller than the cardinality of $X$? I'd say no.

What's a (not too formal) explanation of why this is impossible? Or perhaps it's sometimes possible? But it can't always be, because, for instance, then you could inject an infinite countable set into a finite subset of itself, which I don't think you can.

  • $\begingroup$ The Cantor-Schroeder-Bernstein theorem? $\endgroup$ – Angina Seng Dec 23 '17 at 19:43
  • 1
    $\begingroup$ Please insert the definition of "cardinality" into your question, just to observe that it's a moot point. $\endgroup$ – Professor Vector Dec 23 '17 at 19:47
  • $\begingroup$ Is $J$ just the natural numbers? Otherwise I don't know in what sense you are considering your sequence to be "chained together by injections". $\endgroup$ – Eric Wofsey Dec 23 '17 at 19:59
  • $\begingroup$ The "chain" is handwaving. There must exist some $X_n \to X_{n+1}$ that is an injection to a lower cardinality. ANd that is basically violates the definition of cardinality. $\endgroup$ – fleablood Dec 23 '17 at 20:17

If there exist injections $X\to Y$ and $Y\to X$, then there exists a bijection $X\to Y$ by Schröder-Bernstein, so $X$ and $Y$ have the same cardinality. In particular, if $X_\alpha\subseteq X$ but there is an injection $X\to X_\alpha$, then $X$ and $X_\alpha$ have the same cardinality (since the inclusion map is an injection $X_\alpha\to X$).

| cite | improve this answer | |

To extend Professor Vector's comment:

Two sets $A$ and $B$ have the same cardinality iff there exists a bijection $f:A\rightarrow B$. In your construction, you use the injections $f_\alpha$. But every injection is a bijection onto its image, so an injection must preserve cardinality. I.e., you can't get strictly smaller.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.