Finite Set - Necessary and Sufficient Conditions For Finiteness

Necessary and Sufficient Conditions For Finiteness

In Zermelo–Fraenkel set theory (ZF), the following conditions are all equivalent:

1. S is a finite set. That is, S can be placed into a one-to-one correspondence with the set of those natural numbers less than some specific natural number.
2. (Kazimierz Kuratowski) S has all properties which can be proved by mathematical induction beginning with the empty set and adding one new element at a time. (See the section on foundational issues for the set-theoretical formulation of Kuratowski finiteness.)
3. (Paul Stäckel) S can be given a total ordering which is well-ordered both forwards and backwards. That is, every non-empty subset of S has both a least and a greatest element in the subset.
4. Every one-to-one function from P(P(S)) into itself is onto. That is, the powerset of the powerset of S is Dedekind-finite (see below).
5. Every surjective function from P(P(S)) onto itself is one-to-one.
6. (Alfred Tarski) Every non-empty family of subsets of S has a minimal element with respect to inclusion.
7. S can be well-ordered and any two well-orderings on it are order isomorphic. In other words, the well-orderings on S have exactly one order type.

If the axiom of choice is also assumed (the axiom of countable choice is sufficient), then the following conditions are all equivalent:

1. S is a finite set.
2. (Richard Dedekind) Every one-to-one function from S into itself is onto.
3. Every surjective function from S onto itself is one-to-one.
4. S is empty or every partial ordering of S contains a maximal element.