Dedekind finite

From Cantor's Attic
Jump to: navigation, search

Let $X$ be a set, we say that $X$ is an Dedekind infinite set if there exists $Y\subsetneqq X$ and $f:X\to Y$ which is a bijection, otherwise we say that $X$ is Dedekind finite.

Every finite set is Dedekind finite, however the assertion that every infinite set is Dedekind infinite requires some choice. It follows from the assertion that every countable family of non-empty sets has a choice function. In particular, $X$ is Dedekind infinite if and only if $\aleph_0\le|X|$.

Classes of Dedekind finite sets

There are several classes of Dedekind finite sets: (in this context ordered means linearly ordered)

  1. $\omega$, the set of finite cardinals.
  2. $\Delta_1 = \{x\mid x=y+z\rightarrow y\in\omega\lor z\in\omega\}$, all those cardinals that cannot be written as the disjoint union of infinite sets (also known as amorphous sets).
  3. $\Delta_2 = \{x\mid\text{ Every ordered partition of }x\text{ is finite}$, all those that cannot be mapped surjectively onto an infinite ordered set.
  4. $\Delta_3 = \{x\mid y\subseteq x\text{ can be ordered}\Leftrightarrow |y|\in\omega\}$, all those that have no injection from an infinite ordered set.
  5. $\Delta_4 = \{x\mid \omega\nleq^\ast x\}$, all those that cannot be mapped surjectively onto $\omega$.
  6. $\Delta_5 = \{x\mid x+1\nleq^\ast x\}$, all the cardinals that cannot be surjectively mapped onto a finitely larger set.
  7. $\Delta = \{x\mid \omega\nleq x\}$, all the Dedekind finite cardinals.

In [Tru74] the relations between the different classes is established, as well various consistency results regrading combinations of these classes.

Various types of infinite Dedekind finite sets are used to counter many implications between different choice principles. For example:

  • By adding a Dedekind finite set of real numbers it is possible to show that the ultrafilter lemma holds; that every set can be linearly ordered; every set can be mapped onto $\omega$; however the axiom of choice fails (for countable families).
  • By adding an amorphous set one shows that it is possible to have that not every set can be linearly ordered.



References

  1. [Tru74] J.K.Truss, Classes of Dedekind Finite Cardinals, Fundamenta Mathematicae 84, 187-208, 1974.