**29**

votes

**1**answer

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

510 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 f(n)^{g(n)}\right)$...

**23**

votes

**1**answer

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

**19**

votes

**1**answer

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

**18**

votes

**1**answer

911 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

997 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 \hat{\phantom{\...

**17**

votes

**0**answers

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

**16**

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 $\epsilon_{0}$-...

**16**

votes

**2**answers

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

**15**

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

**15**

votes

**1**answer

821 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

**1**answer

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

**13**

votes

**7**answers

2k 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 http://mathdl.maa.org/images/upload_library/22/Ford/Spencer669-...

**12**

votes

**2**answers

383 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 $\mathbb{R}^\mathbb{...

**12**

votes

**1**answer

254 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

464 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

**1**answer

302 views

### Is ordinal arithmetic more complicated than classical arithmetic?

Consider the first-order language $\mathcal{L}_{\text{OA}}:=(+,\cdot,0,1)$; in this language, we can formulate statements of ordinal arithmetic. Clearly, the theory $T_{\text{OA}}$ of $(\text{On},+,\...

**10**

votes

**3**answers

247 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

**2**answers

459 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 : \phi(...

**9**

votes

**3**answers

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

**9**

votes

**1**answer

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

**9**

votes

**1**answer

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

**9**

votes

**2**answers

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

**9**

votes

**0**answers

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

**8**

votes

**1**answer

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

**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 $\...

**8**

votes

**1**answer

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

**7**

votes

**5**answers

2k 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

344 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

**2**answers

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

**7**

votes

**1**answer

608 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

396 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, $\...

**7**

votes

**1**answer

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

**7**

votes

**1**answer

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

**6**

votes

**4**answers

529 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: ...

**6**

votes

**1**answer

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

**6**

votes

**1**answer

326 views

### Which ordinals are proof-theoretic ordinals?

Few months ago I have posted this question on MO, but I must admit that at the time, admittedly, I had no idea on how technical proof-theoretic considerations can be. I have decided to revise this ...

**6**

votes

**0**answers

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

**5**

votes

**3**answers

539 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

349 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_%...

**5**

votes

**1**answer

123 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

103 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

698 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

**2**answers

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

**4**

votes

**1**answer

218 views

### Reference request, proof about well-ordering of ordinals

I am looking for a second order proof that ordinals are well-ordered up to $\epsilon_0$.
So, starting with encoding those ordinals in numbers, defining the < relation on those encoded ordinals and ...

**4**

votes

**1**answer

415 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

316 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

792 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

277 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

119 views

### Ordinals which embed in surreal subfields

If $k$ is an ordered field, the least ordinal $s(k)$ which doesn't embed in $(k,<)$ is regular. This is because every interval of an ordered field embeds in every infinite interval so given a ...