Cardinality

Discussion0

Written by Joe Zeng, Patrick Stevens, Eric B, et al. last updated 6th Oct 2016

Summaries

You can edit these summaries by clicking on them and reorder them by dragging. Pages can have up to 3 summaries.

brief

The cardinality of a set is a formalization of the "number of elements" in the set.

Summary

If is a finite set then the cardinality of $A$ , denoted $| A |$ , is the number of elements $A$ contains. When $| A | = n$ , we say that $A$ is a set of cardinality $n$ . There exists a bijection from any finite set of cardinality $n$ to the set ${0, . . ., (n - 1)}$ containing the first $n$ natural numbers.

Two infinite sets have the same cardinality if there exists a bijection between them. Any set in bijective correspondence with $N$ is called countably infinite, while any infinite set that is not in bijective correspondence with $N$ is call uncountably infinite. All countably infinite sets have the same cardinality, whereas there are multiple distinct uncountably infinite cardinalities.

technical

The cardinality (or size) of a set $X$ is the number of elements in $X .$ For example, letting $X = {a, b, c, d}, | X | = 4.$

The cardinality of a set is a formalization of the "number of elements" in the set.

Set cardinality is an equivalence relation. Two sets have the same cardinality if (and only if) there exists a bijection between them.

Definition of equivalence classes

Finite sets

A set has a cardinality of a natural number $n$ if there exists a bijection between $S$ and the set of natural numbers from $1$ to $n$ . For example, the set ${9, 15, 12, 20}$ has a bijection with ${1, 2, 3, 4}$ , which is simply mapping the $m$ th element in the first set to $m$ ; therefore it has a cardinality of $4$ .

We can see that this equivalence class is well-defined — if there exist two sets $S$ and $T$ , and there exist bijective functions $f : S \to {1, 2, 3, \dots, n}$ and $g : {1, 2, 3, \dots, n} \to T$ , then $g \circ f$ is a bijection between $S$ and $T$ , and so the two sets also have the same cardinality as each other, which is $n$ .

The cardinality of a finite set is always a natural number, never a fraction or decimal.

Infinite sets

Assuming the axiom of choice, the cardinalities of infinite sets are represented by the Aleph_numbers. A set has a cardinality of $ℵ_{0}$ if there exists a bijection between that set and the set of all natural numbers. This particular class of sets is also called the class of countably_infinite_sets.

Larger infinities (which are uncountable) are represented by higher Aleph numbers, which are $ℵ_{1}, ℵ_{2}, ℵ_{3},$ and so on through the ordinals.

In the absence of the Axiom of Choice

Without the axiom of choice, not every set may be well-ordered, so not every set bijects with an ordinal, and so not every set bijects with an aleph. Instead, we may use the rather cunning Scott_trick.

Parents:

Set