FOM: Re:Comments and queries on Friedman's last 3 posts

[Harvey Friedman]

Shipman 11:58AM 11/11/98 writes:

>Long Walks:
>
>What I like about this is the nonelementary growth of something that is
>so easy to picture geometrically.  The idea of a walk
>with steps of length <=3 in Z^3 is about as intuitive as you can get

In three dimensions I don't get anything nonelementary - just a lower bound
of a stack of 7 2's. See below.

>(though it would be REALLY nice if the length could be reduced to <2,
>which would be equivalent to requiring steps which didn't change any
>coordinate by more than 1).

There is |x-y| < 2 in the Euclidean norm, and there is |x-y| = 1 in the sup
norm. These get the same results, only with somewhat less stack of 2's.
I.e., one still climbs the Ackerman hierarchy as the dimensions go up, but
in three dimensions, one gets an exponential stack of fewer than 7. Now,
there is some fat in my lower bounds, and so I expect this to become a
smaller exponential stack but with numbers greater than 2 in it. So when
exapnded out, in the case of starting at (1,1,1), the lower bound may well
creep up to, say, an exponential stack of 2's of length 6. In any case, it
will still be wildy large even in 3 dimensions. This is the kind of detail
I wanted to postpone until I got the time to go over this very carefully,
and post it in the special series of postings.

>What is the growth rate w.r.t. x of the longest non-outward walk from
>(x,x,x) using steps of Euclidean length <2?

Some very enormous function (but elementary) of x. Same with sup norm 1.

>As the dimension goes up this gets harder to picture and one might as
>well go to the n(k) function to get incomprehensible growth.

I don't fully agree with this. They seem to have interest independently of
each other; both are valuable. Walks in Z^k are fundamental enough in their
own right. There is a huge mathematical tradition of automatically doing
things in k dimensions.

Incidentally, you can get incomprehensible growth by looking at even just
binary sequences. Look at the results about the functions m(k) and B(k) at
the end of special posting 24.

>Q-systems and Proof-Theoretic Ordinals:
>
>This is the most accessible representation I've ever seen of a
>significant portion of the large cardinal "scale".  It is not quite
>"ordinary mathematics" but the concept of definability is about as
>ingratiating to non-logicians as a logical concept can be.

In each case, there is only one assertion, which is extremely accessible
except for one invocation of definability.

Nevertheless, they are not directly combinatorial, and I will be making
some major postings on the fom about a new round of improvements in that
direction.

>It's too bad that you can't bootstrap these results.  You have several
>results of the form
>
>"Con(ZFC+kappa_i) implies Thereexists a Q-system satisfying i implies
>Con(ZFC+lambda_i )"
>
>where kappa_i<lambda_i, but the intervals (kappa_i,lambda_i) don't
>overlap enough that you can combine these to get a result of the form
>
>"Con(ZFC + something small) implies Thereexist Q-systems satisfying
>1,2,...,i implies Con(ZFC+something big)".

Such "results" are always impossible. You can never go from Con(ZFC +
something small) to Con(ZFC + something big). This is because of Godel's
2nd incompleteness theorem and the fact that Con(ZFC + something big)
always implies Con(ZFC + Con(ZFC + something small)). This is in turn
because "something big" always implies Con(ZFC + something small).

You may like what I did in this connection, but I am not a magician.

>Predicatively Infeasible Integers:
>
>By far the nicest thing here is the connection between long sequences
>and labeled trees, so that n(3) can be transformed into an impredicative
>integer by changing "unary" to "binary".  Once you have the picture of
>long sequences from {0,1,2} and the embeddability criterion, it is easy
>to imagine the sequences bifurcating into trees.

Yes. But as far as a pi-0-2 sentence is concerned that cannot be proved
predicatively, I still prefer the forms in special posting 22, and its
modifications in special posting 24. And therefore it is important for me
to also use these for the purpose of getting to predicative unfeasibility.

By the way, is "predicatively infeasible" better English than
"predicatively unfeasible"?

>Harvey, what is your best upper bound for n(3)?
>
I wanted to post on this, after I took a good look at it. At the moment, it
is safe to say that I can do AA(5) > n(3). However, I expect to be able to
do  better. Also, n(4) cannot be written involving A's and constants with
the number of A's and the sum of the constants < A(5).