916: Tangible Incompleteness and Clique Construction/1

[Harvey Friedman]

We are starting to get back to Tangible Incompleteness having been
interrupted mainly with writing a very long paper on Emergence of
(Strict) Reverse Mathematics, which should be done within a week or
two.

As you can see from 890 and 894, links... , I have decided to use
finite length nondeterministic algorithms for explicitly Pi01 and Pi02
Tangible Incompleteness.

But I want to improve on this expositionally and strategically. This
will be very friendly for graph theorists and theoretical computer
scientists.  I will use the graph/clique language and also use a
pointer.

*******************************

DEFINITION 1. A graph is a pair G = (V,E), where V is a set of
vertices and E is an irreflexive symmetric subset of V^2. E is
considered to be the set of edges of G.. Vertices x,y are adjacent if
and only if (x,y)

DEFINITION 2. A clique in a graph is a set of vertices where any two
distinct elements are adjacent.

DEFINITION 3. In graph G on Q^k, x1,...,xn blocks y if and only if
{x1,...,xn,y} is not a clique in G.

DEFINITION 4. fld(x1,...,xn) is the set of all coordinates of the x1,...,xn.

THE BASIC ALGORITHM
A1(G,x,n)
G graph on Q^k
x in Q^k, 1 <= n <= omega

Here is A1(G,x,n):.

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

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

Execution. We have x1,...,xr with pointer at xi, 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. Otherwise. Just advance the pointer to position i+1 if i+1 <=
r,n, else STOP.

Success. Success of execution means that the set of vertices yielded
by the execution, be it finite or infinite, is a clique in G.

THEOREM 1. (RCA0) Let G be a graph on Q^k and 1 <= n <= omega. Let  x
be adjacent, in G, to every y in Q^k\{x}. Then executing A1(G,x,n) by
always setting z to be whatever y is chosen, is always successful and
with a STOP.

This is called the Greedy Execution.

THE SRP LEVEL ALGORITHM
A2(G,x,n)
G graph on Q^k
x in Q^k, 1 <= n <= omega

DEFINITION 5. The upper shift of x in Q^k is obtained from x by adding
1 to all nonnegative coordinates. It is written ush(x).

A2(G,x,n) is identical to A1(G,x,n) except that the criteria for
success is strengthened as follows.

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

DEFINITION 6. G is order invariant if and only if its edge set E is an
order invariant subset of Q^2k. Here order invariant means that for
all order equivalent x,y in Q^2k, x in E iff y in E.

THEOREM 2. (WKL_0) Let G be an order invariant graph on Q^k and 1 <= n
<= omega. Let x be adjacent to every y in Q^k\{x}. The following are
equivalent.
i. A2(G,x,omega)  can be executed successfully.
ii. A2(G,x,2) can be executed successfully.
iii. Con(SRP).
WIthout i, EFA suffices. For i implies iii, RCA_0 suffices.
The Greedy Execution may lead to failure.

There is a slight modification of A1 and A2 with the same results. The
reversal for this modified A2 is considerably easier.

DEFINITION 7. In graph G on Q^k, x1,...,xn lower blocks y if and only
if the set of elements of {x1,...,xn,y} whose max is at most max(y) is
not a clique in G.

A1'(G,x,n) and A2'(G,x,n) are identical to A1(G,x,n) and A2(G,x,n)
except we replace "blocked" by "lower blocked" and "block" by "lower
block".

We will be using lower block only as we move to HUGE Level Algorithms
in Tangible Incompleteness and Clique Construction/2.

Note that

"for all order invariant graphs G on Q^k and x adjacent to every y in
Q^k\{x} and 1 <= n < infinity, A2(G,x,n) can be executed successfully"

is a Pi02 sentence. However, it is a sentence in the first order
theory of (Q,<,+1) with a known decision procedure, and so in that
sense it is really a Pi01 sentence. Alternatively, we can bound the
numerators and denominators of the rationals used in successful
executions in terms of the numerators and denominators used in x,
resulting in an explicitly Pi01 sentence that is equivalent over EFA.

Instead of using just the upper shift here to strengthen the criteria
for success, we can template this by using other functions quantifier
free definable over (Q,<,+1), or even use functions first order
definable over (Q,Z,<,+). We conjecture that we can effectively decide
the metamathematical status of the resulting statements.

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

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 916th 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

Harvey Friedman