Cardinality

From Example Problems
Jump to navigation Jump to search

In mathematics, the cardinality of a set is a measure of the "number of elements of the set". There are two approaches to cardinality – one which compares sets directly using bijections, injections, and surjections, and another which uses cardinal numbers.

Comparing sets

We say that two sets A and B have the same cardinality if there exists a bijection, i.e. a 1-1 and onto function, from A to B. For example, the set E = {2, 4, 6, ...} of positive even numbers has the same cardinality as the set N = {1, 2, 3, ...} of natural numbers, since the function f(n) = 2n is a bijection from N to E.

We say that a set A has cardinality greater than or equal to the cardinality of B (and B has cardinality less than or equal to the cardinality of A) if there exists a 1-1 function from B into A. We say that A has cardinality strictly greater than the cardinality of B if A has cardinality greater than or equal to the cardinality of B, but A and B do not have the same cardinality, i.e. if there is a 1-1 function from B to A but no 1-1 and onto function from A to B. For example, the set R of all real numbers has cardinality strictly greater than the cardinality of the set N of all natural numbers, because the inclusion map i : NR is 1-1, but it can be shown that there does not exist a 1-1 and onto function from N to R.

Countable and uncountable sets

Assuming the axiom of choice holds, the law of trichotomy holds for cardinality, so we have the following definitions.

Cardinal numbers

Main article: Cardinal number

Note that, up until this point, we have only defined the term "cardinality" in a strictly functional role: we have not actually defined the "cardinality" of a set as a specified object itself. We now outline such an approach.

The relation of having the same cardinality is called equinumerosity, and this is an equivalence relation on the class of all sets. The equivalence class of a set A under this relation then consists of all those sets which have the same cardinality as A. There are then two main approaches to the definition of "cardinality of a set":

  1. The cardinality of a set A is defined as its equivalence class under equinumerosity.
  2. A particular class of representatives of the equivalence classes is specified. The most common choice is the Von Neumann cardinal assignment. This is usually taken as the definition of cardinal number in axiomatic set theory.

Cardinality of set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} is denoted Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |S|} . Cardinality of its power set is denoted Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{|S|}} .

Cardinalities of the infinite sets are denoted Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_0 < \aleph_1 < \aleph_2 < ... } (for each ordinal Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_{\alpha+1}} is the first cardinality greater than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_\alpha} ).

The cardinality of the natural numbers is denoted aleph-null (Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\aleph_0}} ), while the cardinality of the real numbers is denoted Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c}} . It can be shown that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c} = 2^{\aleph_0} > {\aleph_0}} . (see: Cantor's diagonal argument). The continuum hypothesis states that there is no cardinal number between the cardinality of the reals and the cardinality of the natural numbers, and so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{c} = \aleph_1} .

Examples and other properties

  • If, for instance, set X is defined as X = {a, b, c}, and set Y is defined as Y = {apples, oranges, peaches}, then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |X| = |Y|} because they both have three elements.
  • If for two sets X and Y, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |X|}Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |Y|} , then there exists a set Z as a subset of Y such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |X| = |Z|} .

Such a property allows for the comparison of how many elements are contained in two or more sets without resorting to an intermediate set (viz. the natural numbers).

  • Within the realm of uncountable sets, there exists a class of sets Y such that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |Y| = c} (cardinality of set of real numbers). Such sets are said to have "cardinality of the continuum."
  • It can be proven that there exists no set X such that for any set Y, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |Y|}Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |X|} .

Proof. Assume there exists such a set, call it X. Then let Y be the power set of X, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |Y| = 2^{|X|}} , from which the contradiction Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |Y| > |X|} follows.

See also

fr:Cardinalité is:Fjöldatölur it:Cardinalità nb:Kardinalitet fi:Mahtavuus zh:基数