Intereting Posts

Why are measures real-valued?
Which rational functions are derivatives of rational functions?
Finding roots of 5 th degree taylor expansion of $e^x$
Mrs Reed safe combination
Evaluation of $\lim_{m \to \infty} \sum_{k = 0}^{m} \frac{m! (2m-k)!}{(m-k)!(2m)!}\frac{x^k}{k!}$
Prove that $a_n=1+\frac{1}{1!} + \frac{1}{2!} +…+ \frac{1}{n!}$ converges using the Cauchy criterion
Irrationality of $ \frac{1}{\pi} \arccos{\frac{1}{\sqrt{n}}}$
Isomorphism of R-modules
Squares in $(\operatorname{rad}(1)^2+1)\cdot(\operatorname{rad}(2)^2+1)\ldots(\operatorname{rad}(n)^2+1)$
If the sequence satisfies the property lim$_{n\to \infty}(a_n-a_{n-2})=0$, prove that lim$_{n\to \infty}\frac{a_n-a_{n-1}}{n}=0$.
Expected value of integrals of a gaussian process
Expected number of rounds to get particular groupings when rolling a die
Every path has a simple “subpath”
Is $\mathbb{Z}/p^\mathbb{N} \mathbb{Z}$ widely studied, does it have an accepted name/notation, and where can I learn more about it?
Are there an infinite number of prime quadruples of the form $10n + 1$, $10n + 3$, $10n + 7$, $10n + 9$?

How is the ordinal $\omega_1$ defined? I know that it is a supremum of all smaller ordinals, but then $\omega^\omega$ is also a supremum of all smaller ordinals. How can we distinguish these two numbers?

Edit: changing the question into how $\omega^{\omega}$ can be shown countable, and how other countable ordinals can be shown to be countable.

- Is this a good way to explicate Skolem's Paradox?
- Assumed True until proven False. The Curious Case of the Vacuous Truth
- Conditional Statements: “only if”
- The cardinality of a countable union of countable sets, without the axiom of choice
- Prove that $\omega + \omega_1 = \omega \cdot \omega_1 = \omega^{\omega_1} = \omega_1$
- Can a model of set theory think it is well-founded and in fact not be?
- Is formal truth in mathematical logic a generalization of everyday, intuitive truth?
- Why $¬¬\bot \not\in PROP$?
- Is Godel's modified liar an illogical statement?
- A limit ordinal $\gamma$ is indecomposable if and only if $\alpha + \gamma = \gamma$ if and only if $\gamma = \omega^{\alpha}$ for some $\alpha$.

$\omega^\omega$ is countable because it is a union of a countable collection of sets, each of which is itself countable: $$\omega^\omega = \bigcup_{i<\omega} \omega^i$$

So it suffices to show that:

- A union of a countable collection of countable sets is countable.
- $\omega^i$ is countable whenever $i$ is finite.

(1) should be familiar to you; it is the usual Cantor argument for showing that the rationals are countable. If the countable sets are $S_0, S_1\ldots$ with elements $S_i = \{s_{i0}, s_{i1}, \ldots\}$, then we can enumerate the union of the $S_i$ as $s_{00}; s_{10}, s_{01}; s_{20}, s_{11}, s_{02}; s_{30}, \ldots$.

(2) is not hard either; you can prove the the product of two countable sets is countable (essentially as in the previous paragraph) and then show that since $\omega^{i+1} = \omega\times\omega^i $, countability of $\omega^{i+1}$ follows from that of $\omega^i$, which is enough to establish the result.

(You may want to look up the notion of cofinality. An ordinal $X$ has countable cofinality if it is a countable union of smaller ordinals. If those smaller ordinals are themselves countable, then $X$ is countable. So to show that $\omega^\omega$ is countable, it is enough to show that it has countable cofinality, which we can do by observing that it is the union of the countable ordinals $\omega^i$ for finite $i$.)

Then similarly if $C$ is some countable ordinal, $\omega^C$ is countable. For we can write some countable sequence $c_0, c_1,\ldots$ whose limit is $C$, and then $\omega^C = \bigcup \omega^{c_i}$ expresses $\omega^C$ as a countable union of countable sets. So not only are $\omega$ and $\omega^\omega$ countable, so are $\omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}} \ldots$. And then we can take the union of countable the sequence of countable sets $\omega, \omega^\omega, \omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}} \ldots$ and conclude that this union, usually written $\epsilon_0$, is countable as well.

$\epsilon_0$ has the property that it is the smallest ordinal $x$ for which $x=\omega^x$. There is an infinite sequence of countable ordinals with this property, and their union is still countable.

There are quite a few countable ordinals, and some of them are very strange monsters. See for example Church–Kleene ordinal and the Feferman–Schütte ordinal.

Generally speaking, the best course of action when trying to show that $\alpha$ is a countable ordinal, is to show that:

- $\alpha = \delta+n$ where $\delta$ is a limit ordinal (if $n=0$ then $\alpha=\delta$);
- $\delta$ is the limit of $\{f(\beta)\mid \beta<\gamma\}$ for some countable $\gamma$; and
- $f(\beta)$ is countable is countable whenever $\beta$ is countable.

For example, $\epsilon_0$ is the limit of $\omega^\omega,\omega^{\omega^\omega},\omega^{\omega^{\omega^\omega}},\ldots$. We can show that this is the limit of the recursive function $f(n+1)=\omega^{f(n)}$ and $f(0)=\omega$. We can further show that if $\beta$ is countable then $\omega^\beta$ is also countable (note that this is ordinal exponentiation) and therefore $\epsilon_0$ is the countable limit of countable ordinals and thus countable.

The same method can be applied to general ordinals, although obtaining such $f$ is often harder than it is in the case of $\epsilon_0$.

One caveat is that this is true in ZFC but not necessarily in ZF, where a countable union of countable ordinals may be countable.

- Why $M=\{(x, |x|), x\in\mathbb{R}\}$ is not an embedded submanifold?
- Linear combinations of delta measures
- What are the odds of hitting exactly 100 rolling a fair die
- Finding the angle of rotation of an ellipse from its general equation and the other way around
- $xy=1 \implies $minimum $x+y=$?
- Uniform distribution on the surface of unit sphere
- Contradictory; Homotopy equivalence and deformation retract problem
- Inequality. $\frac{1}{16}(a+b+c+d)^3 \geq abc+bcd+cda+dab$
- $\mathbb{Q}/\langle x^2+y^2-1 \rangle$ is an integral domain, and its field of fractions is isomorphic to $\mathbb Q(t)$
- What is the fastest way to multiply two digit numbers?
- An almost complex structure on real 2-dimensional manifold
- How to find all the coset leaders? (follow-up to a previous question)
- integrate $\int \frac{1}{e^{x}+e^{ax}+e^{a^{2}x}} \, dx$
- Prove the divergence of the sequence $\left\{ \sin(n) \right\}_{n=1}^{\infty}$.
- Gromov-Hausdorff distance and the “set of all sets”