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.

Filter by
Sorted by
Tagged with
9 votes
2 answers
615 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 $\...
Nate Ackerman's user avatar
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 ...
Scott Aaronson's user avatar
4 votes
0 answers
333 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. ...
Dmytro Taranovsky's user avatar
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 ...
Gro-Tsen's user avatar
  • 29.9k
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 ...
Martin Brandenburg's user avatar
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 ...
Mohammad Golshani's user avatar
13 votes
1 answer
586 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 $\...
Gro-Tsen's user avatar
  • 29.9k
8 votes
1 answer
493 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 ...
Jesse Elliott's user avatar
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 ...
Keith Millar's user avatar
  • 1,242
5 votes
1 answer
645 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_%...
user avatar
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 ...
SSequence's user avatar
  • 861
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 ...
user avatar
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 ...
Mike Battaglia's user avatar
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) ...
Gro-Tsen's user avatar
  • 29.9k
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 ...
David E Speyer's user avatar
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 ...
James Propp's user avatar
  • 19.4k
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 ...
SNd's user avatar
  • 161
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 ...
Simon Henry's user avatar
  • 39.9k
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 ...
user avatar
12 votes
1 answer
803 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, ...
Vladimir Reshetnikov's user avatar
12 votes
1 answer
737 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 ...
Wojowu's user avatar
  • 27.4k
11 votes
2 answers
672 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 ...
Gro-Tsen's user avatar
  • 29.9k
11 votes
3 answers
532 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)...
Jesse Elliott's user avatar
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 ...
Gro-Tsen's user avatar
  • 29.9k
10 votes
1 answer
484 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 ...
QiRenrui's user avatar
  • 475
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: ...
Mirco A. Mannucci's user avatar
9 votes
2 answers
670 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 ...
user avatar
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 ...
Vladimir Reshetnikov's user avatar
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 ...
Toby Bartels's user avatar
  • 2,644
7 votes
1 answer
416 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.$ ...
Idonknow's user avatar
  • 603
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 ...
B H's user avatar
  • 387
6 votes
3 answers
785 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 ...
Vladimir Reshetnikov's user avatar
6 votes
1 answer
501 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 ...
Reflecting_Ordinal's user avatar
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 $(\...
Zetapology's user avatar
5 votes
1 answer
259 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, ...
C7X's user avatar
  • 1,186
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 ...
Yto's user avatar
  • 148
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 ...
SSequence's user avatar
  • 861
3 votes
2 answers
742 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 ...
user820789's user avatar
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 ...
SSequence's user avatar
  • 861
2 votes
1 answer
391 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, ...
Pace Nielsen's user avatar
2 votes
1 answer
440 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 \...
SSequence's user avatar
  • 861
2 votes
1 answer
348 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$). ...
SSequence's user avatar
  • 861