3
$\begingroup$

This follows Arturo's answer of this question.

Let $I$ an infinite set and $\{E_i\}_{i\in I}$ a family of finite sets.

It is said that there exists an injection

$\bigcup_{i\in I} \ E_i \to I.$

In the comments, an argument with "$\aleph$ numbers" (which I haven't studied yet) is given.

I wondered how one could build this injection explicitely ? I have been trying for some time now, but it is quite hard to have intuition about that.

  • 1
    And, generally, when it is said that the existence of something depends on the Axiom of Choice, you shouldn't expect to be able to construct an example explicitly. (It's just barely possible that an explicitly constructible example _exists_, but it will usually not be _provable_ that said explicit construction _is_ in fact an example. (Exceptions include pathologic examples such as "there exists a natural number $n$ such that $2+n=4$ and the Axiom of Choice holds")).2011-10-08

1 Answers 1

2

If the axiom of choice is assumed then we can simply well order everything and just define by induction an injective map.

Simply choose $f_i\colon E_i\hookrightarrow\mathbb N$ which is an injection. Since we assume the axiom of choice we also have:

$\tag{1}|I|=|I\times I|\ge|I\times\mathbb N|=|I|$ We can now inject $E_i$ into $\{i\}\times\mathbb N$, and use $(1)$ to obtain a bijection into $|I|$, and thus into $I$.


Without the axiom of choice it is consistent to have a countable union of disjoint pairs, and the result is not at all countable, so there is no such injection.

(This example is of course Russell's well known saying that you need the axiom of choice to choose from infinitely many pairs of socks.)

  • 0
    Well,$I$knew what $\aleph_0$ is long before I knew what aleph numbers are. For several years I was under the impression that $\aleph_1$ was defined to be $2^{\aleph_0}$, the cardinality of the continuum. In fact the definition of $\aleph_1$ as the cardinality of the set of all countable ordinals goes all the way back to Cantor.2011-10-09