Power (mathematics)

The set of all member states of the European Union comprised 28 states in 2020. This means that their thickness was 28 ( ). ${\displaystyle E}$ ${\displaystyle |E|}$ ${\displaystyle |E|=28}$

In the mathematics used to from the set theory of Georg Cantor derived concept of thickness or cardinality to the for finite sets used term to generalize "number of elements of a set" on infinite sets.

For finite sets, the cardinality is equal to the number of elements in the set, which is a natural number including zero. For infinite sets, you need some preliminary work to characterize their thicknesses. The definitions and conclusions made in the following are also valid in the case of finite sets.

Cardinality for finite sets

For a finite set , the cardinality denotes the number of elements of . It records the thickness of through or alternatively with advanced standing double cross : . ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle |X|}$ ${\displaystyle \#X}$

Examples:

${\displaystyle A=\{1,3,7,21\}\Rightarrow |A|=4}$

${\displaystyle B=\{{\mbox{Tetraeder, Hexaeder, Oktaeder, Dodekaeder, Ikosaeder}}\}\Rightarrow |B|=5}$

${\displaystyle C=\{{\mbox{rot, gelb, blau, orange, violett, schwarz}}\}\Rightarrow |C|=6}$

The power set of a finite set has exactly elements: The choice of a subset corresponds to the independent choice between the two possibilities, whether a certain element of should be in the subset or not. ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle X}$ ${\displaystyle 2^{|X|}}$ ${\displaystyle |X|}$ ${\displaystyle X}$

Equality, mightiness

The comparison of the thickness of two sets

First one defines the concept of the equality of two arbitrary sets and : ${\displaystyle A}$ ${\displaystyle B}$

A set is called equal (in Cantor : equivalent ) to a set if there is a bijection . Then you write or . Uniformity is an equivalence relation on the class of all sets whose equivalence classes (except for the empty set ) are real classes. For more details see below ( §Cardinal Numbers ) and Cardinal Numbers §Definition . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle f\colon A\to B}$ ${\displaystyle |A|=|B|}$ ${\displaystyle A\sim B}$ ${\displaystyle \sim }$

If is equal to and a bijection between and , then the inverse function of a bijection is also equal to . Finite sets are of equal power if and only if they have the same number of elements. Infinite sets are sets that have real subsets of equal power. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle f}$ ${\displaystyle B}$ ${\displaystyle A}$

A set that is equal to the infinite set of natural numbers or a subset of them, which can be “counted” with natural numbers (including 0), is called a countable set . ${\displaystyle \mathbb {N} }$

Sometimes one understands countable only in the sense of countable infinite (= equal to ) and then instead of countable in the sense of the definition introduced above, one speaks of at most countable , which makes the formulation of many proofs somewhat easier and more in line with German usage. ${\displaystyle \mathbb {N} }$

Special results:

1. Powerful DC are: , and (the amounts of the natural, the whole and rational numbers). ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {Q} }$
2. : Equipotent are , , and , wherein the Cantor set is. ${\displaystyle \mathbb {R} }$ ${\displaystyle \left]0,1\right[}$ ${\displaystyle C}$ ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ ${\displaystyle C}$
3. The set of real numbers is more powerful than (i.e. uncountable ). ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {N} }$

See also : Cantor's first diagonal argument  and Cantor's second diagonal argument

Cardinal numbers

Since one can easily show that the uniformity of sets is an equivalence relation , the following definition makes sense:

The equivalence classes of the sets with respect to the relation of equality are called cardinals .

For technical reasons, however, one has to find a suitable system of representatives: By showing that every set is equal to a well-ordered set (this is the statement of the well -ordered set ), one can equate every cardinal number with the smallest ordinal number that is equal to it.

Aleph ( ) is the first letter of the Hebrew alphabet , it is used with an index to denote cardinal numbers of infinite sets, see Aleph function . ${\displaystyle \aleph }$

If a set A is in the equivalence class (= cardinal number) , then we say that A has the cardinality . One then writes: ${\displaystyle \aleph _{i}}$ ${\displaystyle \aleph _{i}}$

${\displaystyle |A|=\aleph _{i}}$.

The cardinal number of a finite set with n elements is set equal to the natural number n .

One can now ask whether all infinite sets are equal to each other - in that case all infinite sets would be countable. However, it turns out that there are infinite sets that are not equal to each other, for example the set of natural numbers is not equal to the set of real numbers . This can be shown, for example, with the so-called “Cantor diagonal proof” , see the article uncountable .

It will be shown below that there are infinitely many different cardinal numbers. Cantor himself showed with Cantor's first antinomy that the cardinal numbers form a real class .

Comparison of thickness

In order to be able to compare the thicknesses of unequal sets, one determines when a set should be more powerful than a set : ${\displaystyle B}$ ${\displaystyle A}$

• If there is a bijection of onto a subset of , then at most is called equal to . Then you write . ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle |A|\leq |B|}$
• If there is a bijection from onto a subset of , but no bijection from to exists, then is called less powerful than and more powerful than . Then you write . Obviously, if and only if is but not . ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle |A|<|B|}$ ${\displaystyle |A|<|B|}$ ${\displaystyle |A|\leq |B|}$ ${\displaystyle |A|=|B|}$

But now the question arises as to the comparability of any two sets, i.e. whether the mere property of being a set implies such a possibility of comparison. Indeed, for any two sets one can show in general (using the axiom of choice ):

• Are and quantities, then or ( comparability principle ) applies . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle |A|\leq |B|}$ ${\displaystyle |B|\leq |A|}$

Furthermore, one can show that every countable set is either finite or of equal power . Furthermore, one can show that every infinite set contains a subset that is too equal. ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} }$

Thus the cardinality of is the smallest infinite cardinal number. They are called : ${\displaystyle \mathbb {N} }$ ${\displaystyle \aleph _{0}}$

${\displaystyle \aleph _{0}:=|\mathbb {N} |}$.

The continuum hypothesis (CH) states that there is no set that is more powerful than but less powerful than . However, as the name suggests, this is not a sentence in the sense that it can be proven. Neither the continuum hypothesis nor its negation can be derived from the usual axiom systems, for example the Zermelo-Fraenkel set theory with axiom of choice. So the continuum hypothesis says that the second smallest is infinite cardinal number . ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle |\mathbb {R} |=|{\mathcal {P}}(\mathbb {N} )|=2^{\aleph _{0}}}$ ${\displaystyle \aleph _{1}}$

Total order of powers

When looking naively at the notation, one could assume that for sets and with and always applies. That this is actually the case is indicated by the following sentence: ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle |A|\leq |B|}$ ${\displaystyle |B|\leq |A|}$ ${\displaystyle |A|=|B|}$

Cantor-Bernstein-Schröder theorem : Is at most equal to and at most equal to , then and are equal. ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle B}$

Let us summarize some properties of the thicknesses:

• It always applies (take identity as a bijection). ${\displaystyle |A|=|A|}$
• Out and follows . ${\displaystyle |A|\leq |B|}$ ${\displaystyle |B|\leq |A|}$ ${\displaystyle |A|=|B|}$
• From and follows (immediately follows from the definition). ${\displaystyle |A|\leq |B|}$ ${\displaystyle |B|\leq |C|}$ ${\displaystyle |A|\leq |C|}$
• For two sets and we always have or (which is equivalent to the axiom of choice ). ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle |A|\leq |B|}$ ${\displaystyle |B|\leq |A|}$

This shows that the cardinal numbers are totally ordered .

Calculation rules for finite cardinalities

Let there be finite sets as well . Then the following rules apply: ${\displaystyle M,N}$ ${\displaystyle N_{1},\ldots ,N_{k}}$

• Bijection or isomorphism rule can be mapped bijectively on .
  ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle \Leftrightarrow }$ ${\displaystyle |M|=|N|}$
• Sum rule applies in general . Another generalization of the sum rule to finitely many finite sets is the principle of inclusion and exclusion .
  ${\displaystyle M\cap N=\emptyset \Leftrightarrow |M\cup N|=|M|+|N|}$
  ${\displaystyle |M\cup N|+|M\cap N|=|M|+|N|}$
  
• Difference rule
  ${\displaystyle M\subseteq N\Leftrightarrow |N\setminus M|=|N|-|M|}$
• Product rule
  ${\displaystyle |M\times N|=|M|\cdot |N|}$
• Quotient rule
  is and holds , then it follows or ${\displaystyle M=N_{1}\;\;\!\!{\dot {\cup }}\;\;\!\!\!\cdots \;\;\!\!\!{\dot {\cup }}\;\;\!\!N_{k}}$ ${\displaystyle \forall i:|N_{i}|=n>0}$ ${\displaystyle k={\tfrac {|M|}{n}}}$ ${\displaystyle |M|=k\cdot n}$
• Subadditivity of sets If the disjoint pairs are, the equality holds: . This means that for disjoint sets, the number of elements in the union of the sets is equal to the sum of the individual numbers of elements in each of these sets.
  ${\displaystyle {\Big |}\bigcup _{i=1}^{k}N_{i}{\Big |}\leq \sum _{i=1}^{k}|N_{i}|}$
  ${\displaystyle N_{i}}$ ${\displaystyle \textstyle |\bigcup _{i=1}^{k}N_{i}|=\sum _{i=1}^{k}|N_{i}|}$
  ${\displaystyle N_{i}}$
• Power rule
  Denotes the set of all mappings . ${\displaystyle N^{M}}$ ${\displaystyle f\colon M\to N}$ ${\displaystyle |N^{M}|=|N|^{|M|}}$

Examples

${\displaystyle M=\{1,2,3\}}$and . Then ${\displaystyle N=\{1,3,5,7\}}$

• there is no bijective mapping between and , ${\displaystyle M}$ ${\displaystyle N}$
• is , ${\displaystyle |M\cup N|=|\{1,2,3,5,7\}|=5}$
• the power of the difference cannot be determined with the above sentence,
• is the thickness of the Cartesian product . ${\displaystyle |M|\cdot |N|=|\{(1,1);(1,3);\ldots \}|=12}$

In another example, let and . Then ${\displaystyle M=\{1,2,3,4\}}$ ${\displaystyle N_{1}=\{1\},N_{2}=\{2\},N_{3}=\{3\},N_{4}=\{4\},N=\{1,2,3,4\}}$

• exist bijective mappings (identical mappings) between the two sets and , ${\displaystyle M}$ ${\displaystyle N}$
• is , since the two sets are identical, ${\displaystyle |M\cup N|=|N|=4}$
• is a subset of , and thus applies: , ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle |N\setminus M|=|N|-|M|=0}$
• the thickness of the Cartesian product is and ${\displaystyle 16}$
• because we receive or ${\displaystyle n=|N_{1}|=\dots =|N_{4}|=1}$ ${\displaystyle k=4}$ ${\displaystyle |M|=4\cdot 1=4}$

Thickness of the power set, greatest thinness

Cantor's theorem answers the question about the greatest power of a set :

For any set the power set is more powerful than . ${\displaystyle A}$ ${\displaystyle {\mathcal {P}}(A)}$ ${\displaystyle A}$

There is also the following notation for the thickness of : ${\displaystyle {\mathcal {P}}(A)}$

${\displaystyle |{\mathcal {P}}(A)|=2^{|A|}}$

It should be noted that the corresponding expression for infinite ordinal numbers returns a different value, and e.g. B. cannot be regarded as a “limit value” of a sequence . ${\displaystyle 2^{|\mathbb {N} |}}$ ${\displaystyle (2^{n})}$

If one now determines the cardinalities of the power sets of power sets of power sets, etc., then one sees that there are infinitely many cardinals and that no most powerful set exists.

Individual evidence

1. ↑ Dieter Klaua : Set theory . De Gruyter textbook. de Gruyter, Berlin, New York 1979, ISBN 3-11-007726-4 . Here p. 75, definition 16, part 1, definition 16, part 2
2. ↑ H. König: Design and structural theory of controls for production facilities (=  ISW research and practice . Volume 13 ). Springer-Verlag, Berlin / Heidelberg 1976, ISBN 3-540-07669-7 , pp. 15-17 , doi : 10.1007 / 978-3-642-81027-5_1 . Here: page 21
3. ↑ Тhοmas Stеιnfеld: equal thickness to Mathpedia

literature

• Erich Kamke : set theory (=  Sammlung Goschen . No. 999 ). De Gruyter, Berlin 1928.
• Oliver Deiser: Introduction to set theory: Georg Cantor's set theory and its axiomatization by Ernst Zermelo . 3. Edition. Springer, Berlin / Heidelberg 2010, ISBN 978-3-642-01444-4 , doi : 10.1007 / 978-3-642-01445-1 .
• Heinz-Dieter Ebbinghaus : Introduction to set theory. With tasks and solution tips. 4th edition. Spektrum Akademischer Verlag, Heidelberg 2003, ISBN 3-8274-1411-3 .
• Andreas Bartholomé, Josef Rung, Hans Kern: Number theory for beginners: An introduction for schoolchildren, teachers, students and other interested parties. 7th, updated edition. Vieweg + Teubner, Wiesbaden 2010, ISBN 978-3-8348-9650-6 , doi: 10.1007 / 978-3-8348-9650-6 .

Web links

Wikibooks: Math for Non-Freaks: Power of Quantities  - Learning and Teaching Materials