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
1
vote
2
answers
104
views
Transfinite recursion to construct a function on ordinals
I am asked to use transfinite recursion to show that there is a function $F:ON \to V$ (here $ON$ denote the class of ordinals and $V$ the class of sets) that satisfies:
$F(0) = 0$
$F(\lambda) = \...
- 839
0
votes
1
answer
117
views
Proving the Weak Goodstein Theorem within $\mathsf{PA}$
In
Cichon, E. A., A short proof of two recently discovered independence results using recursion theoretic methods, Proc. Am. Math. Soc. 87, 704-706 (1983). ZBL0512.03028.
the following process is ...
- 4,432
2
votes
1
answer
67
views
Is possibile to define an exponentiation with respect an ordinal operation?
It is well know the following resul holds.
Theorem
For any $(M,\bot,e)$ monoid there exists a unique esternal operation $\wedge_\ast$ from $X\times\omega$ into $X$ such that for any $x$ in $M$ the ...
- 4,906
1
vote
0
answers
72
views
Reference request: monoids on ordinal numbers
It is well-known that $(\text{Ord},+,0)$ and $(\text{Ord},\cdot,1)$ are monoids, but I haven't found references on these structures or other simpler ones (like $(\omega_1,+,0)$). For example, it would ...
- 414
0
votes
1
answer
67
views
An ordinal $\nu$ is a natural iff there is no injection $f$ of $\nu$ into $X$ in $\mathscr P(\nu)\setminus\{\nu\}$.
Let's we prove the following theorem.
Theorem
An ordinal $\nu$ is a natural if and only if there is no injection of $\nu$ into $X$ in $\mathscr P(\nu)\setminus\{\nu\}$.
Proof.
Let's we assume there ...
- 4,906
1
vote
1
answer
116
views
$\omega$-th or $(\omega + 1)$-th when putting odd numbers after even numbers?
The following clip is taken from Chapter 4 - Cantor: Detour through Infinity (Davis, 2018, p. 56)[2]. When putting odd numbers after even numbers, what should the index for the first odd number ($1$ ...
- 103
3
votes
1
answer
64
views
A countable ordinal which is $\Sigma_n$-definable in first-order ZFC, but not $\Sigma_m^1$-definable in full second-order arithmetic
Let us say that a $\Sigma_m^1$-formula $\phi$ defines a countable ordinal $\alpha$ if it defines a type-$1$ object (i.e. a real) $x$ that encodes a well-ordering of $\mathbb{N}$ of order type $\alpha$ ...
- 922
3
votes
0
answers
82
views
What is $\epsilon_0 \cdot \omega$?
I'm a bit stuck on telling what the ordinal $\epsilon_0 \cdot \omega$ is.
$$\epsilon_0 = \sup \{1, \omega, \omega^{\omega}, \omega^{\omega^{\omega}}, \dots \}$$
so
$$\epsilon_0 \omega = \sup \{\omega, ...
- 3,940
1
vote
1
answer
82
views
How can different representations of the same integer be equivalent?
I recently read about a way to define the set of integers as the set of all equivalence classes for some equivalence relation $\simeq$ satisfying $(a,b)\simeq(c,d)$ for $(a, b),\;(c,d)\in\mathbb{N}\...
- 508
6
votes
0
answers
215
views
$\varepsilon_0 !$ (ordinal factorial)
Given an ordinal $\alpha$, define $\alpha !$ as it follows:
$$
\alpha! := \begin{cases}
0! = 1 \\
(\alpha + 1)! = \alpha ! \cdot (\alpha + 1) \\
\lambda! = \left(\sup_{\gamma < \lambda} \gamma !\...
- 509
2
votes
1
answer
105
views
Taking the limit beyond infinity, with the ordinals
Imagine a function $f:X\to X$ and $x\in X$ (keeping $f$ and $X$ vague on purpose) and let's define
$u_1 = f (x)$
$u_2=f^2(x)=f(f(x))$
$u_n=f^n(x)$
Let's also assume that $\forall n, u_{n-1} \neq u_n $ ...
- 169
2
votes
1
answer
104
views
Stuck on Jech's Set Theory Exercise 2.3
From Jech's Set Theory:
Exercise (2.3). If $X$ is inductive, then $X\cap\text{Ord}$ is inductive. $\textbf{N}$ is the least nonzero limit ordinal, where $\textbf{N} = \bigcap\{X:X\text{ is inductive}\...
- 5,166
0
votes
1
answer
68
views
Proving $\alpha\subset\beta\implies\alpha\in\beta$ for ordinals $\alpha$ and $\beta$
From Jech's Set Theory:
Lemma 2.11.
(iii) If $α\ne β$ are ordinals and $α ⊂ β$, then $α ∈ β$.
Proof: If $α ⊂ β$, let $��$ be the least element of the set $β − α$. Since $α$ is transitive, it follows ...
- 5,166
2
votes
1
answer
200
views
Countable ordinals having a certain property
Which are the countable ordinals $\lambda$ such that, for every sequence of ordinals $\alpha_i\ (i\in\mathbb{N})$ such that
$\ $it is strictly increasing for all sufficiently large $i$
$\ $$\alpha_i&...
- 161
3
votes
1
answer
146
views
Is the empty set always an 'implicit member' of all sets under a pure set theory?
Pure set theory, wherein all objects considered are sets —whose elements are themselves sets, and so forth— is usually thought of as building itself up in an ex nihilo fashion off the empty set $\...
- 512