Expressive power of a simple ordinal notation

[Marek]

I would be much obliged for hints and/or pointers to literature that could
help me with solving the following problems:

Consider a signature consisting of:

constants 0 and \omega
unary successor function S
binary functions A (addition), M (multiplication) and E (exponentiation).

It is well known that for every ordinal number less that epsilon-zero there is
a (finite, closed) term over this signature that denotes it. This is immediate
via Cantor normal forms.
The above signature can be enriched by adding the ternary operator \beth
representing the stacking function (denoted here by B), defined by transfinite
recursion on the third argument by:

B(\alpha, \beta, 0) = \alpha
B(\alpha, \beta, \gamma + 1) = \beta^{B(\alpha, \beta, \gamma)}
B(\alpha, \beta, \lambda) = lim_{\xi < \lambda}(B(\alpha, \beta, \xi) (for a
limit ordinal \lambda)

Now consider the set I consisting of all ordinal numbers that have (finite)
denotations over the extended signature. I is a set because of course the
signature is relatively weak and obviously cannot express any uncountable ordinal.

Problem 1: Show that I is downward closed, that is for any ordinals \alpha and
\beta with \alpha < \beta and \beta \in I, \alpha \in I holds as well. In
other words, prove that I is an ordinal number in the sense of von Neumann.

Problem 2: What is the value of sup(I)? Of course sup(I) = I under the
conjecture stated above, but this is not what I'm asking about. By analogy
with epsilon-zero I would expect sup(I) to be the limit of the sequence

B(\omega, \omega, \omega), B(\omega, \omega, B(\omega, \omega, \omega)), etc

Problem 3: If the above number is denoted by \eta and indeed sup(I) = \eta,
then how is \eta expressed by standard ordinal notations?

Best regards,

Marek

[Dave L. Renfro]

Marek wrote:

[[ Snip comments and questions about higher-order
transfinite "ordinal-epsolon" numbers ]]

Several of my posts in the following Jan-Feb 2002 sci.math
thread might be of use. Note that the Math Forum version
includes some of my posts that the google thread doesn't
have. However, since not all of the special characters
(e.g. something like ü) in my posts came out very well
in the Math Forum archive, I'm including the google
archive also.

"My number is bigger than yours."
http://mathforum.org/kb/thread.jspa?threadID=77834
http://groups.google.com/group/sci.math/browse_frm/thread/e79f0a771162261e

You will also want to look at the following papers,
which should be almost exactly what you're looking for.

John Donner and Alfred Tarski, "An extended arithmetic of
ordinal numbers", Fundamenta Mathematicae 65 (1969), 95-127.
http://matwbn.icm.edu.pl/tresc.php?wyd=1&tom=65

Arthur Rubin and Jean Rubin, "Extended operations and
relations on the class of ordinal numbers", Fundamenta
Mathematicae 65 (1969), 227-242.
http://matwbn.icm.edu.pl/tresc.php?wyd=1&tom=65

Arthur Rubin and Jean Rubin, "Accumulation functions
on the ordinals", Fundamenta Mathematicae 70 (1971), 205-220.
http://matwbn.icm.edu.pl/tresc.php?wyd=1&tom=70

And, if anyone is interested, yes ... this is the
same Arthur Rubin that Archimedes Plutonium has
been driveling on about in connection with Euclid's
proof that there are infinitely many prime numbers.
I think Arthur was 15 years old when the first paper
of his above was written, by the way.

Dave L. Renfro

[Marek]

Dave L. Renfro wrote:
> [...]

Thank you very much for your reaction. It is somehow funny that being Polish I
am referred to a Polish journal...

The pointers you gave are undoubtedly applicable to my problems 2&3 and I am
going to read those papers carefully, but they hardly say anything about my
question #1: isn't the stacking function too "crude" in the sense that the
"gaps" it leaves are too big to be "filled" with the accessible finer
operations? (The quotes indicate a very informal reformulation of the original
question). Do you have any hints/intuitions about it?

Thanks again,

Marek

[David Bernier]

Dave L. Renfro wrote:
> Marek wrote:
>
> [[ Snip comments and questions about higher-order
> transfinite "ordinal-epsolon" numbers ]]
>
> Several of my posts in the following Jan-Feb 2002 sci.math
> thread might be of use. Note that the Math Forum version
> includes some of my posts that the google thread doesn't
> have. However, since not all of the special characters
> (e.g. something like ü) in my posts came out very well
> in the Math Forum archive, I'm including the google
> archive also.
>
> "My number is bigger than yours."
> http://mathforum.org/kb/thread.jspa?threadID=77834
> http://groups.google.com/group/sci.math/browse_frm/thread/e79f0a771162261e
>

[...]

I was reading your post in the
"My number is bigger than yours." thread
dated:
Sun, 20 Jan 2002 18:23:40 +0000 (UTC)
with:
Message-ID: <xukng4jaiocm@legacy>

[BTW: The link
http://mathforum.org/epigone/sci.math/flelsmingsnix/zmhi097wz96w@legacy
now redirects to http://mathforum.org/kb/forum.jspa?forumID=13 ... ]

Suppose we give these definitions for integers n>=0:

--------------------------------------
f_0(n) := n+1
f_{k+1} (0) := f_{k} (1)
f_{k+1} (n+1) := f_{k}( f_{k+1}(n) ).

and then one can define:

f_o (n) = f_{n} (n) , n in N, "o" for omega.
-------------------------------------
(A variation on the Ackerman function)

f_k, k in N and f_o are totally recursive.

How does one procede to define f_alpha for alpha>omega,
and for which alpha is f_alpha totally recursive?

David Bernier

[Dave L. Renfro]

Marek wrote (in part):

> The pointers you gave are undoubtedly applicable to my
> problems 2&3 and I am going to read those papers carefully,
> but they hardly say anything about my question #1: isn't
> the stacking function too "crude" in the sense that the
> "gaps" it leaves are too big to be "filled" with the
> accessible finer operations? (The quotes indicate a very
> informal reformulation of the original question). Do you
> have any hints/intuitions about it?

I've been busy the past few days, but I thought I'd let you
and David Bernier (who also had a question) know that I'll
get back to this in a few days. I have over 60 pages of very
carefully written notes from a series of talks that I gave
on the Donner/Tarski paper, and some related topics, back
in 1991-92. I was able to locate those notes this past
weekend. When I get the chance, I'll see what I can say
about the questions you two asked.

Dave L. Renfro

[Marek]

Dave L. Renfro wrote:
> I've been busy the past few days, but I thought I'd let you
> and David Bernier (who also had a question) know that I'll
> get back to this in a few days. I have over 60 pages of very
> carefully written notes from a series of talks that I gave
> on the Donner/Tarski paper, and some related topics, back
> in 1991-92. I was able to locate those notes this past
> weekend. When I get the chance, I'll see what I can say
> about the questions you two asked.

Perfect. Thanks in advance,

Marek

[Dave L. Renfro]

Marek wrote:

http://groups.google.com/group/sci.math/msg/a008e0742b131d99

> The pointers you gave are undoubtedly applicable to my
> problems 2&3 and I am going to read those papers carefully,
> but they hardly say anything about my question #1: isn't
> the stacking function too "crude" in the sense that the
> "gaps" it leaves are too big to be "filled" with the
> accessible finer operations? (The quotes indicate a very
> informal reformulation of the original question). Do you
> have any hints/intuitions about it?

You asked if a certain set of ordinals is downward
closed, meaning (as you put it) that given any ordinal
belonging to the set, then all smaller ordinals also
belong to the set. I can't tell from how you defined
your set "I". It seems to me that it will depend on
what alpha and beta are. Are they even required to
be countable ordinals? I think if you're interested
in these sorts of issues that it's better to pick
a notational system that someone has already worked
on, study that, and then work out the details of a
different system of your own choice. More than likely,
however, I think you'll find that whatever purpose
you had in mind for your system can be taken care
of by one of the two that I have in mind. One is the
system that Doner and Tarski use in the paper I
previously mentioned. Another is a standard notational
system used in proof theory -- at least, it's fairly
standard for ordinals less than gamma_0, which is
way beyond anything I think you're talking about.

Here are a couple of my sci.math posts that didn't
make it to the google archive which might be of
interest:

"My number is bigger than yours." (February 11, 2002)
http://mathforum.org/kb/thread.jspa?messageID=358519

"Different size infinities?" (October 29, 2004)
http://mathforum.org/kb/thread.jspa?messageID=3414869

For more about the ordinal notation system used in
proof theory, see the following paper:

Stephen G. Simpson, "Unprovable theorems and fast-growing
functions", Contemporary Mathematics 65 (1987), 359-394.

The text of Simpson's paper (posted by Bill Dubuque)
can be found at

http://groups.google.com/group/sci.math/msg/7ed034c97ed64f2c

Finally, the following google searches will take you
to a large number of things that you will likely find
interesting and useful:

http://www.google.com/search?q=ordinal+gamma_0

http://www.google.com/search?q=impredicative+ordinal

http://groups.google.com/groups?q=ordinal+gamma_0

http://groups.google.com/groups?q=impredicative+ordinal

http://books.google.com/books?q=impredicative+ordinal

Dave L. Renfro

[Dave L. Renfro]

David Bernier wrote (in part):

> Suppose we give these definitions for integers n>=0:
>
> --------------------------------------
> f_0(n) := n+1
> f_{k+1} (0) := f_{k} (1)
> f_{k+1} (n+1) := f_{k}( f_{k+1}(n) ).
>
> and then one can define:
>
> f_o (n) = f_{n} (n) , n in N, "o" for omega.
> -------------------------------------
> (A variation on the Ackerman function)
>
> f_k, k in N and f_o are totally recursive.
>
> How does one procede to define f_alpha for alpha>omega,
> and for which alpha is f_alpha totally recursive?

I don't know much about recursive function theory,
but I think the proof-theoretic method of naming
ordinals less than gamma_0 will be what you want.
The Ackerman function is the w'th level operation,
and gamma_0 is the first ordinal such that

max {alpha, beta, eta } < gamma_0

implies the eta'th operation applied to the pair
(alpha, beta) will be less than gamma_0.

See the references in the reply I just made to
Marek's post in this thread.

Dave L. Renfro

[Marek]

Dave,

Thanks again for the pointers. I will continue investigating these problems on
my own.
I probably should have mentioned earlier that these issues are not of central
importance to my research. Solving them would, however, be a very nice and
natural addition to my master thesis that I am currently writing. Switching to
a notation that have been extensively studied would probably be a good
"solution", but it is impossible at this point. I will, however, try harder to
solve my problems in an elementary way and if it fails and time permits, I
will turn to study another notational system and its implications for mine,
just as you suggested.
Now to the specific question you asked:

> You asked if a certain set of ordinals is downward
> closed, meaning (as you put it) that given any ordinal
> belonging to the set, then all smaller ordinals also
> belong to the set. I can't tell from how you defined
> your set "I". It seems to me that it will depend on
> what alpha and beta are. Are they even required to
> be countable ordinals?

\alpha and \beta are variables used in the definition of B. They can be 0,
\omega, or anything you can build from 0 and \omega using the given
operations: S, A, M, E, B. It is definitely expected that all the expressible
ordinals are countable, and very likely below \Gamma_0.

Best,

Marek

[David Bernier]

Dave L. Renfro wrote:
> David Bernier wrote (in part):
>

[...]

>> How does one procede to define f_alpha for alpha>omega,
>> and for which alpha is f_alpha totally recursive?
>
> I don't know much about recursive function theory,
> but I think the proof-theoretic method of naming
> ordinals less than gamma_0 will be what you want.
> The Ackerman function is the w'th level operation,
> and gamma_0 is the first ordinal such that
>
> max {alpha, beta, eta } < gamma_0
>
> implies the eta'th operation applied to the pair
> (alpha, beta) will be less than gamma_0.
>
> See the references in the reply I just made to
> Marek's post in this thread.

I checked Bill Dubuque's 1996 post in text format:
http://groups.google.com/group/sci.math/msg/7ed034c97ed64f2c?dmode=source

The part I liked most was Section 2, "Embeddability of finite trees";
it has a bearing on the question of how large an ordinal
alpha can be if f_alpha is to be recursive...

Th. 2.2, "Friedman's finite form of Kruskal's Theorem", is
an existence result for finite sequences of finite
rooted trees where the size of the i'th tree is no larger
than c*i for a predetermined c. The size of a tree T_i
is denoted | T_i | in Th. 2.2 ; I'm not sure what is counted.
Perhaps the number of vertices of T_i? In any case,
given c, if the length of a sequence of trees of size
bounded by c*i is at least n_c, then there will always
be a tree which can be embedded in a tree appearing
(strictly) after in the sequence. This (minimal possible)
n_c can be thought of as depending on the integer c.
So there exists a sequence of n_c - 1 trees
(T_1, ... T_i, ... T_{n_c -1}), of size bounded by c*i
where no T_i is embeddable in a T_j with j>i.

Simpson's paper (as reproduced by Bill Dubuque) mentions
the Wainer hierarchy; quoting from B. Dubuque's post:

"It can then be shown that f_{G_0} is eventually dominated by the
Friedman function n_c (as a function of c)."

What is clear is that n_c is a recursive function, and it
eventually dominates f_{G_0} ; btw, Simpson refers to
f_{G_0} as the "Wainer function".

Simpson's paper refers frequently to [37] which I've
recopied below.

In an on-going thread, "Harvey Friedman on Cantorian...",
David Petry quoted from:

http://www.cs.nyu.edu/pipermail/fom/2006-January/009526.html

(a Foundation of Mathematics post by Friedman).

The FOM post alludes to recent results in Boolean Relation Theory (BRT)
depending on large cardinal axioms. Some may be interested
in Feferman's presentation "Does Mathematics need new axioms?"

http://math.stanford.edu/~feferman/papers/ASL2000R.pdf

The Bibliography from Feferman's paper looks interesting
for anyone interested in logic/foundations/philosophy etc.

David Bernier

[37] S. G. Simpson, Nonprovability of certain combinatorial
properties of finite trees, in: Harvey Friedman's Research in the
Foundations of Mathematics, edited by L. Harrington, M. Morley, A.
Scedrov, and S. G. Simpson, North-Holland, l985, pp. 87-117.