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

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

- An ordering $R$ is
*reflexive*if and only if $xRx$, for all $x$ in the domain of $R$. - An ordering $R$ is
*irreflexive*if and only if $\neg xRx$. - An ordering $R$ is
*transitive*if and only if $xRy$ and $yRz$ implies $xRz$, for all $x$, $y$, and $z$. - An ordering $R$ is
*antisymmetric*if and only if $xRy$ and $yRx$ implies $x=y$. - An ordering $R$ is
*trichotomous*if and only if $xRy$, $x=y$, or $yRx$ for all $x$ and $y$ in the field of $R$.

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$.

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.

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.

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.