Finite amount

In set theory , a branch of mathematics , a finite set is a set with finitely many elements . Such is the amount, for example

${\displaystyle M\,=\,\{4,6,2,8\}}$

a finite set with four elements. The empty set has no elements according to their definition d. H. is the number of elements, so it is also considered a finite set. The cardinality or cardinality, written for a set , of a finite set, is identified with a natural number (including zero ). For example, one then writes to express that it consists of four elements. ${\displaystyle 0}$ ${\displaystyle |M|}$ ${\displaystyle M}$ ${\displaystyle |M|=4}$ ${\displaystyle M}$

A set that is not finite is called an infinite set .

definition

The bijection indicated by the red arrows shows and thus the finiteness of ${\displaystyle f}$ ${\displaystyle |M|=|N_{4}|}$ ${\displaystyle M}$

A set is called finite if there is a natural number such that a bijection (a one-to-one assignment) ${\displaystyle M}$ ${\displaystyle n}$

${\displaystyle f\colon M\rightarrow N_{n}\quad :=\{m\in \mathbb {N} _{0}\,\mid \,m<n\}\;=\;\{0,1,2,3,\dotsc ,n-1\}}$

between and the set of all natural numbers less than exists. ${\displaystyle M}$ ${\displaystyle N_{n}}$ ${\displaystyle n}$

In particular, the empty set is finite, since a bijection between and the empty set (all natural numbers smaller than , such do not exist) trivially exists. ${\displaystyle \emptyset :=\{\}}$ ${\displaystyle \emptyset }$ ${\displaystyle N_{0}}$ ${\displaystyle 0}$

Such is the amount, for example

${\displaystyle M\,=\,\{4,6,2,8\}}$

finally, as a bijection to the crowd

${\displaystyle N_{4}\,=\,\{0,1,2,3\}}$

exists, see figure on the right.

With this enumerating quantity notation, the order does not matter. Furthermore, an element that is mentioned several times is only included once. So it is for example

${\displaystyle M\,=\,\{4,6,2,8\}\,=\,\{2,4,6,8\}\,=\,\{4,8,6,2,6,8\}\,=\,\{4,8,6,2,6,4,6,4,6,4,6,4,\dotsc \}}$.

For the set of all natural numbers

${\displaystyle \mathbb {N} _{0}=\{0,1,2,3,\dotsc \}}$

if there is no such bijection on a finite set, the set is therefore infinite. ${\displaystyle \mathbb {N} _{0}}$

Fundamental properties of finite sets

• Every subset of a finite set is also finite. ${\displaystyle A}$
• If in particular is a finite set and an arbitrary set, then both the intersection and the difference set are finite sets, because both are subsets of . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\cap B}$ ${\displaystyle A\setminus B}$ ${\displaystyle A}$
• If sets are finite, then their union is also finite. For their mightiness applies . Are and finite and disjoint , so that's how one has . ${\displaystyle A,B}$ ${\displaystyle A\cup B}$
      ${\displaystyle |A\cup B|=|A|+|B|-|A\cap B|}$
  ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\cap B=\emptyset ,}$
      ${\displaystyle |A\cup B|=|A|+|B|=|A\,{\dot {\cup }}\,B|}$
• In general, a union of finitely many finite sets is again a finite set. Their power is given by the principle of inclusion and exclusion .
• Is infinite and finite, so is infinite. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\setminus B}$
• The power set of a finite set has a greater power than the set itself, but is still finite; it applies . ${\displaystyle {\mathcal {P}}(A):=\{U\mid U\subseteq A\}}$ ${\displaystyle A}$ ${\displaystyle |{\mathcal {P}}(A)|=2^{|A|}}$
• The Cartesian product of finite sets is finite. Its power is greater than that of all the factors involved if no factor is empty and at least two factors have a power greater . For finite sets we have . More generally, a Cartesian product of finitely many finite sets is again a finite set. ${\displaystyle A\times B}$ ${\displaystyle 1}$ ${\displaystyle A,B}$ ${\displaystyle |A\times B|=|A|\cdot |B|}$

Dedekind finiteness

Another distinction between finite and infinite sets comes from Dedekind . He defined:

A set is called finite if it is not of equal power to any real subset, otherwise infinite . ${\displaystyle M}$

Today we speak of Dedekind finiteness or Dedekind infinity .

In order to show that every finite set is also Dedekind finite , it suffices to show the following:

1. The empty set is not equal to any real subset .
2. If is not equal to any real subset, then is not equal to any real subset (of itself). ${\displaystyle M}$ ${\displaystyle M\cup \{a\}}$

(Point 1 is clear because the empty set has no real subsets. For point 2, it must be shown that a bijection between the set and a real subset of a bijection between and a real subset can be obtained.) ${\displaystyle f'}$ ${\displaystyle M':=M\cup \{a\}}$ ${\displaystyle U'}$ ${\displaystyle M'}$ ${\displaystyle f}$ ${\displaystyle M}$ ${\displaystyle U}$

Conversely, every Dedekind finite set is also finite, because if it were infinite, one could find a sequence of pairwise different elements with the help of the axiom of choice . The image ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle F:=(a_{0},a_{1},a_{2},\dotsc )=\left(a_{n}\right)_{n\in \mathbb {N} _{0}}}$ ${\displaystyle a_{n}\in A}$

${\displaystyle f\colon A\rightarrow A\setminus \{a_{0}\},\quad a\mapsto {\begin{cases}\\\\\end{cases}}}$	${\displaystyle a_{n+1}}$	For   ${\displaystyle a\in F,}$   ${\displaystyle a_{n}=a}$
	${\displaystyle a}$	For   ${\displaystyle a\not \in F}$

is well-defined , because if there is, then there is a with and this is clear. It shows that it is equal to the real subset and therefore not Dedekind finite - in contradiction to the prerequisite. ${\displaystyle a\in F}$ ${\displaystyle n\in \mathbb {N} _{0}}$ ${\displaystyle a_{n}=a}$ ${\displaystyle A}$ ${\displaystyle A\setminus \{a_{0}\}}$

Hereditary finite sets

A set is said to be hereditary finite if the transitive envelope is finite. This means that not only is finite, but also all elements of are finite sets, and their elements are also finite sets, and so on. ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$

By definition, all hereditary finite sets are finite. The converse is not valid, for example it is a finite set, because it contains the only element , but the element itself is not finite. ${\displaystyle \{\mathbb {N} _{0}\}}$ ${\displaystyle \mathbb {N} _{0}}$ ${\displaystyle \mathbb {N} _{0}}$

In abstract set theory the natural numbers are introduced as hereditary finite sets:

${\displaystyle {\begin{aligned}0&:=\emptyset \\1&:=\{\emptyset \}=\{0\}\\2&:=\{\emptyset ,\{\emptyset \}\}=\{0,1\}\\3&:=\{\emptyset ,\{\emptyset \},\{\emptyset ,\{\emptyset \}\}\,\}=\{0,1,2\}\\&\vdots \\n&:=\{0,1,\dotsc ,n-1\}=N_{n}\end{aligned}}}$

The natural numbers themselves are finite sets, even hereditary finite, and it applies to every natural number , whereby the vertical lines here do not stand for the absolute value function , but for the power. This is the reason why the quantity was chosen instead of in the definition of uniformity in the introduction . The latter would also have been correct, but the choice made fits the definition of natural numbers better, according to which a set has power if it is too even. ${\displaystyle |n|=n}$ ${\displaystyle n}$ ${\displaystyle \{0,1,\dotsc ,n-1\}}$ ${\displaystyle \{1,2,\dotsc ,n\}}$ ${\displaystyle n}$ ${\displaystyle n:=N_{n}}$

Averages, unions, and products of hereditary finite sets are again hereditary finite. The set of all hereditary finite sets is exactly the level of the Von Neumann hierarchy of the Zermelo-Fraenkel set theory . ${\displaystyle V_{\omega }}$

Further finiteness concepts

The finiteness of a set can also be understood in terms of order theory. The concept of Tarski finitude, which goes back to Alfred Tarski , should be mentioned here in particular .

References and comments

1. ↑ There must therefore be a comparison operation that is capable of resp. ascertain. ${\displaystyle \equiv }$ ${\displaystyle 6\equiv 6}$ ${\displaystyle 6\not \equiv 4}$

literature

• Paul R. Halmos : Naive set theory (= modern mathematics in elementary representation. Vol. 6). 5th edition. Vandenhoeck & Ruprecht, Göttingen 1994, ISBN 3-525-40527-8 .
• Oliver Deiser: Introduction to set theory. Georg Cantor's set theory and its axiomatization by Ernst Zermelo . 3rd, corrected edition. Springer, Berlin et al. 2010, ISBN 978-3-642-01444-4 , doi : 10.1007 / 978-3-642-01445-1 .