**9**

votes

**0**answers

197 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

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

**4**

votes

**1**answer

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

**11**

votes

**1**answer

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

**6**

votes

**4**answers

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

**3**

votes

**1**answer

124 views

### Least ordinal not embedded in a total order

If $(E,<)$ is a linear order, let $s(E,<)$ denote the least ordinal which doesn't embed in $(E,<)$.
I am trying to prove the following:
If $(M,+,.,0,1)$ is a model of open induction, (or ...

**4**

votes

**1**answer

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

**6**

votes

**0**answers

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

**16**

votes

**2**answers

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

**6**

votes

**1**answer

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

**2**

votes

**2**answers

258 views

### Ordinals separate from set theory

Is there an exposition and development of ordinals theory separate from set theory? That is, some first-order theory where terms are interpreted as ordinals, with constant $0$ (and maybe $\omega$), ...

**7**

votes

**1**answer

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

**1**

vote

**1**answer

88 views

### Rank of Cartesian product of well-partial-orders

We are interested in the ordinal rank $h(P)$ of a wpo (a well-partial-order). It is known that it coincides with the order type of its longest chain.
When we consider the cartesian product $P\times ...

**5**

votes

**1**answer

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

**10**

votes

**3**answers

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

**1**

vote

**1**answer

183 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]$ ...

**4**

votes

**1**answer

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

**9**

votes

**2**answers

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

**8**

votes

**1**answer

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

**4**

votes

**0**answers

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

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

**12**

votes

**1**answer

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

**1**

vote

**1**answer

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

**23**

votes

**1**answer

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

**17**

votes

**0**answers

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

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

**12**

votes

**1**answer

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

**9**

votes

**3**answers

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

**7**

votes

**1**answer

383 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

**2**answers

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

**4**

votes

**4**answers

692 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}$, ...

**10**

votes

**2**answers

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

**2**

votes

**1**answer

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

**2**

votes

**1**answer

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

**9**

votes

**1**answer

414 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

**2**answers

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

**23**

votes

**2**answers

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

**18**

votes

**1**answer

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

**15**

votes

**1**answer

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

**0**

votes

**1**answer

260 views

### Is there a name for the smallest ordinal $\alpha$ such that $X \subseteq \alpha$

Let $X$ be a set of ordinals.
If $X$ has no largest element, then
\[
\sup X \notin X \subseteq \sup X,
\]
and $\sup X$ is the smallest ordinal $\alpha$ such that ...

**6**

votes

**1**answer

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

**3**

votes

**1**answer

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

**0**

votes

**1**answer

221 views

### Good set theory in which to study ordinal-indexed sequences?

I'd like to "model" the absolute complement of a set $X$ as the ordinal-indexed sequence $\alpha \mapsto V_\alpha \setminus X$ where $V_\alpha$ is the $\alpha$ stage of the cumulative hierarchy. My ...

**3**

votes

**1**answer

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

**17**

votes

**1**answer

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

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

**9**

votes

**1**answer

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

**4**

votes

**1**answer

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

**5**

votes

**3**answers

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

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