For example, the set of all positive integers is infinite: Finite sets are particularly important in combinatorics, the mathematical study of counting.
Many arguments involving finite sets rely on the pigeonhole principle, which states that there cannot exist an injective function from a larger finite set to a smaller finite set.
is called finite if there exists a bijection for some natural number
If a set is finite, its elements may be written — in many ways — in a sequence: In combinatorics, a finite set with
Any proper subset of a finite set
As a consequence, there cannot exist a bijection between a finite set S and a proper subset of S. Any set with this property is called Dedekind-finite.
The axiom of countable choice, a weak version of the axiom of choice, is sufficient to prove this equivalence.
Similarly, any surjection between two finite sets of the same cardinality is also an injection.
In Zermelo–Fraenkel set theory without the axiom of choice (ZF), the following conditions are all equivalent:[1] If the axiom of choice is also assumed (the axiom of countable choice is sufficient),[4] then the following conditions are all equivalent: In ZF set theory without the axiom of choice, the following concepts of finiteness for a set
They are arranged in strictly decreasing order of strength, i.e. if a set
In the absence of the axiom of choice the reverse implications are all unprovable, but if the axiom of choice is assumed then all of these concepts are equivalent.
[5] (Note that none of these definitions need the set of finite ordinal numbers to be defined first; they are all pure "set-theoretic" definitions in terms of the equality and membership relations, not involving ω.)
The forward implications (from strong to weak) are theorems within ZF.
Counter-examples to the reverse implications (from weak to strong) in ZF with urelements are found using model theory.
[7] Most of these finiteness definitions and their names are attributed to Tarski 1954 by Howard & Rubin 1998, p. 278.
However, definitions I, II, III, IV and V were presented in Tarski 1924, pp.
At that time, model theory was not sufficiently advanced to find the counter-examples.
This is not true for V-finite thru VII-finite because they may have countably infinite subsets.