Finite set

From Wikipedia, the free encyclopedia

In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where <math>n</math> is a natural number. (The value n=0 is allowed; that is, the empty set is finite.) All finite sets are countable <ref>Some authors use "countable" to mean "countably infinite", and thus do not consider finite sets to be countable.</ref>, but not all countable sets are finite.

Equivalently, a set is finite if its cardinality, i.e. the number of its elements, is a natural number. For instance, the set of integers between -15 and 3 (excluding the end points) is finite, since it has 17 elements. The set of all prime numbers is not finite. Infinite sets are sets which are not finite.

A set is called Dedekind finite if there exists no bijection between the set and any of its proper subsets. If the axiom of choice holds, a set is finite if and only if it is Dedekind finite.

1 Closure properties
2 Necessary and sufficient conditions for finiteness
3 Footnotes
4 See also
5 References

[edit] Closure properties

For any elements x, y, the sets {}, {x}, and {x, y} are finite. The union of a finite set of finite sets is finite. The powerset of a finite set is finite. Any subset of a finite set is finite. The set of values of a function when applied to elements of a finite set is finite. The Cartesian product of a finite set of finite sets is finite. However, the set of natural numbers (whose existence is assured by the axiom of infinity) is not finite.

[edit] Necessary and sufficient conditions for finiteness

In ZF, the following conditions are all equivalent:

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.
S has all properties which can be proved by mathematical induction beginning with the empty set and adding one new element at a time.
(Paul Stäckel) S can be given a total ordering which is both well-ordered forwards and backwards. That is, every non-empty subset of S has both a least and a greatest element in the subset.
Every function from P(P(S)) one-to-one into itself is onto. That is, the powerset of the powerset of S is Dedekind-finite (see below).
Every function from P(P(S)) onto itself is one-to-one.
(Alfred Tarski) Every non-empty family of subsets of S has a minimal element with respect to inclusion.
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.