Questions tagged [ordinals]
In the ZF set theory ordinals are transitive sets which are well-ordered by $\in$. They are canonical representatives for well-orderings under order-isomorphism. In addition to the intriguing ordinal arithmetics, ordinals give a sturdy backbone to models of ZF and operate as a direct extension of the positive integers for *transfinite* inductions.
1,981
questions
2
votes
0
answers
28
views
References that give the cofinality of ordinal addition, multiplication and exponentiation
$\newcommand{\cf}{\operatorname{cf}}$
Let $\alpha$, $\beta$ be ordinals. I believe that we have
\begin{align*}
\cf(\alpha+\beta)=\cf(\beta),\quad\beta\neq 0;\quad\cf(\alpha\cdot\beta)=\begin{cases}\cf(...
- 1,923
2
votes
1
answer
104
views
Define the sum of transfinite ordinal sequences according to finite ordinal sum.
I know it is possibile to define finite sum of ordinals: if $(\alpha_i)_{i\in n}$ is a sequence of lenght $n$, with $n$ in $\omega$, then the symbolism $\sum_{i\in n}\alpha_i$ has a (formal) meaning; ...
- 4,906
2
votes
1
answer
62
views
Does $\omega_1^{\text{CK}}$ allow to compute the halting problem of $\alpha$-th-order Turing machines for any $\alpha < \omega_1^{\text{CK}}$?
This page contains the following text (see the section “Higher-order busy beaver functions”):
At least, under any reasonable formulation of the notion of a higher-order Turing machine, well-orderings ...
- 922
2
votes
1
answer
156
views
Is this a valid basis for a transfinite number system?
I've been curious about transfinite number systems including infinite ordinals, hyperreals, and surreal numbers. The hyperreals in particular seem particularly appealing for introducing a hierarchy of ...
-2
votes
1
answer
57
views
Prove that the order type of $\alpha\cdot\beta$ is the antilexicographic order in $\alpha\times\beta$. [closed]
This question is related to this one, but not a duplicate, since I am struggling with injectivity and monotonicity, rather than proving that $\{\alpha\cdot\eta + \xi:\eta<\beta\textrm{ and }\xi<\...
- 4,906
6
votes
2
answers
117
views
Can we implement $\omega^{CK}_1$ using $\omega^{CK}_2$ as an oracle?
Let $\omega^{CK}_1$, $\omega^{CK}_2$ denote the first two admissible ordinals greater than $\omega$. Suppose we have an unknown well-ordering of $\mathbb{N}$ of the order type $\omega^{CK}_2$ as an ...
- 161
4
votes
1
answer
182
views
Colourful class function
Background. We're in $\mathsf{ZFC}$, and I can use the principle of $\epsilon$-induction, but not (directly) the $\epsilon$-recursion.
Problem. Let $F : V \to V$, where $V$ is the class of all the ...
- 509
0
votes
0
answers
75
views
How Should I Do the Inductive Case of this Proof on Ordinals?
Question
Prove that for all ordinals $\alpha$, $V_\alpha=\{x:\rho (x)<\alpha\}$.
Note:
The function $\rho$ is a rank function.
Attempt
I did the proof by induction on ordinals. I started with the ...
- 451
2
votes
0
answers
137
views
Strictly decreasing function from an ordinal to $\mathbb{R}$
Context: We are working in $\mathsf{ZFC}$.
Problem: Given a poset $(P,<)$, let $\text{Dec}(P)$ be the set of all strictly decreasing function $f : \alpha \to P$, where $\alpha$ is an ordinal number....
- 509
4
votes
1
answer
126
views
Is there a smarter way to calculate $F(\omega^{15} + 7)$? (Ordinal arithmetic)
Given the function $F : \text{Ord} \to \text{Ord}$ definite by transfinite recursion as it follows:
$$F(0) = 0 \qquad F(\alpha + 1) = F(\alpha) + \alpha \cdot 2 + 1 \qquad F(\lambda) = \sup_{\gamma &...
- 509
2
votes
1
answer
48
views
How Can I Finish off this Solution on Ordinal Arithmetic (Cantor Normal Form)?
Question
Let $\beta = \omega + 3$, and $\alpha = \omega ^42+\omega ^34+6 = \beta ^\gamma \delta +\rho$. Find ordinals $\gamma$ and $\delta$, with $0<\delta<\beta$ and $\rho <\beta ^\gamma$.
...
- 451
1
vote
1
answer
48
views
Is this Solution on Ordinal Arithmetic Correct (Cantor Normal Form)?
Question
Let $\beta=\omega + 3$. Calculate $\beta ^2,\beta ^3$ and $\beta ^4$ in Cantor Normal Form.
Attempt
Since $\beta = \omega + 3$, then $\beta ^2 = (\omega +3)(\omega +3) = (\omega +3).\omega + (...
- 451
0
votes
0
answers
39
views
Find necessary and sufficient conditions for ordinal monotonicity.
First of all let's we remember the following result.
Theorem
Let be $\lambda$ and ordinal: a predicate $\mathbf P$ is true for any $\alpha$ in $\lambda$ when the truth of $\mathbf P$ for any $\beta$ ...
- 4,906
1
vote
0
answers
75
views
Does the equality $\omega\cdot(\omega+1)=(\omega+1)\cdot\omega$ hold?
By this answer I knkow that the equality
$$
(\omega+1)\cdot\omega=\omega^3
$$
holds whereas by the definition of ordinal multiplication I know that the equality
$$
\omega\cdot(\omega+1)=\omega^2+\...
- 4,906
4
votes
0
answers
84
views
Finding the first term of a Goodstein sequence whose expression has maximum exponent
Let $n$ be a natural number. When constructing the Goodstein sequence $(n)_{k}$, we start with $(n)_{1}=n$ written in complete base $2$, and we proceed recursively. That is, if $(n)_{k}$ has been ...
- 4,432