Skip to content

Instantly share code, notes, and snippets.

@michaelochurch
Last active June 29, 2019 12:50
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save michaelochurch/a172119b9157fcd3caaf79d19b7c802d to your computer and use it in GitHub Desktop.
Save michaelochurch/a172119b9157fcd3caaf79d19b7c802d to your computer and use it in GitHub Desktop.
Large Countable Ordinals
ω^ω:
0 < 1 < 2 < 4 < 8 < ... < 3 < 6 < 12 < 24 < ... 9 < 18 < 36 < 72 < ...
< 5 < 10 < 20 < ... < 15 < 30 < 60 < ... 45 < 90 < 180 < ...
< 25 < 50 < 100 < ...
< 7 < 14 < 28 < 56 < ...
< 11 < 22 < 44 < 88 < ...
... and so on.
The construction is to embed ω^ω into ω using prime factorization, and then compare lexicographically. We can go further.
ω^ω^ω:
0 < 1 < 2 < 4 < 16 < 256 < ... 8 < 64 < 2^12 < 2^24 < ... < 512 < 2^18 < ...
< 32 < 2^10 < 2^20 ...
< 128 < 2^14 < ...
< 2^11 < 2^22 < ...
< 3 < 6 < 12 < 48 < 768 < ...
This is similar, but we're using the ω^ω-order above on the exponents.
ε_0:
0 <
1 < 3 < 5 < 7 < ... // 2^0 * (2M + 1) in ω ordering of M
2 < 6 < 10 < 18 < 34 < 66 < ... 14 < ... // 2^1 * (2M + 1) in ω^ω ordering of M
4 < 12 < 20 < 36 < 132 < 2052 < ... // 2^2 * (2M + 1) in ω^ω^ω ordering of M
8 < ... // 2^3 * (2M + 1) in ω^ω^ω^ω ordering of M
This is an ordering of ω + ω^ω + ω^ω^ω + ..., which appears distinct from ε_0 but is actually equivalent, analogous to how 1 + ω = ω (and NOT ω + 1).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment