Cardinality: Encyclopedia - Cardinality

Cardinality

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.

Cardinality - Comparing sets

We say that two sets A and B have the same cardinality if there exists a bijection, i.e. a injective and surjective 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 an injective 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 an injective function from B to A but no bijective 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 : N → R is injective, but it can be shown that there does not exist a bijective function from N to R.

Cardinality - Countable and uncountable sets

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

• Any set with cardinality less than that of the natural numbers is said to be a finite set.
• Any set that has the same cardinality as the set of the natural numbers is said to be a countably infinite set.
• Any set with cardinality greater than that of the natural numbers is said to be uncountable.

Cardinality - Cardinal numbers

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 S is denoted | S | . Cardinality of its power set is denoted 2 ^{| S |} .

Cardinalities of the infinite sets are denoted (for each ordinal α, is the first cardinality greater than ).

The cardinality of the natural numbers is denoted aleph-null (), while the cardinality of the real numbers is denoted . It can be shown that . (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 .

Cardinality - 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 | X | = | Y | because they both have three elements.

• If for two sets X and Y, | X | ≤ | Y | , then there exists a set Z as a subset of Y such that | 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 | 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, | Y | ≤ | X | .

Proof. Assume there exists such a set, call it X. Then let Y be the power set of X, | Y | = 2 ^{| X |} , from which the contradiction | Y | > | X | follows.

See also

• Cardinal number
• Continuum hypothesis
• Aleph number

Category: Set theory

Adapted from the Wikipedia article "Cardinality", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki