918: Tangible Incompleteness and Clique Construction/2

[Harvey Friedman]

We presented four algorithms in
https://cs.nyu.edu/pipermail/fom/2021-December/023018.html A1(G,x,n),
A2(G,x,n), A1'(G,x,n), A2'(G,x,n).

We now start over. We organize these differently, with some
modifications, and also add A3, and A3' corresponding to 1-Con.

We also eliminate the parameter n in the algorithm presentation. All
of the algorithms can be carried out for infinitely many steps, but
the issue is whether the execution is successful. The variable n comes
in when we ask for the execution to be successful while the pointer is
at or before position n.

A1-A3 are based on a single algorithm. The criteria for success
varies: A1 easier than A2 easier than A3.

A1'-A3' differ from A1-A3 in just "z<y" inserted at one spot.
Otherwise A1'-A3' are identical to A1-A3, with the exact same criteria
for success. The reversals for A2',A3' are easier than for A2,A3.

THE BASIC A1(G,x)
G a graph on Q^k
x in Q^k

At every stage we have a sequence x1,...,xr from Q^k and a pointer at
position i pointing to xi.

We say that y is blocked by x1,...,xn if and only if x1,...,xn,y is
not a clique in G.

We choose a "pointer length" of execution for the algorithm. Infinite
pointer length is self explanatory. Pointer length n means that there
is computation as long as the pointer is at position <= n. In this
case, we stop just before the pointer is about to be moved to position
n+1. It will be clear that the pointer starts at position 1 and moves
to the right one position at a time, with an upper bound on the number
of steps the pointer stays at a given position, exponential in that
position and the dimension k.

Initialization. Use length 1 sequence x, with pointer at position 1.

Execution. We have x1,...,xr with pointer at position 1 <= i <= r.
case 1. Some y in fld(x1,...,xi)^k\{x1,...,xn} isn't blocked by
x1,...,xr,. Choose any such y. Transition to x1,...,xr,y or any
x1,...,xr,z  which does block y.
case 2. Else i < r. Advance the pointer to position i+1.
case 3. Else i = r. Transition to x1,...,xr,xr and advance the pointer
to position r+1.

Note that this algorithm can be executed by always setting z to be y.
The same will be true of all of these algorithms. The real question is
whether or not the execution is what we call successful.

Success. Success of execution means that the set of vertices yielded
by the execution is a clique in G.

A2(G,x)
G a graph on Q^k
x in Q^k
for Con(SRP)

The upper shift ush(x) of x in Q^k is obtained from x by adding 1 to
every nonnegative coordinate of x.

Same as A1(G,x), only the criteria for success is UPGRADED.

Success. Success of execution means that the set of vertices yielded
by the execution, together with their upper shifts, is a clique in G.

A3(G,x)
G a graph on Q^k
for 1-Con(SRP)
x in Q^k

Same as A1(G,x), only the criteria for success is further UPGRADED.

Infinite sequences alpha are said to be controlled if and only if
there is a longest finite length of a subsequence of alpha, alpha[n1]
> ... > alpha[ns], such that each n_i+1 is in (ni,2^ni) .

If we choose infinite pointer length, and alpha is the infinite
sequence from Q^k that is yielded, then success means that after we
construe alpha as an infinite sequence beta of rational numbers, there
is a longest length of a subsequence of beta, of the form beta[n1] >
... > beta[ns], with each n_i+1 is in (ni,2^ri) .

Suppose we choose finite pointer length n. Let alpha be the finite
sequence from Q^k yielded, and let alpha be construed as the sequence
beta of rational numbers. Let #(beta) be the longest length of a
subsequence of beta[n1] > ... > beta[ns] such that each n_i+1 is in
(ni,2^ni) .Then for success we require that #(beta) < log log log n.

THEOREM 1. (RCA0) Let G be a graph on Q^k. Let  x
be adjacent, in G, to every y in Q^k\{x}. Then executing A1(G,x) for
infinite pointer length by
always setting z to be whatever y is chosen, is always successful and
ends with an infinitely repeated vertex.

The execution above is called the Greedy Execution.

THEOREM 2. (WKL_0) The following are equivalent.
i. Let G be an order invariant graph on Q^k. Let x be adjacent to
every y in Q^k\{x}. A2(G,x)  can be executed successfully with
infinite pointer length.
ii.  Let G be an order invariant graph on Q^k. Let x be adjacent to
every y in Q^k\{x}. For all n, A2(G,x)  can be executed successfully
with pointer length n.
iii. Let G be an order invariant graph on Q^k. Let x be adjacent to
every y in Q^k\{x}. A2(G,x)  can be executed successfully with pointer
length 2.
iv. Con(SRP).
WIthout i, EFA suffices. For i implies iv, RCA_0 suffices.
The greedy execution may result in failure even with pointer length 2.

THEOREM 3. (WKL_0) The following are equivalent.
i. Let G be an order invariant graph on Q^k. Let x be
adjacent to every y in Q^k\{x}. A3(G,x)  can be executed successfully
for infinite pointer length.
ii.Let G be an order invariant graph on Q^k. Let x be
adjacent to every y in Q^k\{x}. There exists n such that A3(G,x) can
be executed successfully with pointer length n.
iii. 1-Con(SRP).
WIthout i, EFA suffices. For i or ii implies iii, RCA_0 suffices.

THEOREM 4. The least n in Theorem 3ii as a function G,x is a provably
recursive function of SRP+ that eventually dominates every provably
recursive function of SRP.

We now turn to A1'(G,x), A2'(G,x), A3'(G,x). These are identical to
A1,A2,A3 except that in case 1 of Execution, put "z < y" before "which
does block y".

Theorems 1-3 remain the same. The reversals in Theorems 2,3 are easier
for A2',A3'.

Theorem 2ii,iii are explicitly Pi02. However, they become explicitly
Pi01 when double exponential bounds are placed on the heights of the
rationals allowed during execution in terms of the heights of the
rationals in x and the dimension k. Alternatively, it is clear that
for each choice of G,x, the conclusion is an instance of the decision
procedure for (a fragment of) the first order theory of  (Q,<,+,1).

Theorem 3ii is explicitly Pi02.


##########################################

My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 918th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-899 can be found at
http://u.osu.edu/friedman.8/foundational-adventures/fom-email-list/

900: Ultra Convergence/2  10/3/21 12:35AM
901: Remarks on Reverse Mathematics/6  10/4/21 5:55AM
902: Mathematical L and OD/RM  10/7/21  5:13AM
903: Foundations of Large Cardinals/1  10/12/21 12:58AM
904: Foundations of Large Cardinals/2  10/13/21 3:17PM
905: Foundations of Large Cardinals/3  10/13/21 3:17PM
906: Foundations of Large Cardinals/4  10/13/21  3:17PM
907: Base Theory Proposals for Third Order RM/1  10/13/21 10:22PM
908: Base Theory Proposals for Third Order RM/2  10/17/21 3:15PM
909: Base Theory Proposals for Third Order RM/3  10/17/21 3:25PM
910: Base Theory Proposals for Third Order RM/4  10/17/21 3:36PM
911: Ultra Convergence/3  1017/21  4:33PM
912: Base Theory Proposals for Third Order RM/5  10/18/21 7:22PM
913: Base Theory Proposals for Third Order RM/6  10/18/21 7:23PM
914: Base Theory Proposals for Third Order RM/7  10/20/21 12:39PM
915: Base Theory Proposals for Third Order RM/8  10/20/21 7:48PM
916: Tangible Incompleteness and Clique Construction/1  12/8/21   7:25PM
917: Proof Theory of Arithmetic/1  12/8/21  7:43PM

Harvey Friedman