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

Cantor's Attic (original site)
Joel David Hamkins blog post about the Attic
Latest working snapshot at the wayback machine

Basic Order Theory

We will denote an arbitrary ordering relation by $R$. We will establish some preliminary definitions:

Partial Ordering

A partial ordering consists of a relation along with a set such as $( A , \le )$ such that the order is reflexive, transitive, and antisymmetric for all members of $A$.

A strict partial ordering consists of an ordered pair $( A , \lt )$ that is irreflexive and transitive for all members of $A$.

All strict partial orders are asymmetric, meaning that $xRy$ implies that $\neg yRx$.

Total Ordering

A total ordering consists of a partial ordering where any two elements are comparable, that is, for all $x$ and $y$ in $A$, $x\le y \lor y\le x$

A strict total ordering is a strict partial ordering that is also trichotomous.

Well-Founded Relations

A minimal element of $B$ with respect to a strict ordering relation $\lt$ is an element $x$ of $B$ that is not greater than any other element in $B$. That is $\forall y \in B: \neg y \lt x$

A well-founded relation is an ordering $\lt$ under $A$ such that any nonempty subset $x$ of $A$ contains a minimal element.

There are many interesting properties of well-founded relations. For example, all well-founded relations do not have any ordering “loops”. That is, they are irreflexive, asymmetric, etc.

Well-founded relations do not have any infinitely descending $<$-chains. Another way to state this is that no function $f$ mapping the natural numbers to well-founded set $A$ where $f(n+1) < f(n)$ for all natural numbers $n$.

Any subset of $A$, even if it is a proper class, must have a minimal element. The proof of this is not as straightforward as it sounds.

We can also prove schemas of well-founded induction and well-founded recursion; the first strongly resembles epsilon induction, while the second defines a function $F(x)$ in terms of a function $G$ of the restriction of $F$ to the initial segment of $x$.

An initial segment or extension of $x$ is the collection of all sets in $A$ less than $x$.

We call a well-founded relation setlike if the initial segments of all the elements of $A$ are elements.

Well-Ordering Relations

A well-ordering relation is a well-founded relation that is also a strict total order. Equivalently, we can also define a well-ordering relation as a well-founded relation that satisfies trichotomy.

The ordinals can be defined as the set of all transitive sets that are well-ordered by the membership relation.

The Well-ordering principle shows that all sets have some well-order associated with them.

All well-ordered sets are order-isomorphic to the ordinals.