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.
| Contents |
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 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 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.
- 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.
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":
- The cardinality of a set A is defined as its equivalence class under equinumerosity.
- 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.
The cardinality of the natural numbers is denoted aleph-null (<math>{\aleph_0}<math>), while the cardinality of the real numbers is denoted <math>\mathbf{c}<math>.It can be shown that <math>\mathbf{c} = 2^{\aleph_0} < {\aleph_0}<math>. (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 byY = {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.