§ Ordinals and cardinals
This a rough sketch of a part of set theory I know very little about, which I'm encountering as I solve
the "supplementary exercises" in Munkres, chapter 1.
§ 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 3
based 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
A cardinal that cannot be created by adding cardinals, taking unions of cardinals, taking power sets
of cardinals. So the set of cardinals smaller than an inacessible cardinal give a model for ZFC.
if $\kappa$ is an inaccessible cardinal, then $V_\kappa$, collection of all sets of rank less than $\kappa$
acts as a place to do mathematics safely, while still having access to the "set of all sets" $V_\kappa$
(Grothendeick universes, apparently).
§ Alternative definition of cardinality using rank
- Recall that we wanted to define cardinality as the equivalence class of of equinumerous sets, but this ran into set theoretic issues.
- A fix (by Dana Scott) is for a set $A$, consider the least rank $\kappa$where some set in bijection with $A$ appears. Then we define the cardinality of $A$ to be the equivalence classes of sets in $V_\kappa$ that are in bijection with $A$. This gives us the cardinals without needing us to consider all sets. This works even without well ordering.
- I don't actually understand why this works. In my mind, the set
{0}
and {{0}}
both have the same size, but {0}
lives in V1
while {{0}}
lives in V2
, so they won't have the same cardinality? Actually, I think I do understand: for the set {{0}}
, the set {0}
which is in bijection with {{0}}
occurs at rank 1
, so the cardinality of {{0}}
is given by the equivalence class in V1
: [{0}]
. - The key part seems to be "find the smallest rank". I have no idea how one would formalize this.
§ Weak and strong limits
- A set $S$ is a strong limit if it cannot be obtained by taking powersets of sets smaller than it.
- In set theory, we as a rule of thumb replace powerset with successor to get some weaker statement.
- A set $S$ is a weak limit if it cannot be obtained by taking successor of sets smaller than it.
§ References