BIGpedia - Cardinality - Encyclopedia and Dictionary Online

The cardinality of a set is a property that describes the size of the set by describing it using a cardinal number. Sometimes we refer to this notion in a numerical way, so in the case of finite sets, the cardinality of the set is just the number of elements contained in the set.

Contents

1 Comparing sets

2 Countable and uncountable sets

3 Examples and other properties

4 See also

Comparing sets

When comparing two sets, we say that a set A and a set B have the same cardinality if and only if there exists a bijection, i.e. a one-to-one and onto function, between the two sets. So, for example, the set of even numbers has the same cardinality as the set of natural numbers, since the function f(n) = 2n, is a bijection.

Countable and uncountable sets

Any set that has the same cardinality as the set of the natural numbers is said to be an infinite countable set, if the cardinality of such a set is less than that of the natural numbers then it is a finite set, otherwise the set is uncountable.

The cardinality of the natural numbers is aleph-null ( ${\aleph_0}$ ), while the cardinality of the real numbers is $2^{\aleph_0}$ .

The cardinality of the natural numbers is less than the cardinality of the real numbers (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.

Examples and other properties

If, for instance, set X is defined by X = {a, b, c}, and set Y by Y = {apples, oranges, peaches}, then card X = card Y, they both have three elements.

If for two sets X and Y, card X is less than or equal to card Y, then there exists a set Z as a subset of Y such that card X = card 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 card Y = card R, where R is the 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, card Y ≤ card X.

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