§ Ordinals

• Two totally ordered sets have the same order type if there is a monotone isomorphism between them. That is, there's a function $f$ which is monotone, and has an inverse. The inverse is guaranteed to be motone (1), so we do not need to stipulate a monotone inverse.
• Definition of well ordered set : totally ordered set where every subset has a least element.
• Theorem: The set of well ordered sets is itself well ordered.
• Definition ordinals : Consider equivalence classes of well ordered sets under order type. of well ordered sets with the same order type. The equivalence classes are ordinals .

§ (1) Inverse of a Monotone function is monotone.

• Let $f: A \rightarrow B$ be monotone: $a < a'$ implies $f(a) < f(a')$. Furthermore, there is a function $g: B \rightarrow A$ such that $g(f(a)) = a$ and $f(g(b)) = b$.
• Claim: if $b < b'$ then $g(b) < g(b')$.
• Let $b < b'$. We must have (a) $g(b) < g(b')$, or (b) $g(b) = g(b')$, or (c) $g(b) > g(b')$.
• If $g(b) < g(b')$ we are done.
• Suppose for contradiction $g(b) \geq g(b')$ then we must have $f(g(b)) \geq f(g(b'))$ since $f$ is monotone. Since $f, g$ are inverses we get $b \geq b'$. This contradicts the assumption $b < b'$.
• This doesn't work for partial orders because we may get $b$ and $b'$ as incomparable .

§ Von Neumann Ordinals

• Von neumann ordinals: Representatives of equivalence classes of ordinals. Formally, each Von-Neumann ordinal is the well-ordered set of all smaller ordinals.
• Formal defn of Von-Neumann ordinal $o$: (1) every element $x \in o$ will be a subset of $o$, since $x$is itself a set { ordinal < x }, which is a subset of { ordinal < o }. (2) the set $o$is well ordered by set membership, since two such ordinals will always be comparable, and one must contain the other.
• For example of Von Neumann ordinals, consider 0 = {}, 1 = {0}, 2 = {0, 1}, 3 = {0, 1, 2}. We can order 3 based on membership: 0 ∈ 1, 2 so 0 < 1, 2. 1 ∈ 2 hence 1 < 2. This totally orders 3based on set membership. Next, also see that a member of 3, such as 2, is in face 2 = {0, 1}, which is a subset of 3. So every member of 3 is a subset of 3. (Not vice versa: not every subset is a member! The subset {1, 2} is not a member of 3).

§ Limit ordinals

• A limit ordinal is an ordinal that cannot be written as the successor of some other ordinal.
• Theorem : An ordinal must be either zero, or the successor of some other ordinal, or a limit ordinal (2)
• References on ordinals

§ Cardinality and cardinals

• We can define cardinality as equivalence classes of sets that are equinumerous : ie, sets with bijections between them. This does not strictly speaking work due to set-theoretic issues, but let's go with it.
• In each such equivalence class of sets which are equinumerous, there will be many well ordered sets. The smallest such well ordered set (recall that the set of well ordered sets is itself totally ordered). This is called as the cardinal for that cardinality.
• So we redefine cardinality as the smallet ordinal $\alpha$ such that there is a bijection between $X$ and $\alpha$. This is motivated from the "equivalence class of all equinumerous sets", but sidesteps set theoretic issues. For this to work, we need well ordering. Otherwise, there could a set with no ordering that is in bijection with it.

§ Definition of Cardinal

• Said differently, an ordinal is a cardinal if it cannot be put in bijection with any smaller ordinal.
• Thus, all natural numbers are cardinals, $\omega$ is a cardinal, $\omega + 1$ is NOT a cardinal (can be put in bijection with $\omega$),
• We can think of $\aleph_0$ as a countably infinite queue where each person in the queue has to wait for finitely many people to exit.
• We can think of $\aleph_1$ as a uncountably infinite queue where each person in the queue has to wait for countably many people to exit.

§ Rank

• The rank of the empty set is zero. The rank of a set is recursively the smallest ordinal greater than the ranks of all the members of the set. Every ordinal has a rank equal to itself.
• $V_0$ is the empty set.
• $V_{n+1} \equiv 2^{V_n}$. This defines $V$ for successor ordinals.
• $V_\lambda \equiv \cup_{\beta < \lambda} V_\beta$. This defines $V$ for limit ordinals.
• The set $V_\alpha$ are also callled stages or ranks. We can define the rank of a set $S$ to be the smallest $\alpha$such that $S \subseteq V_\alpha$.

§ Inaccessible cardinal