Countable axiom of choice

Each set in the countable sequence of sets contains at least one element. The axiom of countable selection allows one element to be selected from every set at the same time. ${\displaystyle (S_{n})_{n}}$

The countable choice axiom , also called the axiom of countable choice , (from English axiom of countable choice , hence AC _ω for short , for the meaning of the symbol ω see ordinal numbers ) is a weak form of the choice axiom . It says that every countable set of non-empty sets has a selection function.

The axiom of dependent choice (DC) implies the countable choice axiom, the reverse is not true.

ZF + AC _ω suffices to prove that the countable union of countable sets is countable again. It is also sufficient to show that every infinite set is Dedekind-infinite .

AC _ω is particularly useful when working out analysis, where results often depend on being able to choose from a countable set of subsets of the real numbers. In order to show, for example, that each accumulation point of a sequence of real numbers is the limit value of a partial sequence, AC _{ω is} used, whereby in this case an even weaker variant would be sufficient. For general metric spaces, however , the statement is equivalent to AC _ω . Further examples are given by Herrlich as well as Howard and Rubin (see references).

formulation

The countable axiom of choice can be formulated as follows, the logical equivalences result easily:

• If there is a countable set of non-empty sets, then there is a function with for all . (A function with this property is called a selection function.) ${\displaystyle A}$ ${\displaystyle f\colon A\to \bigcup A}$ ${\displaystyle f(a)\in a}$ ${\displaystyle a\in A}$
• The countable Cartesian product of non-empty sets is not empty.
• If there is a sequence of non-empty sets, then there is a sequence with ${\displaystyle \left(A_{n}\right)_{n\in \mathbb {\omega } }}$ ${\displaystyle \left(a_{n}\right)_{n\in \mathbb {\omega } }}$ ${\displaystyle a_{n}\in A_{n}.}$

If one replaces countable with finite in the first two statements , one obtains statements that can be proven without a choice axiom, i.e. in ZF. If, on the other hand, one allows arbitrary quantities, one obtains the general axiom of choice.

Of course, for certain (possibly uncountable) sets of non-empty sets, a selection function can also be specified without the (countable) selection axiom, e.g. B.

• if the section is not empty, because then there is a constant selection function, ${\displaystyle \bigcap A}$
• if the union probably arrange can, because then it can be taken from each lot of the respect smallest of the well-ordering element, and ${\displaystyle \bigcup A}$
• if it is a family of intervals of real numbers, then the element in the middle can always be taken.

On the other hand, even with a countable family of two-element sets, the existence of a selection function cannot be proven in ZF.

Inferences

Every infinite amount is also Dedekind-infinite

Because be infinite. For be the set of -element subsets of . Since is infinite, all are not empty. Applying AC _ω to yields a sequence where is a subset of with elements. Sit now ${\displaystyle X}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle A_{n}}$ ${\displaystyle 2^{n}}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle A_{n}}$ ${\displaystyle (A_{n})_{n}}$ ${\displaystyle \left(B_{n}\right)_{n\in \mathbb {\omega } }}$ ${\displaystyle B_{n}}$ ${\displaystyle X}$ ${\displaystyle 2^{n}}$

${\displaystyle C_{n}=B_{n}\setminus \bigcup _{j=0}^{n-1}C_{j}}$.

Obviously, each contains between and elements and they are disjoint. Another application of AC _ω gives a sequence , where is. ${\displaystyle C_{n}}$ ${\displaystyle 2^{n}}$ ${\displaystyle C_{n}}$ ${\displaystyle \left(c_{n}\right)_{n\in \omega }}$ ${\displaystyle c_{n}\in C_{n}}$

Thus all are different and have a countable subset. The function on maps and all other elements of leaves unchanged is injective but not surjective and proves that Dedekind-infinity is. ${\displaystyle c_{n}}$ ${\displaystyle X}$ ${\displaystyle c_{n}}$ ${\displaystyle c_{n+1}}$ ${\displaystyle X}$ ${\displaystyle X}$

The union of countable sets is countable

Let it be a countable set of countable sets. We want to show that the union is countable again. Since each is at most countable, the set of surjective mappings is not empty. By applying AC _ω to, choose a surjective function for each . The image ${\displaystyle \left\{A_{n}\mid n\in \mathbb {\omega } \right\}}$ ${\displaystyle \textstyle \bigcup _{n\in \omega }A_{n}}$ ${\displaystyle A_{n}}$ ${\displaystyle F_{n}}$ ${\displaystyle \omega \to A_{n}}$ ${\displaystyle (F_{n})_{n}}$ ${\displaystyle n}$ ${\displaystyle f_{n}\colon \omega \rightarrow A_{n}}$

${\displaystyle f\colon \omega \times \omega \to \bigcup _{n\in \omega }A_{n}}$

${\displaystyle f\colon (n,m)\mapsto f_{n}(m)}$ is then also surjective, i.e. the union is countable.

Literature sources

• TJ Jech: The Axiom of Choice. North Holland, 1973.
• Horst Herrlich: Choice principles in elementary topology and analysis . In: Comment.Math.Univ.Carolinae . 38, No. 3, 1997, pp. 545-545.
• Paul Howard, Jean E. Rubin: Consequences of the axiom of choice . In: American Mathematical Society (Ed.): Providence, RI . 1998.
• Michael Potter: Set Theory and its Philosophy. A Critical Introduction. Oxford University Press, 2004, ISBN 0-19-155643-2 , p. 164 ( books.google.com ).