Axiom Of Choice

Description: Relationships between the different definitions of finite

Content:

In this note we summarize what is known about the relationships between possible definitions of ``finite''.

Several authors have studied this topic. They include

The first eight definitions and their names are due to Tarski [1954a].

Definition: A set \(A\) is said to be

decomposable if there are two pairwise disjoint non-empty sets \(x\) and \(y\) such that \(x\prec A\), \(y\prec A\), and \(A = x\cup y\). (Similarly, a cardinal number \(m\) is said to be {\it decomposable}, if there exist two non-zero cardinal number \(p\) and \(q\) such that \(p< m\), \(q < m\), and \(m = p+q\).)
Dedekind finite if it is not equivalent to a proper subset of itself. Otherwise, \(A\) is Dedekind infinite.
\(T\)-finite if every non-empty, monotone \(X\subseteq \cal P(A)\) has a \(\subseteq\)-maximal element.
I-finite if every non-void family of subsets of \(A\) has an \(\subseteq \)-maximal element. (This is (equivalent to) the usual definition of finite.)
Ia-finite if it is not the union of two disjoint sets neither of which is I-finite.
II-finite if every non-empty \(\subseteq \)-monotone family of subsets of \(A\) has a \(\subseteq \)-maximal element.
III-finite if the power set of \(A\) is Dedekind finite.
IV-finite if \(A\) is Dedekind finite.
it V-finite if \(| A| =0\) or \(2\cdot | A| > |A|\). \item{}{\it VI-finite} if \(| A| = 0\) or \(| A| = 1\) or \(| A| ^{2} > | A|\).
VII-finite if \(A\) is I-finite or not well orderable.

In Tarski [1954a] and Levy [1958] it is shown that if a set is finite according to any definition in the above list then it is finite according to any following definition and none of the reverse implications hold.

In Tarski [1938b]}, the following definitions are considered:

Definition: For each \(n\in\omega\), A set \(A\) is \(T(n)\)-finite if for every \(S \subseteq {\cal P}(A)\), if every collection of \(n\) non-empty, pairwise disjoint subsets of \(A\) contains an element of \(S\), then there are \(2n + 1\) elements \(x(i)\), \(1 \le i \le 2n + 1\) of \(S\) such that \(A \subseteq \bigcup \{x(i) : 1 \le i \le 2n + 1 \}\).

In Howard/Yorke [1989] the following definition is introduced:

Definition: A set \(A\) is \(D\) finite if \(|A| = 0\) or \(|A| = 1\) or \(A = C \cup D\) with \(|C| < |A| \) and \(|D| < | A| \). (Note that \(A\) is \(D\) finite if and only if \(|A| = 0\) or \(|A| = 1\) or \(A\) is decomposable.

It is shown there that IV \(\rightarrow D\) and \(D \rightarrow \) VII. Further, V \( \not\rightarrow D\) and \(D \not\rightarrow \) VI.

In Truss [1974a] the following classes of Dedekind finite cardinals are considered:

Definition:

\(\Delta_{1} = \){\(x: x = y + z \rightarrow y\) or \(z\) is finite}. (We will say \(A\) is \(\Delta_{1}\) finite if \(|A|\in \Delta_{1}\). \(\Delta _{1}\)-finite is equivalent to \(I\)a-finite.)
\(\Delta_{2} = \{|A|\) : any linearly ordered partition of \(A\) is finite \(\}\). (\(\Delta_{2}\)-finite is equivalent to \(II\)-finite.)
\(\Delta_{3} = \{|A|\) : any linearly ordered subset of \(A\) is finite \(\}\).
\(\Delta_{4} = \{x: \neg (\aleph _{0} \le ^{*} x) \}\). (\(\Delta _{4}\)-finite is equivalent to \(III\)-finite.)
\(\Delta_{5} = \{x: \neg (x + 1 \le ^{*} x) \}\).

It is shown that I-finite \(\rightarrow\Delta_{1}\rightarrow\Delta_{2} \rightarrow\Delta_{4}\rightarrow \Delta_{5}\rightarrow\) IV-finite and \(\Delta_{2}\rightarrow \Delta_{3} \rightarrow\) IV-finite and that none of the implications are reversible. It is also shown that various combinations of equality and inequality between these classes are consistent. For example, it is shown that

\(ZF+ω=Δ1=Δ2=Δ4≠Δ5≠ IV\)-finite \(+Δ2=Δ3≠ IV\)-finite is consistent.

In Diel [1974]two definitions are finite are considered: ``Almost finite'' which is equivalent to III-finite and ``strongly Dedekind finite'' which is equivalent to \(\Delta_{5}\)-finite.

Finally in Howard/Spiusiak [1994], Spiusiak [1993], and Spiusiak/Vojtaus [1988] the following forms are considered:

Definition: Let \(F\) be one of I, Ia, II, III, IV, V, VI or VII. Then a set \(A\) is \(F''\)-finite if \({\cal P}(A)\) is \(F\)-finite.

It is shown that each of I\(''\), Ia\(''\), II\(''\) and III\(''\) are equivalent to I and that the following implications hold: III \(\rightarrow \) V\(''\) \(\rightarrow\) IV, V\(''\) \(\rightarrow \) VI\(''\) \(\rightarrow\) V, and VII \(\rightarrow\) VII\(''\). Further it is consistent (with ZF) that there exists a set with any combination of the properties III, V\(''\), VI\(''\), IV and V not excluded by the known implications described so far in this note. Finally, it is shown that form 88 (\(C(\infty ,2)\)) implies that V\(''\) and III are equivalent.

In addition, in Howard/Yorke [1989], if \(J\) and \(K\) are two possible definitions of finite then the assertion that \(J\) and \(K\) are equivalent is denoted by \(E(J,K)\) and the strength of these weak forms of \(AC\) is investigated. Several of these appear in the list of forms:

\(E(I,IV)\) is Form 9,
\(E(I,Ia)\) is Form 64,
\(E(I,III)\) is Form 82,
\(E(I,II)\) is Form 83,
\(E(II,III)\) is Form 84,
\(E(II,IV)\) is [9 B],
\(E(IV,V)\) is [3 E],
\(E(V,VI)\) is [1 AH],
\(E(VI,VII)\) is [1 AI],
\(E(V'',III)\) is Form 276 and
\(E(D,VII)\) is Form 277.

We note that \(E(I,D)\) which is equivalent to "every infinite set is decomposable" is equivalent to the axiom of choice since it is form CN 4F in H. Rubin/J. Rubin [1985], p. 139.

The relationships between the various definitions of finite are summarized in the following diagram:

Howard-Rubin number: 94

Type: Summary of definitions

Back

Notes