The ordinal-numbers tag has no wiki summary.

**4**

votes

**0**answers

69 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

80 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

380 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

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

**19**

votes

**1**answer

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

**27**

votes

**1**answer

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

**10**

votes

**0**answers

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

**8**

votes

**3**answers

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

**12**

votes

**1**answer

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

**4**

votes

**1**answer

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

**6**

votes

**2**answers

433 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

628 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

422 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

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

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

**2**

votes

**1**answer

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

**7**

votes

**1**answer

324 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

316 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

410 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

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

**12**

votes

**1**answer

601 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

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

**5**

votes

**1**answer

208 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

326 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

188 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

273 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

942 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

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

**7**

votes

**1**answer

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

**6**

votes

**1**answer

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

**4**

votes

**1**answer

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

**7**

votes

**2**answers

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

**6**

votes

**1**answer

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

**4**

votes

**3**answers

490 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

**2**answers

293 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

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

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

554 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

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

**13**

votes

**1**answer

416 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

**1**answer

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

**1**

vote

**1**answer

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

**5**

votes

**1**answer

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

**1**

vote

**0**answers

296 views

### Transfinite Sums Related to a Sequence

Hello,
Given a sequence $S$ indexed by the finite ordinals, a limit ordinal $\alpha$, and $k \in \mathbb{N}$, define $S_{\alpha+k}$(the extension of $S$ to $\alpha+k$) to be the sum over the products ...

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

**13**

votes

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