The ordinal-numbers tag has no wiki summary.

**27**

votes

**1**answer

944 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 ...

**23**

votes

**2**answers

445 views

### Order type of the smallest set containing the identity function and closed under exponentiation

Let $E$ be the smallest set of functions $\mathbb{N}^+\to\mathbb{N}^+$ containing the identity function $n \mapsto n$ and closed under exponentiation $(f,g) \mapsto \left(n \mapsto ...

**19**

votes

**1**answer

698 views

### Why isn't this a computable description of the ordinal of ZF?

In a previous MO question, I was told by several commenters that
(a) it's known that there exists a computable ordinal $\alpha_{ZF}$ that "encodes the strength of ZF set theory" (i.e., a least ...

**18**

votes

**1**answer

811 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

**1**answer

960 views

### Number of distinct values taken by $\alpha$ ^ $\alpha$ ^ $\dots$ ^ $\alpha$ with parentheses inserted in all possible ways, $\alpha\in\mathbf{Ord}$

Let $\alpha\in\mathbf{Ord}$ and $n\in\mathbb{N}^+$.
Let $F_\alpha(n)$ be the number of distinct values taken by ordinal exponentiation $\underbrace{\alpha \hat{\phantom{\hat{}}} \alpha ...

**14**

votes

**3**answers

2k views

### Understanding the countable ordinals up to $\epsilon_{0}$

Hello,
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 ...

**14**

votes

**1**answer

860 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 ...

**14**

votes

**1**answer

647 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) ...

**14**

votes

**0**answers

197 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 ...

**13**

votes

**7**answers

1k views

### Finding the largest integer describable with a string of symbols of predefined length

(This question is motivated by the reading of the article Large numbers and unprovable theorems by Joel Spencer, which can be found at ...

**13**

votes

**1**answer

1k 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 ...

**13**

votes

**1**answer

422 views

### Ordinal-indexed homology theory?

Back when I was a grad student sitting in on Mike Freedman's topology seminar at UCSD, he posed the following question. Does there exist a good homology theory $H_{\alpha}(X)$ where $\alpha$ is an ...

**12**

votes

**2**answers

330 views

### What is the least ordinal than cannot be embedded in $\mathbb{R}^\mathbb{R}$?

Let $\mathbb{R}^\mathbb{R}$ be the set of functions $\mathbb{R}\to\mathbb{R}$ patially ordered by eventual domination. Obviously, every ordinal below $\omega_1$ can be embedded in ...

**12**

votes

**1**answer

209 views

### Nontrivial upper bounds on proof-theoretic ordinals of strong theories: do we have any?

Motivated by Consistency of Analysis (second order arithmetic) and Proof-Theoretic Ordinal of ZFC or Consistent ZFC Extensions?, I have the following question:
Are there any examples of strong ...

**12**

votes

**1**answer

408 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, ...

**10**

votes

**3**answers

188 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 ...

**10**

votes

**2**answers

441 views

### Ways to define “definability”

The notion of a definable set is not expressible in the language of set theory: there is no formula $\delta(x)$ that is equivalent with there being a formula $\phi(y)$ such that $x = \lbrace y : ...

**8**

votes

**3**answers

694 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 ...

**8**

votes

**1**answer

463 views

### Does this “jumping-ahead” ordinal function exist?

While working on a project in operator algebras with a collaborator (and fellow MO user), we are able to successfully complete a transfinite induction assuming that the following has an affirmative ...

**8**

votes

**2**answers

1k views

### Naturally occurring orderings

The are many orderings that naturally occur in interesting but seemingly unrelated circumstances. Here are some examples:
The volume spectrum of orientable hyperbolic 3-manifolds has order type ...

**7**

votes

**5**answers

1k 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 ...

**7**

votes

**2**answers

335 views

### Ordinals and complexity classes

What is the least recursive ordinal $\alpha$ such that there is no algorithm in complexity class $\mathsf{P}$ which implements a well-ordering of $\mathbb{N}$ with order type $\alpha$? (where the size ...

**7**

votes

**1**answer

347 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 ...

**7**

votes

**1**answer

197 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 ...

**7**

votes

**2**answers

293 views

### Peano arithmetic vs. fast-growing hierarchy with pathological fundamental sequences

Fundamental sequence for a countable limit ordinal $\alpha$ is an increasing sequence $\{\alpha[i]\}$ of ordinals of length $\omega$ such that $\lim_{i\rightarrow\omega}\alpha[i]=\alpha$. There are ...

**6**

votes

**2**answers

459 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 ...

**6**

votes

**1**answer

601 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 ...

**6**

votes

**1**answer

677 views

### Ordinal category theory?

Just out of curiosity: Is there a notion of $\alpha$-category for an ordinal number $\alpha$, extending the given notions for $\alpha \leq \omega$? If there is none, which one would you propose? Feel ...

**5**

votes

**1**answer

298 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 ...

**5**

votes

**1**answer

224 views

### Arithmetic strength of Peano + the Howard ordinal

Consider the theory $\mathrm{PA}+\mathrm{BHO}$ consisting of first-order Peano arithmetic ($\mathrm{PA}$) enriched by an axiom scheme which allows well-founded induction up to any ordinal less than [a ...

**5**

votes

**0**answers

40 views

### Anything known about the Grundy Ordinal of Sylver's Coinage

Sylver's coinage is an example of an unbounded finite (if slightly modified) combinatorial impartial game. Quoth wikipedia:
The two players take turns naming positive integers that are not the
...

**5**

votes

**0**answers

89 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 ...

**4**

votes

**4**answers

653 views

### Prime numbers and limit ordinals

As a set, i.e. as a von Neumann ordinal, the $\omega$-th limit ordinal $\omega^2$ is fairly complex and not so easy to visualize (for the novice). But as an explicit well-ordering of $\mathbb{N}$, ...

**4**

votes

**3**answers

507 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 ...

**4**

votes

**1**answer

353 views

### Cardinality of cofinal set of normal functions $f \colon \omega_1 \to \omega_1$

What is the cardinality of the set $F$ of all normal functions $f \colon \omega_1 \to \omega_1$, where $\omega_1$ is the first uncountable ordinal?
What is the least cardinality of a subset of $F$ ...

**4**

votes

**2**answers

296 views

### Heights of several interesting posets

Let the height of a poset $P$ be the supremum of ordinals that are order types of all well-ordered subsets of $P$ (with order inherited from $P$).
Define several sets of total functions, in each ...

**4**

votes

**1**answer

662 views

### Cantor's Normal Form and Aleph_1

The Cantor Normal Form Theorem states that every ordinal $\alpha > 0$ can be uniquely expressed in the form $$\omega^{\beta_1}k_1 + \omega^{\beta_2}k_2 + \dots + \omega^{\beta_n}k_n$$ for some $n ...

**4**

votes

**1**answer

208 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 ...

**4**

votes

**1**answer

211 views

### Surreal numbers, ultrapowers of $\Bbb R$, ordinal-valued functions and the slow-growing hierarchy

Philip Ehrlich's paper “The Absolute Arithmetic Continuum and the Unification of All Numbers Great and Small”, The Bulletin of Symbolic Logic 18 (1) 2012, pp. 1-45. claims as a theorem that, in NBG, ...

**4**

votes

**0**answers

78 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 ...

**3**

votes

**2**answers

1k 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 ...

**3**

votes

**1**answer

348 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 ...

**3**

votes

**1**answer

557 views

### Height of ordered set

In all "constructive" fixed-point theorems for functions on ordered sets that I am aware of, where the fixed point is obtained as the limit of a stationary increasing transfinite sequence, it is ...

**3**

votes

**1**answer

813 views

### Well ordering of countably branching well founded trees

Hello everybody,
I would like to say, before stating the question, that I'm not a mathematician, and therefore i apologize in advance if the question is trivial, or well-known. I'll try to state it ...

**3**

votes

**1**answer

282 views

### Order type of the minimal set closed under ordinal exponentiation

Define $\tau: \mathbf{Ord} \to \mathbf{Ord}$ such that $\tau(\alpha)$ is the order type of the minimal set $S$ of ordinals such that $\alpha \in S$ and $S$ is closed under ordinal exponentiation.
We ...

**2**

votes

**1**answer

222 views

### What is the order type of $L$ with Godel's well ordering?

In some sense $Ord$ is a "proper class" ordinal. Unfortunately the notion of a proper class ordinal is not a straight forward generalization of the notion of "set" ordinals because the proper classes ...

**2**

votes

**1**answer

221 views

### A question about additively indecomposable ordinals

I'm studying some topics about topological games of length $\alpha\geq\omega$, where I came across the following statement about additively indecomposable ordinals (recall that $\alpha$ is additively ...

**1**

vote

**1**answer

139 views

### Functions in “gaps” in Hardy hierarchy

Recall the definition of Hardy's hierarchy:
$H_0(n)=n+1\\
H_{\alpha+1}(n)=H_\alpha(n+1)\\
H_\alpha(n)=H_{\alpha[n]}(n)$,
where the last rule applies if $\alpha$ is limit ordinal, and $\alpha[n]$ ...

**1**

vote

**1**answer

253 views

### center depth of Birkhoff center

I saw a statement about the Birkhoff center. Namely let $X$ be a compact metric space and $f:X\to X$ be a homeomorphism on $X$. Then for each ordinal $\alpha$ we define
for $\alpha=0$, let ...

**1**

vote

**1**answer

113 views

### Formula for the Ordinal Number of k-Sets of Positive Integers

Background of my question is, that I would like to store flags indicating the relation between a pairs of non-adjacent edges of a graph (that relation could for example be, whether the edges cross, ...