Climb into Cantor’s Attic, where you will find infinities large and small. We aim to provide a comprehensive resource of information about all notions of mathematical infinity.
View the Project on GitHub neugierde/cantors-attic
Quick navigation
The upper attic
The middle attic
The lower attic
The parlour
The playroom
The library
The cellar
Sources
Cantor's Attic (original site)
Joel David Hamkins blog post about the Attic
Latest working snapshot at the wayback machine
Cardinality is a measure of the size of a set. Two sets have the same cardinality—they are said to be equinumerous—when there is a one-to-one correspondence between their elements. The cardinality assignment problem is the problem of assigning to each equinumerosity class a cardinal number to represent it. In ZFC, this problem can be solved via the well-ordering principle, which asserts that every set can be well-ordered and therefore admits a bijection with a unique smallest ordinal, an initial ordinal. By this means, in ZFC we are able to assing to every set $X$ a canonical representative of its equinumerosity class, the smallest ordinal bijective with $X$.
We therefore adopt the definition that $\kappa$ is a cardinal if it is an initial ordinal, an ordinal that is not equinumerous with any smaller ordinal.
The set $\omega$ of natural numbers is the smallest inductive set, that is, the smallest set for which $0\in\omega$ and whenever $n\in\omega$ then also $n+1\in\omega$, where $n+1=n\cup\{n\}$ is the successor ordinal of $n$. A set is finite if it is equinumerous with a natural number, and otherwise it is is infinite. In ZFC, the finite sets are the same as the Dedekind finite sets, but in ZF, these concepts may differ. In ZFC, $\aleph$ is a unique order-isomorphism between the ordinals and the cardinal numbers with respect to membership.
A set is countable when it is equinumerous with a subset of $\omega$. This includes all finite sets, including the empty set, and the infinite countable sets are said to be countably infinite. An uncountable set is a set that is not countable. The existence of uncountable sets is a consequence of Cantor’s observationt that the set of reals is uncountable.
Hartog established that for every set $X$, there is a smallest ordinal that does not have an injection into $X$, and this ordinal is now known as the Hartog number of $X$. When $\kappa$ is a cardinal, then the successor cardinal of $\kappa$, denoted $\kappa^+$, is the Hartog number of $\kappa$, the smallest ordinal of strictly larger cardinality than $\kappa$. The existence of successor cardinals can be proved in ZF without the axiom of choice. Iteratively taking the successor cardinal leads to the aleph hierarchy.
Although ZF proves the existence of successor cardinals for every cardinal, ZF also proves that there exists some cardinals which are not the successor of any cardinal. These cardinals are known as limit cardinals. Cardinals which are not limit cardinals are known as successor cardinals. The limit cardinals are precisely those which are limit points in the topology of cardinals (hence the name). That is, for any cardinal $\lambda<\kappa$, there is some $\nu>\lambda$ with $\nu<\kappa$.
The limit cardinals share an incredible affinity towards the singular cardinals; there does not exist a weakly inaccessible cardinal if and only if the singular cardinals are precisely the limit cardinals. If inaccessibility is inconsistent (which is thought “untrue” by most set theorists, although possible), then ZFC actually proves that any cardinal is singular if and only if it is a limit cardinal.
A cardinal $\kappa$ is regular when $\kappa$ not the union of fewer than $\kappa$ many sets of size each less than $\kappa$. Otherwise, when $\kappa$ is the union of fewer than $\kappa$ many sets of size less than $\kappa$, then $\kappa$ is said to be singular.
The axiom of choice implies that every successor cardinal $\kappa^+$ is regular, but it is known to be consistent with ZF that successor cardinals may be singular.
The cofinality of an infinite cardinal $\kappa$, denoted $\text{cof}(\kappa)$, is the smallest size family of sets, each smaller than $\kappa$, whose union is all of $\kappa$. Thus, $\kappa$ is regular if and only if $\text{cof}(\kappa)=\kappa$, and singular if and only if $\text{cof}(\kappa)\lt\kappa$.
See general cardinal for an account of the cardinality concept arising without the axiom of choice.
When the axiom of choice is not available, the concept of cardinality is somewhat more subtle, and there is in general no fully satisfactory solution of the cardinal assignment problem. Rather, in ZF one works directly with the equinumerosity relation.
In ZF, the axiom of choice is equivalent to the assertion that the cardinals are linearly ordered. This is because for every set $X$, there is a smallest ordinal $\alpha$ that does not inject into $X$, the Hartog number of $X$, and conversely, if $X$ injects into $\alpha$, then $X$ would be well-orderable.
The Dedekind finite sets are those not equinumerous with any proper subset. Although in ZFC this is an equivalent characterization of the finite sets, in ZF the two concepts of finite differ: every finite set is Dedekind finite, but it is consistent with ZF that there are infinite Dedekind finite sets. An amorphous set is an infinite set, all of whose subsets are either finite or co-finite.