The cardinality of a set is a measure of a set's size, meaning the number of elements in the set. For instance, the set has a cardinality of for the three elements that are in it. The cardinality of a set is denoted by vertical bars, like absolute value signs; for instance, for a set its cardinality is denoted . When is finite, is simply the number of elements in . When is infinite, is represented by a cardinal number.
Two finite sets are considered to be of the same size if they have equal numbers of elements. To formulate this notion of size without reference to the natural numbers, one might declare two finite sets and to have the same cardinality if and only if there exists a bijection . For finite sets, these two definitions are equivalent. A bijection will exist between and only when elements of can be paired in one-to-one correspondence with elements of , which necessarily requires and have the same number of elements.
There is nothing preventing one from making a similar definition for infinite sets:
Two sets and are said to have the same cardinality if there exists a bijection .
This seemingly straightforward definition creates some initially counterintuitive results. For example, note that there is a simple bijection from the set of all integers to the set of even integers, via doubling each integer. More formally, this is the bijection where This means that, in terms of cardinality, the size of the set of all integers is exactly the same as the size of the set of even integers.
Let denote the set of natural numbers.
An infinite set is called countably infinite (or countable) if it has the same cardinality as . In other words, there is a bijection .
An infinite set is called uncountably infinite (or uncountable) if it is not countable. In other words, there exists no bijection .
These definitions suggest that even among the class of infinite sets, there are different "sizes of infinity." In the sense of cardinality, countably infinite sets are "smaller" than uncountably infinite sets. Of course, finite sets are "smaller" than any infinite sets, but the distinction between countable and uncountable gives a way of comparing sizes of infinite sets as well. Below are some examples of countable and uncountable sets.
Let denote the set of integers. Is countable or uncountable?
Consider the following map from
Each integer is mapped to by some natural number, and no integer is mapped to twice. Thus, this is a bijection. We conclude is countable.
Let denote the set of rational numbers. Is countable or uncountable?
A map from can be described simply by a list of rational numbers. If this list contains each rational number at least once, we can remove repeats to obtain a bijection .
For a rational number (in lowest terms), call its height. There are finitely many rational numbers of each height. Hence, if we list all the rationals of height 1, then the rationals of height 2, then the rationals of height 3, etc., we will obtain the desired list of rationals.
Thus, we conclude is countable.
Consider the interval . As a set, is countable or uncountable?
By Cantor's famous diagonal argument, it turns out is uncountable. His argument is a clever proof by contradiction.
Suppose is countable, so that we may write , where each . For each , write (one of) its binary representation(s):
where each .
For each , let , so that if and if . Now, construct a number by writing down its binary representation:
Since differs from in the binary digit, we know for all .
But this means is not in the list , even though . Thus, the list does not include every element of the set , contradicting our assumption of countability!
Cardinality places an equivalence relation on sets, which declares two sets and are equivalent when there exists a bijection . The equivalence classes thus obtained are called cardinal numbers. For a set , let denote its cardinal number.
There is an ordering on the cardinal numbers which declares when there exists an injection . This is actually the Cantor-Bernstein-Schroeder theorem stated as follows:
If and , then .
For finite sets, cardinal numbers may be identified with positive integers. The smallest infinite cardinal is , which represents the equivalence class of . This means that for any infinite set , one has ; that is, for any infinite set, there is an injection .
Cardinal arithmetic is defined as follows:
Assuming the axiom of choice, the formulas for infinite cardinal arithmetic are even simpler, since the axiom of choice implies .