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.
42
questions
9
votes
2
answers
649
views
Order type of $\alpha$-computable well-orderings
One of the nice features of the first admissible ordinal after $\omega$, i.e. $\omega_1^{CK}$, is that it is the collection of ordinals whose order type is that of a computable well-ordering on $\...
40
votes
2
answers
3k
views
Is there a computable ordinal encoding the proof strength of ZF? Is it knowable?
In comments on Quora (see, for example, here, here, here), Ron Maimon has repeatedly expressed the strong opinion that Hilbert's program was not killed by Gödel's results in the way typically ...
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.
...
18
votes
1
answer
1k
views
Looking for a copy of Leo Harrington's unpublished notes on the first nonprojectible ordinal
Sometime around 1975, Leo Harrington wrote a set of notes, apparently 13 pages long, entitled Kolmogorov's $R$-operator and the first nonprojectible ordinal. I do not know how widely they were ...
17
votes
6
answers
4k
views
What is the idea behind stationary sets?
Let $\kappa$ be a cardinal (of uncountable cofinality). A subset $S \subseteq \kappa$ is called stationary if it intersects every club, i.e. closed unbounded subset of $\kappa$. Now my question is ...
13
votes
3
answers
2k
views
Consistency of Analysis (second order arithmetic)
Is there a proof of the consistency of Analysis (second order arithmetic), which is similar to Gentzen's proof of the consistency of arithmetic?
Update:
Which (different) methods can be used to ...
13
votes
1
answer
592
views
About primitively recursively recognizable ordinals
Preliminary: I believe the notion of primitive recursive functions on ordinals is standard and unproblematic (the main difference with the finite case is that one needs to introduce a $\sup$ or $\...
8
votes
1
answer
496
views
Transcendence degree of the surreals over the subfield generated by the ordinals
Consider the Grothendieck ring $K[\Omega]$ of the semiring $\Omega$ of all ordinals under the operations of natural sum and product. Its quotient field $K(\Omega)$ is naturally a subfield of the ...
8
votes
4
answers
1k
views
Formalizations of The Matchstick Diagram Representation of Ordinals
The matchstick diagram is a really interesting and intuitive method of representing countable ordinals. However, because of how difficult it is to graphically represent ordinals with it, I started ...
5
votes
1
answer
647
views
value of Theta in ZF+AD
Since I found out about it, I've always been interested in the Axiom of Determinacy rather than the Axiom of Choice. Along these lines, I've kept flipping back to http://en.wikipedia.org/wiki/%CE%98_%...
2
votes
1
answer
269
views
Mapping between Notations
As in my other question, it is assumed that the (total) function describing a given notation is denoted as $address:p\rightarrow \Bbb{N}$ and assumed to be bijective.
Suppose we are given two ...
38
votes
4
answers
5k
views
Understanding the countable ordinals up to $\epsilon_{0}$
in a recent MO question, link, discussing the current foundations of mathematics, the author linked a video lecture by Prof. Voevodsky, which argues against the principle of $\epsilon_{0}$-induction ...
31
votes
1
answer
2k
views
Are Conway's omnific integers the Grothendieck group of the ordinals under commutative addition?
This is a question in two parts.
Say that $\mathbf{On}$ is the proper class of all ordinal numbers in ZFC. We can define a binary operator over $\mathbf{On}$ which corresponds to the commutative ...
29
votes
2
answers
3k
views
Does Taranovsky's system of ordinal notations make sense?
Dmytro Taranovsky has a Web page on which he claims to define a system of ordinal notations strong enough to provide an ordinal analysis of full second-order arithmetic. I think (perhaps unjustly) ...
27
votes
5
answers
3k
views
What is induction up to $\varepsilon_0$?
This is a question asked out of curiosity, and because I can't understand the Wikipedia page.
I have often been told that PA cannot prove the validity of induction up to $\varepsilon_0$, which has ...
18
votes
2
answers
1k
views
Nice sign-expansions of special surreal numbers
What is the "right" surreal generalization of the fact that a real number $r$ is rational if and only if its sign-expansion is eventually periodic?
I can think of more than one natural way to ...
16
votes
1
answer
2k
views
Proof theoretic ordinal
In Ordinal Analysis, Proof-theoretic Ordinal of a theory is thought as measure of a consistency strength and computational power.
Is it always the case? I. e. are there some general results about ...
15
votes
3
answers
1k
views
Ordinals in constructive mathematics ? (references)
I'm looking for references presenting a constructive treatment of the theory of ordinals. By constructive I mean valid in the internal logic of a topos (so no axiom of choice and no law of excluded ...
14
votes
1
answer
1k
views
How strong are large cardinal properties of Ord?
Ordinal numbers are generalizations of natural numbers. In this sense the "proper class" of all ordinals ($Ord$) is very similar to "infinite" set of all natural numbers ($\omega$). In the other ...
12
votes
1
answer
747
views
Which ordinals can be proof-theoretic ordinals of a reasonable theory?
When talking to a friend recently he asked a question - are there any reasonable first-order theories which have proof theoretic ordinal equal to small or large Veblen ordinal? I have then extended ...
12
votes
1
answer
806
views
Transfinitely extending $\sf PA$ — can we get stronger than $\sf ZFC$?
Let $\sf PA$ denote the theory of natural numbers with constants $(0, 1)$ and binary operators $(+,\times)$ based on the first-order predicate calculus with equality, having the following axioms, ...
11
votes
2
answers
679
views
Is there a modern account of Veblen functions of *several* variables?
Veblen $\phi$ functions extend the $\xi \mapsto \phi(\xi) := \omega^\xi$ and the $\xi \mapsto \phi(1,\xi) := \varepsilon_\xi$ functions on the ordinals by repeatedly taking fixed points (I won't ...
11
votes
3
answers
533
views
First-order definable bijection between $P(On)$ (or $No$) and $V$? (Is this equivalent to $V = HOD$?)
It is known that locally one can ``code'' any set in the von Neumann universe $V$ by a set of ordinals. But can one do this globally? In other words, is there a first-order definable bijection $P(On)...
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 ...
10
votes
1
answer
488
views
Examples of proofs using induction or recursion on a big recursive ordinal
There are many proofs use induction or recursion on $\omega$, or on an arbitary (may be uncountable) ordinal. Are there some good examples of proofs which use a big but computable ordinal?
The ...
9
votes
4
answers
1k
views
Direct axiomatization of ordinal and cardinal numbers
Again, this question is related (**) to a previous one:
in standard books on basic set theory, after stating the axioms of ZFC, ordinal numbers are introduced early on. Afterwards cardinals appear: ...
9
votes
2
answers
673
views
The Theory of Transfinite Diophantine Equations [closed]
The theory of Diophantine equations is one of the main stream research areas in number theory. There are many known results and unknown conjectures about the existence of non-trivial solutions for ...
8
votes
1
answer
3k
views
Foundations: Existence of uncountable ordinals.
This isn't really a research question, but at least it's research-level mathematics. I'm talking with some other people about the first uncountable ordinal, and I want some facts to inform this ...
8
votes
2
answers
1k
views
How this set of functions is ordered?
Notation:
$k, m, n$ are non-negative integers
$f, g, h$ are functions $\mathbb{N} \to \mathbb{N}$
$f^k$ is $k$-th iterate of the function $f$: $f^0(n)=n, f^{k+1}(n)=f^k(f(n))$
$f \prec g$ means ...
7
votes
1
answer
1k
views
Cardinality of $\omega\uparrow^\omega\omega$
I was wondering what the cardinality of $\omega\uparrow^\omega\omega$ is, with $\uparrow$ being Knuth's up-arrow notation. I ask this purely out of curiosity; after finding out about set theory I feel ...
7
votes
1
answer
420
views
Reference Request: Existence of Ordinal Rank Theory?
Notations: Recall that $\omega_1$ is the first uncountable ordinal.
Let $X$ be a Polish space (completely metrizable and separable) and $F(X)$ be the collection of all real-valued functions on $X.$
...
6
votes
1
answer
508
views
Parameter-free effective cardinals
In the paper "Effective cardinals and determinacy in third order arithmetic" by Juan Aguilera, effective cardinals is defined.
I'm curious about its little variation, parameter-free ...
6
votes
3
answers
1k
views
Do these ordinals exist?
Given an ordinal $\alpha$, I define $F_{n}(\alpha)$ as follows:
$F_0(\alpha)=\alpha$
$F_{n+1}(\alpha)$ is the smallest $\beta$ such that no first-order $\phi$ in the
language of $\{\in\}$ has $(\...
6
votes
3
answers
786
views
Is it consistent with ZFC that for all ordinals $\alpha, \beta < \omega$ it holds that $2^{\aleph_\alpha} = 2^{\aleph_\beta}$?
Let $\gamma=\omega$ (the first transfinite ordinal). Is it consistent with ZFC that for all ordinals $\alpha, \beta < \gamma$ it holds that $2^{\aleph_\alpha} = 2^{\aleph_\beta}$?
If yes, can the ...
5
votes
1
answer
260
views
How closely do ordinal collapsing functions relate to Mostowski collapse?
Ordinal collapsing functions (such as Rathjen's $\psi_\pi$-functions, not the Levy collapse function) name large countable ordinals by mapping larger ordinals below some "large" ordinal, ...
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 ...
3
votes
2
answers
758
views
Veblen function with uncountable ordinals & beyond
Disclaimer: I am not a professional mathematician.
Background: I have been researching large countable ordinals for awhile & I think the Veblen function is particularly eloquent. My understanding ...
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 ...
2
votes
1
answer
394
views
Generalizing König's Lemma
In some recent work, I need a strengthening of König's Lemma to "trees" of arbitrary ordinal heights. Trees, in this context, are really just well-founded partially ordered sets. See, for instance, ...
2
votes
2
answers
299
views
Finite Number of Registers and Computable Well-Orderings
I have added the formal definition of the function $address$. The question is divided in two parts. This is important because of two reasons. First due to the length of the question. Secondly if one ...
2
votes
1
answer
444
views
Formal definition of this ordinal?
Few days I asked this question (https://math.stackexchange.com/questions/2907733/simple-ordinal-question) on MSE. Summary of the question is that I defined a certain function over ordinals $x \mapsto \...
2
votes
1
answer
349
views
Relation of $\omega_{\omega_1+1}^{CK}$ to some other ordinals
This was posted as a side question in Formal definition of this ordinal? and was split as a separate question based upon suggestion in comments there.
Assume an ordinary ORM model (call it $C_1$). ...