Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with ordinal-numbers
Search options not deleted
user 1946
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.
21
votes
Accepted
Why isn't this a computable description of the ordinal of ZF?
Theorem. The following are equivalent.
The relation on $\mathbb{N}$ computed by your program P is a well-order.
ZF is $\Pi^1_1$-sound.
Proof. You gave the argument for the reverse implication $( …
- 236k
19
votes
Accepted
How strong are large cardinal properties of Ord?
$\newcommand{\Ord}{\text{Ord}}
\newcommand{\ZFC}{\text{ZFC}}$
Here is one way to formalize your concept a little more tightly,
which provides the answers to your questions. For any large
cardinal pro …
- 236k
19
votes
What is the idea behind stationary sets?
One answer to your question about intuition is simply that stationary sets arise very naturally once you begin to think of the natural measure surrounding club sets. The stationary sets are simply tho …
- 236k
18
votes
Accepted
Ordinals and complexity classes
There is no such recursive ordinal, because in fact every computable ordinal is the order type of a polynomial time computable relation on $\mathbb{N}$. In other words, the least ordinal not describab …
- 236k
16
votes
Accepted
Finding the largest integer describable with a string of symbols of predefined length
My first remark is that if you allow players to pick their own theories, but only allow consistent theories to win, then you will not be able to compute the winner of the contest. The reason is that t …
- 236k
15
votes
Order type of the smallest set containing the identity function and closed under exponentiation
This is a partial answer, and I am unsure about part of it.
I claim that these functions are well-ordered by eventual
domination, and the order type is at most the ordinal $\epsilon_0$.
First, your …
- 236k
14
votes
Accepted
Cardinality of $\omega\uparrow^\omega\omega$
The Knuth arrow notation is most often defined only on the natural numbers, but the central idea of it
can be easily extended to the ordinals, for example as follows:
$$\alpha\uparrow^0\beta=\alpha\b …
- 236k
14
votes
Accepted
What is the least ordinal than cannot be embedded in $\mathbb{R}^\mathbb{R}$?
Let me get things started with some simple observations.
Note that given any countable sequence of functions $f_n$, we can
by diagonalization construct a function eventually dominating all
of them, $ …
- 236k
14
votes
Accepted
Peano arithmetic vs. fast-growing hierarchy with pathological fundamental sequences
The answer is no. Choose a fundamental sequence for $\epsilon_0$ itself in the usual way, which I think is $\epsilon_0[n]=\omega^{\omega^{{\vdots}^\omega}}$, and then modify the earlier fundamental se …
- 236k
12
votes
Ramsey Theorem for the class ORD
Ali Enayat and I have proved that with respect to definable classes, Ord is NOT weakly compact. In particular, we show, in every model of ZFC,
there is a definable Ord-tree with no definable cofina …
- 236k
12
votes
Accepted
Ways to define "definability"
I am glad to see this question, Hans, which I believe gets right to the heart of the definability concept, on which some of your recent questions have focused. This is an excellent question.
First, l …
- 236k
11
votes
Accepted
Prime numbers and limit ordinals
The ordinals below $\omega^2$ are exactly those of the form $\omega\cdot n+k$ for natural numbers $n$ and $k$. Thus, these are the ordinals having two digits in base $\omega$, and counting to $\omega^ …
- 236k
11
votes
Accepted
Which part(s) of this proof of Goodstein's Theorem are not expressible in Peano arithmetic?
Because your argument involves arithmetical classes at several points, as you noticed, it is not directly expressible in the first-order language of $\newcommand\PA{\text{PA}}\PA$, although as Noah me …
- 236k
10
votes
Accepted
Surreal numbers, ultrapowers of $\Bbb R$, ordinal-valued functions and the slow-growing hier...
This kind of analysis is very well understood in ultrapowers, and one often sees this kind of thinking with ultrapowers, where one performs calculations with the representing function for an object. W …
- 236k
10
votes
Formalizations of The Matchstick Diagram Representation of Ordinals
I prefer to think of the matchstick representations a little differently than you present them. Namely, your function $f$ provides the amount to jump up by at each step, the difference between each ma …
- 236k