§ 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 ff 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:ABf: A \rightarrow B be monotone: a<aa < a' implies f(a)<f(a)f(a) < f(a'). Furthermore, there is a function g:BAg: B \rightarrow A such that g(f(a))=ag(f(a)) = a and f(g(b))=bf(g(b)) = b.
  • Claim: if b<bb < b' then g(b)<g(b)g(b) < g(b').
  • Let b<bb < b'. We must have (a) g(b)<g(b)g(b) < g(b'), or (b) g(b)=g(b)g(b) = g(b'), or (c) g(b)>g(b)g(b) > g(b').
  • If g(b)<g(b)g(b) < g(b') we are done.
  • Suppose for contradiction g(b)g(b)g(b) \geq g(b') then we must have f(g(b))f(g(b))f(g(b)) \geq f(g(b')) since ff is monotone. Since f,gf, g are inverses we get bbb \geq b'. This contradicts the assumption b<bb < b'.
  • This doesn't work for partial orders because we may get bb and bb' 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 oo: (1) every element xox \in o will be a subset of oo, since xxis itself a set { ordinal < x }, which is a subset of { ordinal < o }. (2) the set oois 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 XX 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, ω+1\omega + 1 is NOT a cardinal (can be put in bijection with ω\omega),
  • We can think of 0\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 1\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.
  • V0V_0 is the empty set.
  • Vn+12VnV_{n+1} \equiv 2^{V_n}. This defines VV for successor ordinals.
  • Vλβ<λVβV_\lambda \equiv \cup_{\beta < \lambda} V_\beta. This defines VV for limit ordinals.
  • The set VαV_\alpha are also callled stages or ranks. We can define the rank of a set SS to be the smallest α\alphasuch that SVα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κ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κ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 AA, consider the least rank κ\kappawhere some set in bijection with AA appears. Then we define the cardinality of AA to be the equivalence classes of sets in VκV_\kappa that are in bijection with AA. 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 SS 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 SS is a weak limit if it cannot be obtained by taking successor of sets smaller than it.

§ References