Cardinality

From Wikipedia, the free encyclopedia

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 and injections, and another which uses cardinal numbers.

Contents 1 Comparing sets 2 Countable and uncountable sets 3 Cardinal numbers 4 Examples and properties 5 See also

[edit] Comparing sets

Two sets A and B have the same cardinality, if there exists a bijection, that is, an 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.

A set A has cardinality greater than or equal to the cardinality of B, if there exists an injective function from B into A. The set 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. In other words, if there is an injective function from B to A, but no bijective function from B to A. 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.

[edit] Countable and uncountable sets

If the axiom of choice holds, the law of trichotomy holds for cardinality. Thus we can make 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.

[edit] Cardinal numbers

Main article: Cardinal number

Above, "cardinality" was defined functionally. That is, the "cardinality" of a set was not defined as a specific object itself. However, such an object can be defined as follows.

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 two ways to define the "cardinality of a set":

1. The cardinality of a set A is defined as its equivalence class under equinumerosity.
2. A representative set is designated for each equivalence class. The most common choice is the initial ordinal in that class. 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 least cardinal number 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, that is, .

[edit] Examples and properties

• If X = {a, b, c} and Y = {apples, oranges, peaches}, then | X | = | Y | , because is a bijection between them. Their cardinality is 3.

• If , then there exists Z such that | X | = | Z | and

• If (cardinality of set of real numbers), then Y is said to have "cardinality of the continuum", and Y is uncountable.

• There is no largest cardinal number. That is, given any set X, there is a set Y such that X < Y. In particular, Y may be taken to be the powerset of X.

[edit] See also

• Cardinal number
• Continuum hypothesis
• Aleph number