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.

learn more… | top users | synonyms

17
votes
0answers
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 ...
9
votes
0answers
263 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 ...
6
votes
0answers
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
0answers
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
0answers
101 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
0answers
37 views

Does the rank (=height) of a well partial order bound its type (=length, =stature)?

Terminology and context (This should all be standard, but is recalled because terminology sometimes varies, and also to put the question into perspective.) A partially ordered set is called well-...
1
vote
0answers
312 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 ...