Questions tagged [ordinal-numbers]
An ordinal is the order type of a well-ordered set. The first few ordinals are $0, 1, 2, \dots, \omega, \omega+1, \dots$ where $\omega$ is the order type of $\mathbb{N}$, and $\omega+1$ is the order type of $\mathbb{N}$ together with a maximum element.
45
questions with no upvoted or accepted answers
19
votes
0
answers
576
views
Can Gentzen-style proofs give omega-consistency and beyond?
In 1936, Gentzen famously showed that Primitive Recursive Arithmetic, plus the assumption that the ordinal $\epsilon_0$ is well-founded, is able to prove Con(PA). But of course, Con(PA) doesn't yet ...
- 9,753
17
votes
0
answers
835
views
Ramsey's theorem for the first uncountable ordinal
Sierpiński proved that a version of Ramsey's theorem for colourings of pairs of countable ordinals fails miserably by comparing the ordering of $\omega_1$ with the linear ordering of (a subset of) the ...
- 11.3k
13
votes
0
answers
405
views
Is it an open problem whether fast-growing hierarchies can be defined without fundamental sequences?
Googology Wiki says this, concerning the relation between fast-growing hierarchies defined for all countable ordinals, and the existence of a system of assigning a canonical fundamental sequence to ...
- 4,529
10
votes
0
answers
494
views
Which finite sets could be packed into a square?
This question is inspired by an interesting visualization of the finite levels of von Neumann's hierarchy on Adam P. Goucher's blog, Complex Projective 4-Space.
The problem starts with a two-...
10
votes
0
answers
397
views
Computing the ordinal of a rational language well-partially-ordered by the subword relation
Let $\Sigma$ be a finite set or "alphabet", $\Sigma^*$ the free monoid on $\Sigma$ or set of "words". If $w,w'\in \Sigma^*$, write $w\leq w'$ when $w$ is a "subword" of $w'$, i.e., can be obtained by ...
- 30.2k
9
votes
0
answers
293
views
Mapping graphs to ordinals
Robertson-Seymour theorem implies that graph minor relation is a well-quasi-ordering, which means (among other things) that this relation can be extended to a well-order, and other result says that ...
- 27.4k
8
votes
0
answers
264
views
Natural examples of recursive pseudowellorderings
Question: What are some natural examples of recursive pseudowellorderings?
By natural, I mean in the style of reasonable ordinal notation systems as opposed to dependent on a Gödel numbering or an ...
- 6,112
7
votes
0
answers
280
views
How "small" can an ordinal be made by forcing?
I know that forcing essentially does not change the ordinals, but by small I mean in comparison with other ordinals whose definition might not be stable under forcing, like the smallest uncountable ...
- 40.2k
6
votes
0
answers
150
views
Iterated $\Pi^1_1$-reflection and non-Gandiness underrepresented in ordinal analyses?
This is a copy of Math StackExchange question #4395977, which I felt was more appropriate for MathOverflow.
Note on terminology: "admissible", "$(^+)$-stable", and "$\Pi^1_1$-...
- 1,298
6
votes
0
answers
141
views
Proof of Theorem Concerning Conway's "Nim Field"
I have a question about the proof of theorem 44 in "On Numbers and Games" on page 58, concerning the "Nim field" ${ON}_2$. As background, ${ON}_2$ turns the ordinals into a field ...
- 449
6
votes
0
answers
370
views
What is proof-theoretic ordinal of weak first-order arithmetic?
According to Wikipedia(https://en.wikipedia.org/wiki/Ordinal_analysis) and nlab(https://ncatlab.org/nlab/show/ordinal+analysis), a proof-theoretic ordinal of $\mathsf{PRA}$ is $\omega^\omega$.
...
- 178
6
votes
0
answers
283
views
Weaker versions of Gandy ordinals
Gostanian's paper "The next admissible ordinal" (see https://www.sciencedirect.com/science/article/pii/0003484379900251 ), is concerned with the supremum of the $\alpha$-recursive ordinals for various ...
- 335
5
votes
0
answers
155
views
Higher-order equivalence of ordinals
I wonder which ordinals are second-order equivalent, and similarly for other logical equivalences. Let the signature be fixed and include only <. For concreteness, let us first ask for the first ...
5
votes
0
answers
234
views
Higher order arithmetic, hierarchies and proof theoretic ordinals
I asked this question on MSE some days ago but I have not received any answer so I have decided to post it here.
I would like to consider a generalization of the notation $\Pi$ and $\Sigma$ used for ...
- 161
5
votes
0
answers
238
views
$Π_2$ strength of KP
I am looking for a characterization of the $Π_2$ statements provable in KP.
Here, KP (often denoted KPω) is the Kripke-Platek set theory, including infinity and full induction on ordinals. Here is ...
- 6,112
4
votes
0
answers
108
views
Parameter-free $\alpha$-recursivity versus weakened Turing machines with oracles
In the quest to find a transfinite extension of recursivity which matches intuition, mentioned also in my previous question, Discord user onion5 came up with an idea that expressed precisely how I ...
- 148
4
votes
0
answers
126
views
Simple $(\alpha+1)$-recursive well-orders with order type $|\alpha\text{-recursive}|$
In the following, $L_\alpha$ is the $\alpha$-th level of the constructible hierarchy, $\alpha$-recursive means definable in $L_\alpha$ by a $\Delta_1$ formula. $|\alpha\text{-recursive}|$ is the ...
- 148
4
votes
0
answers
145
views
Slicing large countable ordinal properties, from $\Pi_3$-reflection to $\Sigma_2$-admissibility
Edit 2024: This post was based on an incorrect premise, as can be seen by my conversation with Farmer S in the comments. However the mistake I made and the conversation in comments may be instructive (...
- 1,298
4
votes
0
answers
148
views
Infinite positions in 3D chomp
I've recently come back to investigating ordinal chomp. See A winning move for the first player in $3 \times 3 \times \omega$ Ordinal Chomp for a definition. I made a new discovery, that the position \...
- 2,691
4
votes
0
answers
338
views
Ordinal analysis and nonrecursive ordinals
Ordinal analysis is typically described as characterizing recursive ordinals in a theory $T$, but there is a sense in which it can characterize all $T$-ordinals, even those that are nonrecursive.
...
- 6,112
4
votes
0
answers
205
views
$\omega_1$-like elementary chains from long countable elementary chains
For some countable first-order theory $T$, if we have a linearly ordered set $I$ and an elementary chain $\{\mathfrak{A}_i\}_{i\in I}$ we can form a structure $\mathfrak{A}_{I}^\star = (\bigcup_{i\in ...
- 10.3k
4
votes
0
answers
189
views
On the proof of a normal form theorem for ordinal (primitive) recursion
Consider the following statement (which follows easily from various results found in the literature):
(†) There exists a primitive recursive (“p.r.”) relation $T$ on the ordinals such that, if $(...
- 30.2k
4
votes
0
answers
202
views
Upper bound on ranks of well-founded trees in $SKI\Omega$ calculus
All ideas explained below are due to A.P.Goucher, and defined here.
First of all, $SKI\Omega$ calculus is an extension of standard SKI calculus, with additional type of combinator, called oracle ...
- 27.4k
3
votes
0
answers
100
views
Existence of a almost increase $\omega_1^{\omega_1}$ sequence mod $[\omega_1]^{<\omega_1}$ with length $\omega_2$
In my textbook, the author said that the sequence below is satisfied the requirement.
$$\text{For }\alpha<\omega_1,\forall\gamma<\omega_1,g_\alpha(\gamma)=\alpha, \text{For }\omega_1\le\alpha<...
- 31
3
votes
0
answers
326
views
An alternative definition of computable ordinals
An ordinal $\alpha$ is said to be computable if there is a computable relation on a subset of integers that is well-ordered and its order type equals $\alpha$.
But let's consider well-founded trees on ...
- 1,288
3
votes
0
answers
243
views
Is this recursion theoretic analogue of a criterion of weakly compact cardinal accurate?
Jensen proved that, if V=L, and $\kappa$ is a regular cardinal, then if for any stationary $A\subseteq \kappa$, the set $\{\alpha\mid A \text{ is stationary below }\alpha\}$ is stationary in $\kappa$, ...
- 1,410
3
votes
0
answers
149
views
Can the essence of the $0^\#$ LCA be weakened to an axiom not requiring uncountable cardinals?
"$0^\#$ exists" is an informally stated large cardinal axiom that is to be understood as "there is an uncountable set of Silver indiscernibles", "every uncountable cardinal is ...
- 482
3
votes
0
answers
155
views
Trees of prescribed ordinal
My question is very imprecise, as I know very little about descriptive set theory.
In a problem I am thinking about I have a family of well-founded trees (finite sequences on $\cup_n X^n$ closed under ...
- 63
3
votes
0
answers
79
views
Self-contained proof of WO of Buchholz's ordinal notation system
I would like a self-contained proof that the ordinal notation system defined by Buchholz in this paper is indeed well-ordered. Meaning, I would like a proof that does not rely on ordinals. Buchholz's ...
- 1,074
3
votes
0
answers
122
views
Coloring triples in trees
Definitions
Let us say a tree is a partially ordered set $(P, \leqslant )$ such that for any $t\in P$, the ancestor set $\{s\in P: s\leqslant t\}$ is finite and linearly ordered. We let $MAX(P)$ ...
user78375
3
votes
0
answers
167
views
Simple transfinite generalization of $p$-adic integers
One way to define the ring of $p$-adic integers is as a quotient of the formal power series semiring $\Bbb N[[x]]/(x-p)$. One can likewise start with the formal power series ring $\Bbb Z[[x]]/(x-p)$ ...
- 4,525
3
votes
0
answers
137
views
Partial well-ordering of formulas
Given a theory $T$, for arbitrary formulas $φ$ and $ψ$ that provably in $T$ denote an ordinal, set $[φ]_T < [ψ]_T$ iff provably in $T$, the ordinal denoted by $φ$ is less than the ordinal denoted ...
- 6,112
3
votes
0
answers
58
views
Trace-Recursive Functions and Natural/Unnatural Operations
I have been quite hesitant to post this question. Due to the highly general nature of the question there is a possibility of a trivial answer. At a first glance at least, one gets the feeling that ...
- 861
2
votes
0
answers
150
views
How closely do ordinal collapsing functions relate to Skolem hulls?
Ordinal collapsing functions appear in proof theory, and they are used to name large countable ordinals by using uncountable ordinals. Previously I posted a question about why $\psi(\alpha)$ is ...
- 1,298
2
votes
1
answer
303
views
What's the order type of the following set?
Fix a positive integer n. Assume $Lan=\{R_0,R_1,...,R_n\}$ be a language of first order logic, where every $R_i$ is a 2-ary relation symbol.
Assume $M$ is an Lan-model, where the underlying set is $...
- 1,410
2
votes
0
answers
226
views
The supremum of ordinals eventually writable by Ordinal Turing Machines with an oracle for the class of stabilization ordinals
This question is based on the assumption that all computations start with no ordinal parameters (i.e. the input is empty).
The term “stabilization time of a machine” for this question implies the ...
- 959
2
votes
0
answers
217
views
Countable Fodor's Lemma?
Does Fodor's lemma fail for countable ordinals?
For the usual statement of Fodor's lemma to make sense, one needs well-behaved notions of club and stationary sets, which fail for countable ordinals, ...
- 61.6k
2
votes
0
answers
63
views
Splitting of ordinals of oscillation ranks of a Baire $1$ function
Denny and Tang proved that
Theorem $2.3$ Let $(f_n)$ be a sequence in $\mathfrak{B}_1(K)$ converging pointwise to a function $f.$
Suppose $\sup\{ \beta(f_n):n\in\mathbb{N} \} \leq \beta_0$ and $\...
- 603
2
votes
1
answer
668
views
Transfinite sums related to a sequence
Given a sequence $S$ indexed by the finite ordinals, a limit ordinal $\alpha$, and $k \in \mathbb{N}$, define $S_{\alpha+k}$(the extension of $S$ to $\alpha+k$) to be the sum over the products of all $...
- 333
1
vote
0
answers
120
views
Can every set be ordinal definable?
From Wikipedia:
OD is not necessarily transitive, and need not be a model of ZFC.
This obviously means that, assuming ZFC is consistent, there is a model $M \models \mathrm{ZFC}$ so that $\mathrm{OD}...
- 704
1
vote
0
answers
159
views
Can we have a proper class of infinitely descending infinite ordinals?
Working in $\sf ZF-Reg.$, can we have a transitive model $M$ of $\sf ZF$ such that there exists a proper class (i.e. a subset of $M$ that is not an element of $M$) of infinitely descending infinite ...
- 9,276
1
vote
0
answers
202
views
Is it possible to construct a formal language that allows to refer to specific real numbers that encode ordinals accidentally writable by an ITTM?
Let $A$ denote a particular (fixed) algorithm to encode ordinals as real numbers. The exact technical description of $A$ is irrelevant for this question: it can be any algorithm that is mathematically ...
- 959
1
vote
0
answers
123
views
Ordinal corresponding to well-quasi-order on graphs
Let $K$ be an infinite cardinal. Then, by the Robertson–Seymour theorem, the set of graphs with fewer than $K$ vertices and edges form a well-quasi-order.
In terms of $K$, what is the maximal order ...
- 5,831
0
votes
0
answers
25
views
Reference for tree of bad sequences of WPO
I'm looking for a reference to give in Wikipedia for the following result: Let $X$ be a WPO. Let $T_X$ be the tree of bad sequnces of $X$, and let $o(X)$ be the ordinal height of the root of $T_X$. ...
- 1,074
0
votes
0
answers
143
views
How to define BHO alternatives below admissible ordinals?
Bachmann-Howard ordinal is a recursive ordinal. It's not that large compared to those proof-theoretic ordinals of stronger theories, but the definition of BHO is sufficient to illustrate how ...
- 1,410