How can we construct ordinals after large Veblen?

[jacquesb]

The binary Veblen function $\varphi_\alpha(\beta)$ or $\varphi(\alpha,\beta)$ (see https://www.physicsforums.com/threa...-for-the-veblen-hierarchy-of-ordinals.933538/) can be generalized to finitely many variables, for example $\varphi(\alpha,\beta,\gamma)$ which can also be written $\varphi(\alpha_2,\beta_1,\gamma_0)$ (often written $\varphi(\gamma_0,\beta_1,\alpha_2)$ or $\varphi(0 \rightarrow \gamma, 1 \rightarrow \beta, 2 \rightarrow \alpha)$, but here I prefer to use reverse order to stay consistent with the convention I used for binary Veblen function). Indices represent the position of the variable, 0 may be ommited, for example $\varphi(\alpha,0,\beta)$ may be written $\varphi(\alpha_2,\beta_0)$. With this notation we can generalize Veblen function to transfinitely many variables with a finite number different from 0, for example $\varphi(1_\omega)$ which is the limit of $\varphi(1)=\varphi(0,1), \varphi(1,0), \varphi(1,0,0), \varphi(1,0,0,0), ...$. The set of all ordinals which can be reached with this Veblen function with transfinitely many variables (or the least ordinal which cannot be reached with it) is called the large Veblen ordinal.
For more explanations see for example :
- Wikipedia : https://en.wikipedia.org/wiki/Veblen_function
- Googology : http://googology.wikia.com/wiki/Ordinal_notation
- Veblen's article : http://www.ams.org/journals/tran/1908-009-03/S0002-9947-1908-1500814-9/S0002-9947-1908-1500814-9.pdf

My question is : is it possible to go further with this formalism ?

It seems that generally, when people want to go further, they use different formalism like Schütte's Klammersymbols or bracket, or ordinal collapsing functions, generally using $\Omega$, the first uncountable ordinal, to define countable ordinals. Is it because it is impossible to go furthen within the Veblen formalism, for example starting by enumerating the fixed points of $\alpha \rightarrow \varphi(1_\alpha)$ (the first one seems to me to be the large Veblen ordinal), or is it easier to use other formalisms beyond the large Veblen ordinal ?

 

[SSequence]

I am not familiar with (notational) conventions usually used for finitely many variables. However, a brief word of care w.r.t. the last link. I have read that the author uses $1$ instead of $0$ as the "first" value (as seemingly that was the convention at that time). Now a days, the standard is to start from $0$.

My question is : is it possible to go further with this formalism ?

It seems that generally, when people want to go further, they use different formalism like Schütte's Klammersymbols or bracket, or ordinal collapsing functions, generally using $\Omega$, the first uncountable ordinal, to define countable ordinals. Is it because it is impossible to go further within the Veblen formalism ... or is it easier to use other formalisms beyond the large Veblen ordinal ?

As I understand "Schütte's Klammersymbols or bracket" is not much different from a certain concrete realisation (of certain points reached through fixed point method). But I am completely unfamiliar with any of the specifics here, so someone could correct this if I am wrong.

Regarding your last sentence, it is the latter sentence that might be true perhaps.
For example, in your OP to the linked thread:
https://www.physicsforums.com/threa...-for-the-veblen-hierarchy-of-ordinals.933538/

The very first link you posted in the original post, you can see a number of other papers (posted online) by the same author.

 

[jacquesb]

(...) go further within the Veblen formalism, for example starting by enumerating the fixed points of $\alpha \rightarrow \varphi(1_\alpha)$ (the first one seems to me to be the large Veblen ordinal), (...) ?

Let me explain a bit more my idea.

We start with the large Veblen ordinal (LVO) which is the least fixed point of the function $\alpha \mapsto \varphi(1_\alpha)$, $\varphi(1_\alpha)$ representing the application of $\varphi$ with transfinitely many variables with 1 at position $\alpha$ and 0 anywhere else. Then we consider a function F which enumerates the fixed points of $\alpha \mapsto \varphi(1_\alpha)$. So we have LVO = F(0). The next fixed point F(1) is the limit of $LVO+1, \varphi(1_{LVO+1}), \varphi(1_{\varphi(1_{LVO+1})}), ...$

Then we can consider the fixed points of the function F and define a function G which enumerates these fixed points, then a function H which enumerates the fixed points of G, and so on.

This construction is similar to $\epsilon$ which enumerates the fixed points of $\alpha \mapsto \omega^\alpha$, $\zeta$ which enumerates the fixed points of $\epsilon$, $\eta$ which enumerates the fixed points of $\zeta$.

Like we have defined :
- $\varphi_0(\alpha) = \omega^\alpha$
- $\varphi_1(\alpha) = \epsilon(\alpha)$
- $\varphi_2(\alpha) = \zeta(\alpha)$
...
we can define :
- $\varphi'_0(\alpha) = F(\alpha)$
- $\varphi'_1(\alpha) = G(\alpha)$
- $\varphi'_2(\alpha) = H(\alpha)$

With this notation we can write $LVO = \varphi'_0(0)$.

Then $\varphi'_\alpha(\beta)$ can be written as a binary function $\varphi'(\alpha,\beta)$ which can be generalized to finitely many variables like $\varphi'(\alpha,\beta,\gamma)$ and transfinitely many variables like $\varphi'(1_\omega)$.

Then we can consider the fixed points of the function $\alpha \mapsto \varphi'(1_\alpha)$ and define a function $\varphi''_0$ which enumerates these fixed points.

The same way we can define $\varphi'''$, $\varphi''''$, ...

We can then introduce a new notation :
- $\Phi_0 = \varphi$
- $\Phi_1 = \varphi'$
- $\Phi_2 = \varphi''$
...

Then we can go on with for example the fixed points of $\alpha \mapsto \Phi_\alpha (1_\alpha)$ or something like that ...

These are just general ideas, there is still a lot of work to do to make it rigorous, like define the values of the different functions when applied to limit ordinals, define the fundamental sequences, prove that all of this is consistent...

Does this seem correct to you ? Do you think this could be an interesting research direction ? Do you know if some similar work has already be made ?

 

[SSequence]

I am not fully conversant with terminology conventions that are used, so I can't point out exactly whether there is an issue or not. You are right though that the process can be extended. However, it seems to me that the general direction (using fixed point approach) is covered in rather detailed way in the papers (described in post#2).
I haven't read any of them but this is the feeling I got from looking at them. And the process seems to be extended to rather very large points (using precise mathematical machinery).

============

Let me explain a bit what is going on with SVO and LVO so it should be somewhat clearer what is happening (I already described that in older thread but in words). Note though that there is a heavy personal aspect attached to it (important to emphasize because the description below doesn't describe anything fully precisely).

If you consider $\varphi_\alpha (\beta)$, then each function $\varphi_\alpha$ can be consider as a function from $\varphi_\alpha:\Psi \rightarrow \Psi$ in its own right.

We can think of a function $F:\Psi^2 \rightarrow \Psi$ that can be considered as storing each $\varphi_\alpha$ in the following way:
$\varphi_\alpha(\beta)=F(\Psi \cdot \alpha + \beta)$
Hence the function $F$ can be considered as a "storing function" in a way.

If we want to proceed to three variables we have a function $F:\Psi^3 \rightarrow \Psi$. We can think of the function $F$ as being defined by $\varphi(a,b,c)$ as:
$\varphi(a,b,c)=F(\Psi^2 \cdot a + \Psi \cdot b +c)$

To be precise, we would have to do following things:
(a) Describe the function $F$ in a precise way. This can be done either using a program (not ordinary ones) or give a mathematical description.
(b) Show that the functions stored in $F$ produced on each stage will be normal.
(c) Give a full or at least fully precise description of recursive well-order relation (in terms of finite+decidable symbol set) that is limit of the system.

Ideally a fully detailed description of hierarchy should achieve all the goals I "think" (quotation marks meaning it is just my feeling).

In a sense, the same thing is happening over and over again (suitable selection of points, point-wise limits and producing a normal function from that using appropriate modifications). It "seems" that probably selection of points is more sophisticated part generally.

If this process is defined in a certain specific way we have a function $F:\Psi^\omega \rightarrow \Psi$
where:
$\varphi(x_n,x_{n-1},...x_1,x_0)=F(\Psi^n \cdot x_n+\Psi^{n-1} \cdot x_{n-1}+...+\Psi \cdot x_1+x_0)$

SVO is then defined as $sup \{ F(\Psi^n) : n \in \mathbb{N}^+ \}$.

For LVO one will have to go well-beyond that. But, at any rate, if one proceeds with this in a certain systematic (and specific) manner, one can describe the storing function $F:\Psi^\Psi \rightarrow \Psi$. LVO would then be defined as the first fixed point of the function $f:\Psi \rightarrow \Psi$ defined as:
$f(x)=F(\Psi^x)$

 

[jacquesb]

If you consider $\varphi_\alpha (\beta)$, then each function $\varphi_\alpha$ can be consider as a function from $\varphi_\alpha:\Psi \rightarrow \Psi$ in its own right.

We can think of a function $F:\Psi^2 \rightarrow \Psi$ that can be considered as storing each $\varphi_\alpha$ in the following way:
$\varphi_\alpha(\beta)=F(\Psi \cdot \alpha + \beta)$
Hence the function $F$ can be considered as a "storing function" in a way.

What is $\Psi$ ?

 

[SSequence]

First ordinal which isn't countable (also denoted by $\omega_1$ sometimes I think).

 

[jacquesb]

First ordinal which isn't countable (also denoted by $\omega_1$ sometimes I think).

I never saw the notation $\Psi$ for the first uncountable ordinal, in everything I read it was denoted by $\Omega$.

Like we have defined :
- $\varphi_0(\alpha) = \omega^\alpha$
- $\varphi_1(\alpha) = \epsilon(\alpha)$
- $\varphi_2(\alpha) = \zeta(\alpha)$
...
we can define :
- $\varphi'_0(\alpha) = F(\alpha)$
- $\varphi'_1(\alpha) = G(\alpha)$
- $\varphi'_2(\alpha) = H(\alpha)$

With this notation we can write $LVO = \varphi'_0(0)$.

Finally I think it is more homogeneous to define :

- $\varphi'_0(\alpha) = \varphi(1_\alpha)$
- $\varphi'_1(\alpha) = F(\alpha)$
- $\varphi'_2(\alpha) = G(\alpha)$
- $\varphi'_3(\alpha) = H(\alpha)$
...

With this notation we can write $LVO = \varphi'_1(0)$.

 

[jacquesb]

There is another way to express my construction, using Veblen functions indiced by the function used for $\varphi_0$.

As SSequence noticed in https://www.physicsforums.com/threa...-for-the-veblen-hierarchy-of-ordinals.933538/ , there are different conventions for $\varphi_0(x)$, like $\omega^x$ or $\epsilon_x$. We can write explicitely the convention chosen for $\varphi_0$ by writing "$\varphi_f(\alpha,\beta)$" for "$\varphi_\alpha(\beta)$ with function f used for $\varphi_0$". With this notation we have:

- $\varphi_f(0,\beta) = f(\beta)$
- $\varphi_f(\alpha+1,\beta) = (1+\beta)$th fixed point of the function $\beta \mapsto \varphi_f(\alpha,\beta)$
- $\varphi_f(\lambda,\beta) = (1+\beta)$th common fixed point of the function $\beta \mapsto \varphi_f(\alpha,\beta)$ for all $\alpha < \lambda$, if $\lambda$ is a limit ordinal.
( See http://www.cs.man.ac.uk/~hsimmons/TEMP/OrdNotes.pdf )

Then we generalize the binary function $\varphi_f(\alpha,\beta)$ to finitely many variables: for example $\varphi_f(1,0,\alpha) = (1+\alpha)$th common fixed point of the function $\xi \mapsto \varphi(\xi,0)$ ( see https://en.wikipedia.org/wiki/Veblen_function ) and to infinitely many variables with a finite number of them different from 0, for example $\varphi_f(1_\omega)$.

Then we can define new $\varphi$ functions by taking for $\varphi_0$ the function $\xi \mapsto \varphi_f(1_\xi)$ and define functions $\varphi_{\xi \mapsto \varphi_f(1_\xi)}$ with 2 variables, with finitely many variables and with transfinitely many variables.

To make a correspondence with my previous construction, if f is the function $\xi \mapsto \omega^\xi$, then $\varphi_f(\alpha,\beta)$ corresponds to what I wrote $\varphi_\alpha(\beta)$, and $\varphi_{\xi \mapsto \varphi_f(1_\xi)}(\alpha,\beta)$ to $\varphi'_\alpha(\beta)$.

If we define the function S by $S(f)(\xi) = \varphi_f(1_\xi)$, then $\varphi_{\xi \mapsto \varphi_f(1_\xi)}$ can be written $\varphi_{S(f)}$. We can then consider $\varphi_{S(S(f))}$ and so on.

Given an ordinal $\alpha$, we can iterate transfinitely "$\alpha$ times" the application of S to an initial function $f_0$, for example $f_0(\xi) = \omega^\xi$, to obtain a function which I will write $S^\alpha(f_0)$. We can use this function to define a function $\varphi_{S^\alpha(f_0)}$ which permits to construct big ordinals.

We must verify that this function really permits to get greater and greater ordinals and does not get stucked in a loop, perhaps by verifying it is "fruitful" or "helpful" in the sense of http://www.cs.man.ac.uk/~hsimmons/TEMP/OrdNotes.pdf:
"An ordinal function $f \in Ord′$ is fruitful if it is inflationary, monotone, continuous, and big. Let Fruit be the class of fruitful functions.
An ordinal function $h \in Ord′$ is helpful if it is strictly inflationary, monotone, and strictly big. Let Help be the class of helpful functions."

If it is the case and if this construction is correct, there is probably a correspondence with the notations using ordinal collapsing functions, but for the moment I don't see how to establish it.

And after ? The next step could perhaps start by enumerating the fixed points of a function like $\xi \mapsto \varphi_{S^\xi}(1_\xi)$ or something like that ...

 

[SSequence]

As SSequence noticed there are different conventions for $\varphi_0(x)$, like $\omega^x$ or $\epsilon_x$.

The particular choice between $\omega^x$ or $\epsilon_x$ shouldn't matter in the long run, because even as soon as we get to $\omega$ stage the $\varphi_\omega$ functions are equal in both cases.

We can write explicitely the convention chosen for $\varphi_0$ by writing "$\varphi_f(\alpha,\beta)$" for "$\varphi_\alpha(\beta)$ with function f used for $\varphi_0$". With this notation we have:

- $\varphi_f(0,\beta) = f(\beta)$
- $\varphi_f(\alpha+1,\beta) = (1+\beta)$th fixed point of the function $\beta \mapsto \varphi_f(\alpha,\beta)$
- $\varphi_f(\lambda,\beta) = (1+\beta)$th common fixed point of the function $\beta \mapsto \varphi_f(\alpha,\beta)$ for all $\alpha < \lambda$, if $\lambda$ is a limit ordinal.
( See http://www.cs.man.ac.uk/~hsimmons/TEMP/OrdNotes.pdf )

Writing $(1+\beta)$-th instead of $\beta$-th seems redundant to me in both second and third equations (unless I have missed some context). Can you describe the exact page number where the author wrote these formulas?

...

If it is the case and if this construction is correct, there is probably a correspondence with the notations using ordinal collapsing functions, but for the moment I don't see how to establish it.

The author (for link above) has a number of other papers (about four or five) where at points he describes the correspondence between his approach (which seems to be a somewhat detailed and clearer description of fixed point approach) and the "closure" based approach (that's what collapsing looks like to me but I don't understand it nor have spent much time on it).

Generally speaking though, comparisons between different points obtained through different choices made (at various stages of storing function say) is likely to be very difficult.

And after ? ...

There is no end to it in principle. It seems to me that at some point (probably at some point beyond howard ordinal), higher uncountable values would have to be used (and if one uses $\omega_{CK}$, there would be somewhat different notions).

===========================

I feel that this is a danger with informal descriptions (instead of precise computation for the well-order relations). They can be good to understand a few basic ideas at times, but otherwise they have to be made mathematically precise (otherwise the value is lost).

But on the other hand, there also seems to be a real sharp discrepancy between describing a storing function (in post#4) for say $\Gamma_0$ and an description of actual computable less-than relation. The storing function can probably be described in a few hundred lines (mathematically or even programmatically). The same is not true for a less-than relation (see paragraph below).

The thing is that (at least it seems to me) that logicians have already devised very efficient systems for various elements (and I will admit ignorance for the specific reasons ...). This seems to me almost a necessity anyway (because of time). For example, if you look at reference(3) I posted in post#2 of the other thread (see post#2 of this thread), it seems that the author seemingly describes (at least that what I understood from heading) a well-ordering for $\mathbb{N}$ with order-type $\Gamma_0$.
I wouldn't be surprised that if you wrote that into a programming language and compared that with one produced through in a somewhat "exhaustive"/naive manner, the difference would be that of few hundred lines and thousands of lines (if not several thousand ... not to mention the enormous number of intermediate stages that are likely to be involved in a naive method ... that's how human beings generalise/visualise/understand in a natural manner). And the difference would likely becomes far more pronounced as you start to get higher.

============================

But this is actually a very interesting topic, generally speaking. That's partly because there seems to be no analogue to this topic (generally speaking) in maths****. @Deedlit might have something interesting to add to this discussion (or any other experts on this specific topic who might read this thread). I have already spent of a lot of time on these threads past few days, so I might not necessarily be able to reply promptly/quickly to further posts (I don't have much else to add to this topic anyway).

Also note that if you don't have a specific question or point, then repeated posts might lead to locking of a topic. Anyway, it is your thread so you can use it as you like. But my request is to make your posts in the first thread you made.
As I mentioned above, this is a very interesting topic (in a general sense), and normally I don't like to make a thread on a topic like this, but since a thread has been made ... it might be interesting to hear some different well-informed opinions on this.****The only type of analogue that I can think of might be whether there are always mathematically fully reliable techniques that can determine a non-recursive set using increasingly more sophistication. Such discussions usually just seem to become one philosophical position against other (say for number theory specifically, platonism versus unreliability of LEM) ... or which tradition is more likely to be adopted by mathematicians. But the question just mentioned shifts the focus from "ability" to do something to "principle techniques". If we take the question back to "ability" (which is what is under discussion for question in main post) it seems to turn into a rather vague discussion. Same old discussion ... can you reliably(mathematically) determine halt of first 1000 programs, 10000 programs, 100000 programs etc.

 

[jacquesb]

Writing $(1+\beta)$-th instead of $\beta$-th seems redundant to me in both second and third equations (unless I have missed some context). Can you describe the exact page number where the author wrote these formulas?

The author wrote these formulas in page 10 in a slightly different but equivalent form :
$\phi_f 0 = f$
$\phi_f(\alpha+1) =$ enumeration of fixed points of $\phi_f \alpha$
$\phi_f \lambda =$ enumeration of common fixed points of $\phi_f \alpha$ for all $\alpha < \lambda$

I rewrote these formulas introducing $1+\beta$ because of the usual language convention of starting with "first" ("1th") and not "0th". So the successive fixed points of the function $\beta \mapsto \varphi_f(\alpha,\beta)$ are :
- first : $\varphi_f(\alpha+1,0)$
- 2nd : $\varphi_f(\alpha+1,1)$
- 3rd : $\varphi_f(\alpha+1,2)$
- 4th : $\varphi_f(\alpha+1,3)$
...
- "$\omega$th" : $\varphi_f(\alpha+1,\omega)$
...
We can see that $\varphi_f(\alpha+1,\beta)$ is the $(1+\beta)$th fixed point.
I saw such definitions in different texts, for example https://en.wikipedia.org/wiki/Veblen_function .

 

[SSequence]

Now a days it is (almost) universal to start from 0-th element (this is what would be assumed in writing "enumeration"), so it would be better to use that for communication.

==============

Also ofc you can continue to post (though I think it would be better to take it to the other thread ... see the reason mentioned towards end of post#9 ... you can quote this post in the other thread if needed). But I don't understand the notational conventions that are usually made or assumed after finite variables, so I can't answer your question or point out specific issues (someone more knowledgeable probably can).

Still I don't understand what you are trying to do or say specifically. Let's assume that everything you wrote is correct. The thing is just going beyond LVO is not enough. You can do it in some kind of elementary way but that's not enough (that would only take you a "little far" ... good for experimentation but not as something concrete), since I already mentioned (and given you references) that people have gone "really far" beyond it (even using fixed point approach).
If your goal is a better understanding, then you might try to fill all the gaps (by reading papers or detailed references) and trying to understand (and possibly filling in on occasions) the proofs.

 

[jacquesb]

Also note that if you don't have a specific question or point, then repeated posts might lead to locking of a topic. Anyway, it is your thread so you can use it as you like. But my request is to make your posts in the first thread you made.

My two threads are not a repetition.
My first thread was about a specific technical question concerning the fundamental sequences of $\varphi_\alpha(\beta)$. I consider it as solved for me since the definitions I read seem plausible to me now.
My second thread is about the more general and vast topic of constructing ordinals beyond LVO within Veblen "style".
If it is a problem for you (why?) that I post in two threads, I prefer to post only in the second one now.
About the first topic, I'll perhaps have something to add concerning some definitions that I am studying of the binary Veblen function in programming languages ( http://isabelle.in.tum.de/website-Isabelle2017-RC2/dist/library/HOL/HOL-Induct/Ordinals.html , http://www.dcs.ed.ac.uk/home/pgh/ordinals.agda ) which seems equivalent to the definitions of the fundamental sequence that I read, but it could also be posted in the second thread since this subject has been evocated here and these definitions could be generalized to greater ordinals.
I also think of other readers who might be interested in the topic of my second thread but not in the first one, and who would miss some posts which would interest them if I post them in my first thread.

 

[SSequence]

Yes, I understand what you are saying makes sense (the first thread was indeed regarding a specific question and the second thread is a general one).

I had certain specific scope for both threads in my mind when I suggested that ... but I will leave the details. I probably might just make another thread maybe. Anyway, since you are the OP, it is ofc up to you to determine the scope of your own threads as you wish (it seems that you are probably more comfortable with the scope you identified in the above post).

 

[jacquesb]

Also ofc you can continue to post (though I think it would be better to take it to the other thread ... see the reason mentioned towards end of post#9 ... you can quote this post in the other thread if needed). But I don't understand the notational conventions that are usually made or assumed after finite variables, so I can't answer your question or point out specific issues (someone more knowledgeable probably can).

Still I don't understand what you are trying to do or say specifically. Let's assume that everything you wrote is correct. The thing is just going beyond LVO is not enough. You can do it in some kind of elementary way but that's not enough (that would only take you a "little far" ... good for experimentation but not as something concrete), since I already mentioned (and given you references) that people have gone "really far" beyond it (even using fixed point approach).
If your goal is a better understanding, then you might try to fill all the gaps (by reading papers or detailed references) and trying to understand (and possibly filling in on occasions) the proofs.

What I am trying to do now is first to understand what has already been done in the domain of ordinals construction, and then perhaps to go further.

I began studying some tutorial presentations of ordinals, for example :
- http://www.madore.org/~david/weblog/d.2011-09-18.1939.nombres-ordinaux-intro.html
- https://sites.google.com/site/largenumbers/home/4-2
- http://quibb.blogspot.fr/p/infinity-series-portal.html
but generally does not go very far, and technical articles are more difficult to read, so I found it easier to do the work myself, that's why I did it first, than to understand the work done by others, but I am not sure that what I did is correct. This is a problem with mathematics, unlike computing, where the computer tells you if your program is correct. That's why I began to study representations of ordinals in computer languages. I think that the syntax control of the language can perhaps not guarantee that your construction is entirely correct but at least highlight some inconsistencies. And I think it could be interesting, after having done my work, to compare it with other's work.

Concerning the references of people who have gone "really far", do you mean the papers written by Harold Simmons you mentioned before ? At first sight they seem interesting to me and I hope I'll find time to study them more deeply.
But are you sure that ordinals that can be built using the system of Simmons (or other existing systems) are bigger than, for example, the least fixed point of my function $\xi \mapsto \varphi_{S^\xi(f_0)}(1_\xi)$ ? How could you know it since, if I correctly understood, you are not even familiar with Veblen function with transfinitely many variables ?

 

[SSequence]

Concerning the references of people who have gone "really far", do you mean the papers written by Harold Simmons you mentioned before ? At first sight they seem interesting to me and I hope I'll find time to study them more deeply.
But are you sure that ordinals that can be built using the system of Simmons (or other existing systems) are bigger than, for example, the least fixed point of my function $\xi \mapsto \varphi_{S^\xi(f_0)}(1_\xi)$ ?

Yes I am sure. There isn't much to look (don't take this in a negative way). The author(who is also a serious mathematician) mentions that his method goes "well-beyond" the howard ordinal. And I am afraid you might be underestimating how far that goes in first place.

How could you know it since, if I correctly understood, you are not even familiar with Veblen function with transfinitely many variables ?

I believe I understand the storing function in post#4 (and even if I didn't, it wouldn't matter since the choice of points at each stage is an arbitrary matter ... as I mentioned before comparison between different choices can ofc get very difficult) and can reconstruct it in principle needed ... and hence also the underlying compuable well-order relation if needed (in principle). However, I don't feel the need to translate the well-order relation into some optimal form. I believe logicians have done that extremely well already and I could just read the relevant literature to learn that.

 

[jacquesb]

Yes I am sure. There isn't much to look (don't take this in a negative way). The author(who is also a serious mathematician) mentions that his method goes "well-beyond" the howard ordinal. And I am afraid you might be underestimating how far that goes in first place.

Where did you see that his method goes "well-beyond" the Howard ordinal ?
In http://www.cs.man.ac.uk/~hsimmons/ORDINAL-NOTATIONS/Fruitful.pdf , Simmons only speaks about "a method of producing ordinal notations `from below' (for countable ordinals up to the Howard ordinal)".

 

[SSequence]

It has been quite some time since I looked at those papers (and I have not studied them). So I guess maybe I didn't remember it fully well.

My main point still stands. I will repeat once again something that I have said before ... a naive method of extension (beyond any actually large value) won't go much far at all.

 

[jacquesb]

It has been quite some time since I looked at those papers (and I have not studied them). So I guess maybe I didn't remember it fully well.

My main point still stands. I will repeat once again something that I have said before ... a naive method of extension (beyond any actually large value) won't go much far at all.

What is exactly a "naive method of extension" ?

If Simmons ( http://www.cs.man.ac.uk/~hsimmons/ORDINAL-NOTATIONS/ordinal-notations.html ) really went much further than it is possible to go with my method, then the best would perhaps be to start where Simmons stopped and go further.
I already have an idea (which has to be formalized more precisely ofc) about how this could be done :
- Introduce a notation $[n...p] = [n] [n-1] ... [p+1] [p]$, where $[0] h = Fix (\alpha \mapsto h^\alpha 0), [1] H h = Fix (\alpha \mapsto H^\alpha h 0)$ , ... and $Fix f \zeta = f^\omega(\zeta+1)$. With this notation we have $\Delta[n+2] = [n...0] Next \ \omega$ where $Next = Fix (\alpha \mapsto \omega^\alpha)$
- Define $[\omega...0]$ by $[\omega...0] h \zeta =$ limit / least upper bound of $[0] h \zeta, [1] [0] h \zeta, [2] [1] [0] f \zeta, ...$
- Define $[\omega+1...0] = [1] [\omega...0]$
- Define $[\omega+2...0] = [2] [1] [\omega...0] = [2...1] [\omega...0]$
- ...
- By generalizing the previous definitions, define recursively $[\alpha...0]$ for any ordinal alpha
- Consider the fixed points of $\alpha \mapsto [\alpha...0] Next \ \omega$

 

[jacquesb]

I noticed a correspondence between Veblen functions and Madore's $\psi$ collapsing function.

$\psi(\alpha)$ is defined as the least ordinal not in $C(\alpha)$, where $C(\alpha)$ is the set of all ordinals constructible using only 0, 1, $\omega$, $\Omega$ and addition, multiplication, exponentiation, and the function $\psi$ restricted to ordinals smaller than a, and $\Omega$ is the least uncountable ordinal.
For more information see :
https://en.wikipedia.org/wiki/Ordinal_collapsing_function
http://quibb.blogspot.fr/2012/03/infinity-impredicative-ordinals.html.

To distinguish between the different Veblen functions, let us call $\varphi_F$ the Veblen function with finitely many variables, and $\varphi_T$ the Veblen function with transfinitely many variables.

$\varphi_F$ is a function which, when applied to a list of countable ordinals, gives a countable ordinal. A list of countable ordinals can be seen as a function which, when applied to a natural number, gives a countable ordinal, with the restriction that the result differs from 0 for finitely many integers. If we denote $\omega$ the set of natural numbers and $\Omega$ the set of countable ordinals, then this can be written : $\varphi_F : (\omega \rightarrow \Omega) \rightarrow \Omega$. If we replace $\alpha \rightarrow \beta$ by $\beta^\alpha$, we get $\Omega^{\Omega^\omega}$, and if we apply $\psi$ to it, we get $\psi(\Omega^{\Omega^\omega})$, which is the small Veblen ordinal, the least ordinal that cannot be reached using $\varphi_F$.

For $\varphi_T$, the position of a variable is represented by a countable ordinal instead of a natural number, also with the restriction that finitely many variables differ from 0, so we have $\varphi_T : (\Omega \rightarrow \Omega) \rightarrow \Omega$. If we replace $\alpha \rightarrow \beta$ by $\beta^\alpha$, we get $\Omega^{\Omega^\Omega}$, and if we apply $\psi$ to it, we get $\psi(\Omega^{\Omega^\Omega})$, which is the large Veblen ordinal, the least ordinal that cannot be reached using $\varphi_T$.

Is it a coincidence or is there a deep reason for it ?

Is it possible to extrapolate this correspondence and define a generalization of the Veblen function whose limit would be $\psi(\Omega^{\Omega^{\Omega^\Omega}})$, and the "position" of a variable would be a function which gives a countable ordinal when applied to a countable ordinal, and so on, up to the Howard ordinal, which is the limit of $\psi(\Omega), \psi(\Omega^\Omega), \psi(\Omega^{\Omega^\Omega}), ...$ ?