Definition

Ordering#

Definition. A binary relation \(<\) on a set \(P\) is a partial ordering of \(P\) if

Nonreflexive. \(p\nless p\) for any \(p\in P\).
Transitive. if \(p<q\) and \(q<r\) then \(p<r\).

if moreover we have trichotomy, namely \(p<q\) or \(p=q\) or \(q<p\) for any \(p,q\in P\), the ordering is called linear. The relation \(\leq\) is also called a partial/linear ordering if \(<\) is a partial/linear ordering.

Given a partially ordered set \((P,<)\) and a nonempty subset \(X\) of \(P\), and \(a\in P\), then

\(a\) is a maximal(or minimal) element of \(X\) if \(a\in X\) and \(\forall x\in X(a\nless x)\) (or \(a\nless x)\).
\(a\) is the greatest(or least) element of \(X\) if \(a\in X\) and \(\forall x\in X(x\leq a)\) (or \(a\leq x\)).
\(a\) is an upper bound (lower bound) of \(X\) if \(\forall x\in X(x\leq a))\) (or \(a\leq x\)). Note that we don't need \(a\) to be in \(X\).
\(a\) is the supremum(infimum) of \(X\) if \(a\) is the least upper bound (greatest lower bound) of \(X\).

Maximal is not smaller, while greatest is positively greatest. Thus if \(X\) is linearly ordered then a maximal element of \(X\) coincides with its greatest element.

An order-preserving function \(f\) is also called increasing if it is between linearly ordered sets.

Well-Ordering#

Definition. A linear ordering \(<\) of a set \(P\) is a well-ordering if every nonempty subset of \(P\) has a least element.

Lemma. If \((W,<)\) is a well-ordered set and \(f:W\to W\) is increasing, then \(f(x)\geq x\) for each \(x\in W\).

Proof. If \(X=\{x\in W: f(x) <x\}\) is nonempty, then let \(z\) be the least element of \(X\), then \(f(z)<z\) which is absurd.

Corollary. The only automorphism of a well-ordered set is the identity. (since \(f(x) \geq x\) and \(f^{-1}(x)\geq x\) for all \(x\))

Corollary. The isomorphism between two well-ordered sets is unique.

Corollary. No well-ordered set is isomorphic to an initial segment of itself. (if \(\text{Im}(f) = \{x:x<u\}\) then \(f(u)<u\))

Theorem. If \(V\) and \(W\) are well-ordered sets, then exactly one of the following cases holds:

\(V\cong W\).
\(V\) is isomorphic to an initial segment of \(W\).
\(W\) is isomorphic to an initial segment of \(V\).

Ordinal Numbers#

Definition. A set \(T\) is transitive if every element of \(T\) is a subset of \(T\).

Definition. A set is an ordinal number if it is transitive and well-ordered by \(\in\).

From definition we have the following lemma:

Lemma.

\(0=\emptyset\) is an ordinal.
If \(\alpha\) is an ordinal and \(\beta\in\alpha\), then \(\beta\) is an ordinal. (\(\beta\) is an element of \(\alpha\), thus a subset of \(\alpha\), thus an element of \(\beta\) is a subset of \(\alpha\) intersected with \(\beta\), which is a subset of \(\beta\).)
If \(\alpha\neq\beta\) are ordinals and \(\alpha\subset\beta\) then \(\alpha\in\beta\). (\(\alpha\) is an initial segment of \(\beta\) and since ordinals are well-ordered by \(\in\), \(\alpha\in\beta\).)
If \(\alpha,\beta\) are ordinals, then either \(\alpha\subset\beta\) or \(\beta\subset\alpha\).

Thus we have that \(<\) is a linear ordering of the class \(\text{Ord}\) of ordinals. For \(\alpha, \beta\) ordinals, \(\alpha < \beta\) iff \(\alpha\in \beta\) and \(\alpha = \{\beta:\beta<\alpha\}\). Morover an intersections of nontempty class of ordinals is an ordinal. A union of nonempty sets of ordinals is an ordinal.

For every \(\alpha\) ordinal, \(\alpha\cup\{\alpha\}\), the successor of \(\alpha\), also denoted \(\alpha +1\), is an ordinal. \(\alpha + 1 = \text{Inf}\{\beta:\beta>\alpha\}\). Since \(\text{sup}(\text{Ord})+1\) is still in \(\text{Ord}\), \(\text{Ord}\) is a proper class.

Theorem. Every well-ordered set is isomorphic to a unique ordinal number. (We need Replacement Axioms to prove this.)

Definition. If \(\alpha\) is an ordinal which is not a successor, then \(\alpha = \text{sup}\{\beta:\beta<\alpha\} = \bigcup \alpha\) and \(\alpha\) is called a limit ordinal. We consider \(0\) a limit ordinal and define \(\text{sup}\emptyset = 0\). (The existence of limit ordinals other than \(0\) follows from the Axiom of Infinity.)

Definition. The least nonzero limit ordinal is called the set of natural numbers and is denoted \(\omega\). The ordinals less than \(\omega\) are called finite ordinals or natural numbers. A set \(X\) is finite if there is a 1-1 mapping of \(X\) onto some \(n\in\omega\). \(X\) is infinite it is not finite.