Kardinalität

Aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Die Menge aller platonischen Körper hat 5 Elemente. Also .

In der Mathematik ist die Kardinalität einer Menge ein Maß für die "Anzahl der Elemente " der Menge. Zum Beispiel enthält die Menge 3 Elemente und hat daher eine Kardinalität von 3. Ab dem späten 19. Jahrhundert wurde dieses Konzept auf unendliche Mengen verallgemeinert , wodurch man zwischen den verschiedenen Arten der Unendlichkeit unterscheiden und mit ihnen rechnen kann . Es gibt zwei Ansätze zur Kardinalität: einen, der Mengen direkt mit Bijektionen und Injektionen vergleicht , und einen anderen, der Kardinalzahlen verwendet . [1]Die Kardinalität einer Menge wird auch als Größe bezeichnet , wenn keine Verwechslung mit anderen Größenbegriffen [2] möglich ist.

Die Kardinalität einer Menge wird normalerweise mit einem vertikalen Balken auf jeder Seite bezeichnet. [3] [4] Dies ist die gleiche Notation wie der Absolutwert , und die Bedeutung hängt vom Kontext ab . Die Kardinalität eines Satzes kann alternativ durch bezeichnet , , , oder .

Sätze vergleichen [ bearbeiten ]

Bijektive Funktion von N bis zur Menge E von geraden Zahlen . Obwohl E eine richtige Teilmenge von N ist , haben beide Mengen die gleiche Kardinalität.
N hat nicht die gleiche Kardinalität wie seine Potenzmenge P ( N ): Für jede Funktion f von N bis P ( N ) stimmt die Menge T = { nN : nf ( n )} nicht mit jeder Menge in der Bereich von f , daher kann f nicht surjektiv sein. Das Bild zeigt ein Beispiel f und das entsprechende T ; rot : nf ( n ) \T , blau : nT \ f ( n ).

Während die Kardinalität einer endlichen Menge nur die Anzahl ihrer Elemente ist, beginnt die Erweiterung des Begriffs auf unendliche Mengen normalerweise mit der Definition des Begriffs des Vergleichs beliebiger Mengen (von denen einige möglicherweise unendlich sind).

Definition 1: | A | = | B | [ bearbeiten ]

Zwei Sätze A und B haben die gleiche Mächtigkeit , wenn es existiert eine Bijektion (aka, eine Eins-zu-Eins - Entsprechung) von A zu B , [5] Das heißt, eine Funktion von A bis B , die sowohl ist injektiv und surjektiv . Solche Sätze werden gesagt sein äquipotent , äquipollent oder gleichzahlig . Diese Beziehung kann auch als AB oder A ~ B bezeichnet werden .
Zum Beispiel hat die Menge E = {0, 2, 4, 6, ...} von nicht negativen geraden Zahlen die gleiche Kardinalität wie die Menge N = {0, 1, 2, 3, ...} von natürlich Zahlen , da die Funktion f ( n ) = 2 n eine Bijektion von N nach E ist (siehe Bild).

Definition 2: | A | ≤ | B | [ bearbeiten ]

A hat eine Kardinalität, die kleiner oder gleich der Kardinalität von B ist , wenn eine Injektionsfunktion von A nach B besteht .

Definition 3: | A | <| B | [ bearbeiten ]

A hat eine Kardinalität, die streng geringer ist als die Kardinalität von B , wenn es eine injizierende Funktion, aber keine bijektive Funktion von A nach B gibt .
Zum Beispiel hat die Menge N aller natürlichen Zahlen eine Kardinalität, die streng geringer ist als ihre Potenzmenge P ( N ), weil g ( n ) = { n } eine injektive Funktion von N nach P ( N ) ist, und es kann gezeigt werden, dass Keine Funktion von N nach P ( N ) kann bijektiv sein (siehe Bild). Durch ein ähnliches Argument hat N eine Kardinalität, die streng geringer ist als die Kardinalität der Menge R aller reellen Zahlen . Für Beweise siehe Cantors diagonales Argumentoder Cantors erster Unzählbarkeitsnachweis .

Wenn | A | ≤ | B | und | B | ≤ | A |, dann | A | = | B | (eine Tatsache, die als Schröder-Bernstein-Theorem bekannt ist ). Das Axiom der Wahl entspricht der Aussage, dass | A | ≤ | B | oder | B | ≤ | A | für jedes A , B . [6] [7]

Kardinalzahlen [ bearbeiten ]

Im obigen Abschnitt wurde die "Kardinalität" einer Menge funktional definiert. Mit anderen Worten, es wurde nicht als ein bestimmtes Objekt selbst definiert. Ein solches Objekt kann jedoch wie folgt definiert werden.

Die Beziehung der gleichen Kardinalität wird als Äquinumerosität bezeichnet , und dies ist eine Äquivalenzbeziehung für die Klasse aller Mengen. Die Äquivalenzklasse einer Menge A unter dieser Beziehung besteht also aus all jenen Mengen, die die gleiche Kardinalität wie A haben . Es gibt zwei Möglichkeiten, die "Kardinalität einer Menge" zu definieren:

  1. Die Kardinalität einer Menge A wird als ihre Äquivalenzklasse unter Äquinumerosität definiert.
  2. Für jede Äquivalenzklasse wird ein repräsentativer Satz festgelegt. Die häufigste Wahl ist die anfängliche Ordnungszahl in dieser Klasse . Dies wird normalerweise als Definition der Kardinalzahl in der axiomatischen Mengenlehre verwendet .

Unter der Annahme des Axioms der Wahl werden die Kardinalitäten der unendlichen Mengen bezeichnet

Für jede Ordnungs , ist die kleinste Kardinalzahl größer .

Die Kardinalität der natürlichen Zahlen wird mit aleph-null ( ) bezeichnet, während die Kardinalität der reellen Zahlen mit " " (ein Fraktur-Skript in Kleinbuchstaben "c") bezeichnet wird und auch als Kardinalität des Kontinuums bezeichnet wird . [3] Cantor zeigte anhand des diagonalen Arguments , dass . Wir können das zeigen , dies ist auch die Kardinalität der Menge aller Teilmengen der natürlichen Zahlen.

Die Kontinuumshypothese besagt, dass dh die kleinste Kardinalzahl größer ist als , dh es gibt keine Menge, deren Kardinalität streng zwischen der der ganzen Zahlen und der der reellen Zahlen liegt. Die Kontinuumshypothese ist unabhängig von ZFC , einer Standardaxiomatisierung der Mengenlehre; Das heißt, es ist unmöglich, die Kontinuumshypothese oder ihre Negation von ZFC zu beweisen - vorausgesetzt, ZFC ist konsistent. Weitere Einzelheiten finden Sie unter § Kardinalität des Kontinuums unten. [8] [9] [10]

Endliche, zählbare und unzählbare Mengen [ Bearbeiten ]

Wenn das Axiom der Wahl gilt, gilt das Gesetz der Trichotomie für die Kardinalität. Somit können wir folgende Definitionen vornehmen:

  • Jede Menge X mit einer Kardinalität, die kleiner als die der natürlichen Zahlen ist , oder | X  | <| N  | soll eine endliche Menge sein .
  • Jede Menge X , die dieselbe Kardinalität wie die Menge der natürlichen Zahlen hat, oder | X  | = | N  | = , soll eine zählbar unendliche Menge sein. [5]
  • Jede Menge X mit einer Kardinalität, die größer als die der natürlichen Zahlen ist, oder | X  | > | N  | zum Beispiel | R  | = > | N  | soll unzählig sein .

Unendliche Mengen [ Bearbeiten ]

Unsere Intuition aus endlichen Mengen bricht zusammen, wenn wir mit unendlichen Mengen umgehen . Im späten neunzehnten Jahrhundert lehnten Georg Cantor , Gottlob Frege , Richard Dedekind und andere die Ansicht ab, dass das Ganze nicht die gleiche Größe wie das Teil haben könne. [11] [ Bearbeiten ] Ein Beispiel hierfür ist Hilberts Hotel . In der Tat definierte Dedekind eine unendliche Menge als eine, die in eine Eins-zu-Eins-Entsprechung mit einer strengen Teilmenge gestellt werden kann (dh dieselbe Größe im Sinne von Cantor hat); Dieser Begriff der Unendlichkeit wird Dedekind unendlich genannt. Cantor introduced the cardinal numbers, and showed—according to his bijection-based definition of size—that some infinite sets are greater than others. The smallest infinite cardinality is that of the natural numbers ().

Cardinality of the continuum[edit]

One of Cantor's most important results was that the cardinality of the continuum () is greater than that of the natural numbers (); that is, there are more real numbers R than natural numbers N. Namely, Cantor showed that (see Beth one) satisfies:

(see Cantor's diagonal argument or Cantor's first uncountability proof).

The continuum hypothesis states that there is no cardinal number between the cardinality of the reals and the cardinality of the natural numbers, that is,

However, this hypothesis can neither be proved nor disproved within the widely accepted ZFC axiomatic set theory, if ZFC is consistent.

Cardinal arithmetic can be used to show not only that the number of points in a real number line is equal to the number of points in any segment of that line, but that this is equal to the number of points on a plane and, indeed, in any finite-dimensional space. These results are highly counterintuitive, because they imply that there exist proper subsets and proper supersets of an infinite set S that have the same size as S, although S contains elements that do not belong to its subsets, and the supersets of S contain elements that are not included in it.

The first of these results is apparent by considering, for instance, the tangent function, which provides a one-to-one correspondence between the interval (−½π, ½π) and R (see also Hilbert's paradox of the Grand Hotel).

The second result was first demonstrated by Cantor in 1878, but it became more apparent in 1890, when Giuseppe Peano introduced the space-filling curves, curved lines that twist and turn enough to fill the whole of any square, or cube, or hypercube, or finite-dimensional space. These curves are not a direct proof that a line has the same number of points as a finite-dimensional space, but they can be used to obtain such a proof.

Cantor also showed that sets with cardinality strictly greater than exist (see his generalized diagonal argument and theorem). They include, for instance:

  • the set of all subsets of R, i.e., the power set of R, written P(R) or 2R
  • the set RR of all functions from R to R

Both have cardinality

(see Beth two).

The cardinal equalities and can be demonstrated using cardinal arithmetic:

Examples and properties[edit]

  • If X = {a, b, c} and Y = {apples, oranges, peaches}, then | X | = | Y | because { (a, apples), (b, oranges), (c, peaches)} is a bijection between the sets X and Y. The cardinality of each of X and Y is 3.
  • If | X | ≤ | Y |, then there exists Z such that | X | = | Z | and ZY.
  • If | X | ≤ | Y | and | Y | ≤ | X |, then | X | = | Y |. This holds even for infinite cardinals, and is known as Cantor–Bernstein–Schroeder theorem.
  • Sets with cardinality of the continuum include the set of all real numbers, the set of all irrational numbers and the interval .

Union and intersection[edit]

If A and B are disjoint sets, then

From this, one can show that in general, the cardinalities of unions and intersections are related by the following equation:[12]

See also[edit]

  • Aleph number
  • Beth number
  • Cantor's paradox
  • Cantor's theorem
  • Countable set
  • Counting
  • Ordinality
  • Pigeonhole principle

References[edit]

  1. ^ Weisstein, Eric W. "Cardinal Number". MathWorld.
  2. ^ Such as length and area in geometry. – A line of finite length is a set of points that has infinite cardinality.
  3. ^ a b "Comprehensive List of Set Theory Symbols". Math Vault. 2020-04-11. Retrieved 2020-08-23.
  4. ^ "Cardinality | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2020-08-23.
  5. ^ a b "Infinite Sets and Cardinality". Mathematics LibreTexts. 2019-12-05. Retrieved 2020-08-23.
  6. ^ Friedrich M. Hartogs (1915), Felix Klein; Walther von Dyck; David Hilbert; Otto Blumenthal (eds.), "Über das Problem der Wohlordnung", Mathematische Annalen, Leipzig: B. G. Teubner, 76 (4): 438–443, doi:10.1007/bf01458215, ISSN 0025-5831
  7. ^ Felix Hausdorff (2002), Egbert Brieskorn; Srishti D. Chatterji; et al. (eds.), Grundzüge der Mengenlehre (1. ed.), Berlin/Heidelberg: Springer, p. 587, ISBN 3-540-42224-2 - Original edition (1914)
  8. ^ Cohen, Paul J. (December 15, 1963). "The Independence of the Continuum Hypothesis". Proceedings of the National Academy of Sciences of the United States of America. 50 (6): 1143–1148. doi:10.1073/pnas.50.6.1143. JSTOR 71858. PMC 221287. PMID 16578557.
  9. ^ Cohen, Paul J. (January 15, 1964). "The Independence of the Continuum Hypothesis, II". Proceedings of the National Academy of Sciences of the United States of America. 51 (1): 105–110. doi:10.1073/pnas.51.1.105. JSTOR 72252. PMC 300611. PMID 16591132.
  10. ^ Penrose, R (2005), The Road to Reality: A Complete guide to the Laws of the Universe, Vintage Books, ISBN 0-09-944068-7
  11. ^ Georg Cantor (1887), "Mitteilungen zur Lehre vom Transfiniten", Zeitschrift für Philosophie und philosophische Kritik, 91: 81–125
    Reprinted in: Georg Cantor (1932), Adolf Fraenkel (Lebenslauf); Ernst Zermelo (eds.), Gesammelte Abhandlungen mathematischen und philosophischen Inhalts, Berlin: Springer, pp. 378–439 Here: p.413 bottom
  12. ^ Applied Abstract Algebra, K.H. Kim, F.W. Roush, Ellis Horwood Series, 1983, ISBN 0-85312-612-7 (student edition), ISBN 0-85312-563-5 (library edition)