Cardinality

https://arbital.com/p/cardinality

by Joe Zeng Jun 28 2016 updated Oct 5 2016

The "size" of a set, or the "number of elements" that it has.


[summary(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 , denoted , is the number of elements contains. When , we say that is a set of cardinality . There exists a bijection from any finite set of cardinality to the set containing the first natural numbers.

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

[summary(technical): The cardinality (or size) of a set is the number of elements in For example, letting

[todo: technical summary of infinite cardinality]]

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 if there exists a bijection between and the set of natural numbers from to . For example, the set has a bijection with , which is simply mapping the th element in the first set to ; therefore it has a cardinality of .

We can see that this equivalence class is [ well-defined] — if there exist two sets and , and there exist bijective functions and , then is a bijection between and , and so the two sets also have the same cardinality as each other, which is .

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 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 and so on through the [ordinal 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].

%%todo: Examples and exercises (possibly as lenses) %%

%%todo: Split off a more accessible cardinality page that explains the difference between finite, countably infinite, and uncountably infinite cardinalities without mentioning alephs, ordinals, or the axiom of choice.%%