\def\ac#1{#1}
\def\ap#1{}
\def\iput#1{}
\def\icopy#1{#1}
\input amstex
%\undefine\eth
\documentstyle{amsppt}
\pageheight{8.75truein}
\pagewidth{6.5truein}
\NoBlackBoxes
\loadbold
%\magnification=\magstep1
\head{NOTE 94}\endhead In this note we summarize what is known
about the relationships between possible definitions of ``finite''.
\par \iput{definitions of finite}
Several authors have studied this topic they include \ac{Diel}
\cite{1974}, \ac{Howard/Yorke} \cite{1989}, \ac{Levy} \cite{1958},
\ac{Spi\u siak} \cite{1993}, \ac{Spi\u siak/Vojt\'a\u s} \cite{1988},
\ac{Tarski} \cite{1938b} and \cite{1954a}, \ac{Truss} \cite{1974a} and
\ac{Hickman} \cite{1972}. The first eight definitions and
their names are due to \ac{Tarski} \cite{1954a}
\par\medskip
\definition{Definition.} A set $A$ is said to be
\par
\item{} {\it 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$.)
\item{} {\it Dedekind finite} if it is not equivalent to a proper
subset of itself. Otherwise, $A$ is {\it Dedekind infinite}.
\iput{Dedekind finite}
\item{} {\it $T$-finite} if every non-empty, monotone $X\subseteq
\Cal P(A)$ has a $\subseteq$-maximal element. \iput{$T$-finite}
\item{}{\it 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.)
\par
\item{}{\it Ia-finite} if it is not the union of two disjoint sets
neither of which is I-finite.
\par
\item{}{\it II-finite} if every non-empty $\subseteq $-monotone family
of subsets of $A$ has a $\subseteq $-maximal element.
\par
\item{}{\it III-finite} if the power set of $A$ is Dedekind finite.
\par
\item{}{\it IV-finite} if $A$ is Dedekind finite.
\item{}{\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|$.
\item{}{\it VII-finite} if $A$ is I-finite or not well orderable.
\enddefinition
In \ac{Tarski} \cite{1954a} and \ac{Levy} \cite{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.
\par
In \ac{Tarski} \cite{1938b} the following definitions are considered:
\par
\definition{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 \}$.\enddefinition
\nopagebreak
In \ac{Howard/Yorke} \cite{1989} the following definition is introduced:
\definition{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.
\enddefinition
It is shown there that IV $\rightarrow D$ and $D \rightarrow $ VII.
Further, V $ \not\rightarrow D$ and $D \not\rightarrow $ VI.
\par\smallskip
In \ac{Truss} \cite{1974a} the following classes of Dedekind finite
cardinals are considered:
\definition{Definition}
\item{}$\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 Ia-finite.)
\item{}$\Delta_{2} = \{|A|$ : any linearly ordered partition of $A$ is
finite $\}$. ($\Delta_{2}$-finite is equivalent to II-finite.)
\item{}$\Delta_{3} = \{|A|$ : any linearly ordered subset of
$A$ is finite $\}$.
\item{}$\Delta_{4} = \{x: \neg (\aleph _{0} \le ^{*} x) \}$.
($\Delta_{4}$-finite is equivalent to III-finite.)
\item{}$\Delta_{5} = \{x: \neg (x + 1 \le ^{*} x) \}$.
\enddefinition
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
$$
\hbox{ZF} + \omega = \Delta _{1} = \Delta _{2} = \Delta _{4} \neq
\Delta _{5} \neq \hbox{ IV-finite }+ \Delta _{2} = \Delta _{3}
\neq \hbox{
IV-finite}
$$
is consistent.
\par
In \ac{Diel} \cite{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.
\par \iput{almost finite} \iput{strongly Dedekind finite}
Finally in \ac{Howard/Spi\u siak} \cite{1994}, \ac{Spi\u siak} \cite{1993}
and \ac{Spi\u siak/Vojt\'a\u s} \cite{1988} the
following forms are considered:
\definition{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.
\enddefinition
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.
\par
In addition, in \ac{Howard/Yorke} \cite{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 form [9
B], $E(IV,V)$ is form [3 E], $E(V,VI)$ is form [1 AH], $E(VI,VII)$ is
form [1 AI], $E(V'',III)$ is form 276 and $E(D,VII)$ is form 277.
\par
We note that $E(I,D)$ which is equivalent to ``{\it every infinite set is
decomposable}'' is
equivalent to the axiom of choice since it is form CN 4F in
\ac{H.~Rubin/J.~Rubin} \cite{1985}, p. 139.
\par\medskip
The relationships between the various definitions of
finite are summarized in the following diagram:
\par\medskip
{\documentstyle{amsppt}
%%Here we load XY-pic:
\input xy
\xyoption{all}
%%
\document
\centerline{
\xymatrix{%
%
%
%
&\text{I} \ar@{->}[d] \\%
&\text{Ia} \ar@{->}[d] \\%
&\text{II} \ar@{->}[d] \ar@{->}[ddr]\\%
&\text{III} \ar@{->}[d] \ar@{->}[d] \\%
&\text{V}'' \ar@{->}[d] \ar@{->}[dl] & \Delta_3 \ar@{->}[ddl] \\
\text{VI}'' \ar@{->}[ddr] & \Delta_5 \ar@{->}[d] \\%
&\text{IV} \ar@{->}[d] \ar@{->}[dr] \\%
& \text{V} \ar@{->}[d] & D \ar@{->}[ddl]\\%
& \text{VI} \ar@{->}[d] \\%
& \text{VII} \ar@{->}[d] \\%
& \text{VII}'' %
%
%
}}}
\par\medskip
\noindent (In addition VI$''$ $\not\rightarrow $ IV, IV
$\not\rightarrow$ VI$''$, V $\not\rightarrow D$, $D\not
\rightarrow$ VI, and none of the arrows are reversible.)
\par
Also, it was shown by De la Cruz [2001] that $\Delta_3$-finite
and III-finite are independent, neither implies the other in ZF.
Also, he has shown that $V''\implies \Delta_5$. In $\Cal N3$,
Mostowski's linearly ordered model, $\Cal P(A)$, where $A$
is the set of atoms, is Dedekind finite, but can be linearly ordered.
Therefore, $\Cal P(A)$ is III-finite, but not $\Delta_3$-finite.\par
On the other hand, in Fraenkel's Basic Model, $\Cal N1$, the
set of all finite subsets of A, is III-infinite,
but it contains no infinite linearly ordered subset. For suppose
that $L$ is such an infinite linearly ordered subset and $E$ is a
support for $L$ and its linear order $R$. Then, there exists
$n\in\omega$ such that $L'=\{x\in L: |x|=n\}$ is infinite; otherwise
we can well order $L$ by
$$ x