FOM: 19:Long Sequences

[Harvey Friedman]

This is the 19th in a series of self contained postings to fom
covering a wide range of topics in f.o.m. Previous ones are:

1:Foundational Completeness   11/3/97, 10:13AM, 10:26AM.
2:Axioms  11/6/97.
3:Simplicity  11/14/97 10:10AM.
4:Simplicity  11/14/97  4:25PM
5:Constructions  11/15/97  5:24PM
6:Undefinability/Nonstandard Models   11/16/97  12:04AM
7.Undefinability/Nonstandard Models   11/17/97  12:31AM
8.Schemes 11/17/97    12:30AM
9:Nonstandard Arithmetic 11/18/97  11:53AM
10:Pathology   12/8/97   12:37AM
11:F.O.M. & Math Logic  12/14/97 5:47AM
12:Finite trees/large cardinals  3/11/98  11:36AM
13:Min recursion/Provably recursive functions  3/20/98  4:45AM
14:New characterizations of the provable ordinals  4/8/98  2:09AM
14':Errata  4/8/98  9:48AM
15:Structural Independence results and provable ordinals  4/16/98 10:53PM
16:Logical Equations, etc.  4/17/98  1:25PM
16':Errata  4/28/98  10:28AM
17:Very Strong Borel statements  4/26/98  8:06PM
18:Binary Functions and Large Cardinals  4/30/98  12:03PM

A complete archiving of fom, message by message, is available at
http://www.math.psu.edu/simpson/fom/
Also, my series of positive postings (only) is archived at
http://www.math.ohio-state.edu/foundations/manuscripts.html

Here is the abstract from a paper in preparation.

LONG FINITE SEQUENCES
by
Harvey M. Friedman
Ohio State University
friedman at math.ohio-state.edu
www.math.ohio-state.edu/~friedman/

ABSTRACT

Let k be a positive integer. There is a longest finite sequence
x_1,...,x_n in k letters such that for no i < j <= n/2 is x_i,...,x_2i a
subsequence of x_j,...,x_2j. Let n(k) be this longest length. We prove
that n(1) = 3, n(2) = 11, and n(3) is incomprehensibly large. We give a
lower bound for n(3) in terms of the familiar Ackerman hierarchy. We
also give a much larger lower bound for n(4) involving extensions of
the Ackerman hierarchy (formulated here without the use of ordinals).
In addition, we give upper and lower bounds for n(k). We view n(3) as a
particularly elemental description of an incomprehensibly large
integer. Related problems involving binary sequences (two letters) are
also addressed.

********

This is the version of the Ackerman hierarchy that we use: For
n,m >= 1, we define A_n(m) as follows. A_1(m) = 2m, A_n+1(m) =
A_nA_n...A_n(1), where there are m applications of A_n. Thus A_1 is
doubling, A_2 is exponentiation, and A_3 is tower exponentiation.

The Ackerman function itself is defined as A(n) = A_n(n).

We perform a few illustrative calculations.

A_3(1) = 2. A_3(2) = 4. A_3(3) = 16. A_3(4) = 2^16 = 65,536. A_3(5) =
2^65,536.

A_4(1) = 2. A_4(2) = A_3A_3(1) = A_3(2) = 4. A_4(3) = A_3A_4(2) =
A_3(4) = 2^16 = 65,536. A_4(4) = A_3A_4(3) = A_3(65,536), which is an
exponential tower of 2 of height 65,536.

I submit that A_4(4) is a ridiculously large number, but it is not an
incomprehensibly large number. One can imagine a tower of 2 of a
large height, where that height is 65,536, and 65,536 is not
ridiculously large.

However, if we go much further, then a profound level of
incomprehensibility emerges. The definitions are not incomprehensible,
but the largeness is incomprehensible. These higher levels of largeness
blur, where one is unable to sense one level of largeness from
another.

It seems safe to assert that, say, A5(5) = A(5) is incomprehensibly large. We
propose this number as a sort of benchmark. In section 4 we prove that
n(3) > A7(184) > A(7).

A draft of the proof that n(3) > A7(184) has been completed.

The statement "for all k, n(k) exists" is provable in 3-quantifier
induction but not in 2-quantifier induction. Any proof that n(3) exists
in, say, exponential function arithmetic, must be of length much
greater than, say, A5(5). Any proof that n(4) exists in 1-quantifier
induction (or even RCA_0) must be of length much greater than, say,
A5(5). These proofs of course exist by exhaustion.

The function n = n(k) is at the level omega^omega in the Wainer
hierarchy, where the Ackerman function is of level omega. In terms of
what I we call descent recursion in: Friedman/Sheard, Elementary Descent
Recursion and Proof Theory, Annals of Pure and Applied Logic, 71 (1995),
pp. 1-45, the Ackerman function is an omega^omega descent recursive
function, whereas n = n(k)
is an omega^(omega^omega) descent recursive function.

We also give upper and lower bounds for n(k), in terms of these
hierarchies of functions. We also present the relevant hierarchies of
functions in purely combinatorial terms without talking about ordinals.
The lower bound for n(4) is qualitatively far greater than the lower
bound given for n(3), and cannot be reasonsably described in terms of
composites of the Ackerman function, in a precise sense. Actually, n(4) is
much bigger than this last sentence would suggest.