[FOM] 501: Embedded Maximal Cliques 4

[Harvey Friedman]

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING BUILDS ON

introductory remarks at
http://www.cs.nyu.edu/pipermail/fom/2012-September/016692.html

preliminary sections 1,2 at
http://www.cs.nyu.edu/pipermail/fom/2012-September/016695.html

sections 3 - 8 at http://www.cs.nyu.edu/pipermail/fom/2012-September/016698.html

WE FIRST REPEAT THE ABSTRACT AND GIVE A TABLE OF CONTENTS FOR THE
CONVENIENCE OF THE READER.

(the abstract has been slightly changed, and the title of section 9 in
the table of contents has been changed)

Abstract. Every order invariant graph on Q≥0^k has an f embedded
maximal clique, where f is +1 on {0,...,n}. Every order invariant
graph on Q≥0^k has an f embedded maximal clique, where f is +1 on
{0,...,n} extended by the identity on Q>n+1. We give a proof of the
first statement within the usual ZFC axioms for mathematics. We give a
proof of the second statement (and more general statements) that goes
well beyond ZFC, and establish that ZFC does not suffice (assuming ZFC
is consistent). As a consequence of the Gödel completeness theorem,
both statements are Π01. We present statements about finite cliques that are
explicitly Π01. These predict that certain computer searches will
result in actual certificates. Computer investigations are discussed
which may indicate how these predictions can be argued to provide
confirmation of the consistency, or pragmatic consistency, of ZFC and
some of its far reaching extensions.

1. Graphs, cliques, embeddings.
2. Order invariant and order theoretic.
3. OIG(J,f).
4. OIG(J,f1,...,fn).
5. OIG characterizations
6. Total embeddings.
7. n-invariance.
8. General conjectures.
9. Finite cliques.
10. Extremely strong statement.
11. Computational aspects.

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

EMBEDDED MAXIMAL CLIQUES continued

*9. Finite cliques.*

We present a nondeterministic algorithm that generates an LSH[n]
embedded clique in any given order invariant graph on Q>=0^k, in
infinite many steps. It may not be a maximal clique, but it will be a
maximal clique in the subgraph induced by some A^k ⊆ Q^k.

There are many ways to carry out the construction for a while, only to
get blocked at the next stage. However, using Proposition 3.4, it is
possible to continue the construction for infinitely many steps.

Because of the purely order theoretic nature of the construction, we
see that it is possible to carry out the construction for infinitely
many steps if and only if it is possible to carry out the construction
for any given finite number of steps.

Thus we arrive at the explicitly Π01 sentence "the construction can be
carried out for t steps".

Now for the details. The field of a sequence is the set of its terms.

We present the nondeterministic algorithm ALG(k,n,G,t), where k,n ∈
Z+, t ∈ Z+ ∪ {∞}, and G is an order invariant graph on Q≥0^k.

1. Initialize c to 1. Initialize α to be the empty sequence.. Go to 2.

2. Let α = α1,...,αr. If {α1,...,αr} is not a clique, yield ERROR (and
stop). If c = t, HALT. Otherwise, go to 3.

3. Choose x ∈ (fld(α1) ∪ ... ∪ fld(αc) ∪ {0,...,n+2})^k, outside
{α1,...,αr}, such that {α1,...,αr,x} is a clique. Choose y ∈ Q≥0^k
such that x,y are not adjacent. Update α to α followed by
y,LSH[n](y),LSH[n]^-1(y), where only defined terms are appended. Go to
2. If x cannot be so chosen, update c to c+1, and go to 2.

PROPOSITION 9.1. ALG(k,n,G,∞) can be carried out without ERROR.

PROPOSITION 9.2. ALG(k,n,G,t), t < ∞, can be carried out without ERROR.

PROPOSITION 9.3. Let G be an order invariant graph on Q≥0^k. The
subgraph induced by some A^k ⊆ Q≥0^k has an LSH[n] embedded maximal
clique.

THEOREM 9.4. Theorems 3.5, 3.6 apply to Propositions 9,1 - 9.3. For
Proposition 9.2, EFA can be used instead of WKL0.

On the face of it, Proposition 9.2 is explicitly Π02 since there is no
explicit control over the numerators and denominators of the rationals
that are used. However, the statement is purely order theoretic, with
constants 0,...,n+1. So obvious upper bounds can be placed on the
numerators and denominators, resulting in an explicitly Π01 sentence.

*10. Extremely strong statement.*

We use ∪. for disjoint union. We say that two functions are comparable
if and only if their graphs are comparable under inclusion.

A cube in Q^k is a set E^k, E ⊆ Q.

Let A ⊆ Q^k. For x ∈ Q^i, 1 ≤ i < k, we define the cross section Ax =
{y ∈ Qk-i: (x,y) ∈ A}.

We say that h nontrivially embeds A below p ∈ Q if and only if

i. h is a one-one function from fld(A) ∩ (-∞,p) into itself.
ii. there exists q ∈ dom(h) such that h(q) ≠ q.
iii. for all x1,...,xk ∈ dom(h), (x1,...,xk) ∈ A ↔ (h(x1),...,h(xk)) ∈ A.

Let R ⊆ Q^2k. We define R<B = {y ∈ Q^k: (∃x ∈ B)(max(x) < max(y) ∧ R(x,y))}.

PROPOSITION 10.1. For every order invariant R ⊆ Q^2k there exists a
cube A ∪. R<B in Q^k, where the B_x, x ∈ N^k-2, nontrivially embed A
below min(x), with the same fixed points.

The following is proved using the completeness theorem for first order
predicate calculus.

THEOREM 10.2. Proposition 10.1 is provably equivalent to a Π01
sentence over WKL0.

We now present the well known relevant formal systems.

I3 is ZFC + (∃κ,j)(j is a nontrivial elementary embedding of V(κ) into V(κ)).

I2 is NBG + AxC + (∃j,M,κ,λ)(M is a transitive class, j:V → M is a
nontrivial elementary embedding with critical point κ, j(λ) = λ > κ,
and V(λ) ⊆ M).

THEOREM 10.3. Proposition 10.1 is provable in I2 and ACA' + Con(I2),
but not in any consistent fragment of I2 that proves RCA0. Proposition
10.1 is not provable in ZFC + Con(I3), provided ZFC + Con(I3) is
consistent.

*11. Computational aspects.*

We make modifications in ALG(k,n,G,t) with the expectation of creating
significant engagement with abstract set theory in a real computer.

For such engagement, we use n-invariance instead of LSH[n] embedding.
We write n[x] for the equivalence class of x ∈ Q≥0^k under
n-equivalence.

We fix parameters k,n,m ≥ 1.

1. Create a random set E ⊆ {(x,y): x ≠ y ∧ x,y ∈ {1,...,2k}^k ∧
{x1,...,xk,y1,...,yk} forms an initial segment of {1,...,2k}}, where E
of cardinality m. Form the order theoretic graph G on Q≥0^k whose
adjacency relation is {(x,y): x,y ∈ Q≥0^k ∧ (x,y) or (y,x) is order
equivalent to an element of E}. Go to 2.

2. Initialize α to be the empty sequence, Go to 3.

3. Let α = α1,...,αr. If n[α1] ∪ ... ∪ n[αr] is not a clique, yield
ERROR (and stop). Otherwise, go to 4.

4. Choose x ∈ (fld(α1) ∪ ... ∪ fld(αr) ∪ {0,1,...,n,n+1})^k by the
following randomized algorithm. First choose 0 ≤ i ≤ k randomly. Then
randomly choose i elements of {0,...,n+1}, repetitions allowed, and
place them randomly in i of the k positions of x. Then randomly choose
the remaining k-i coordinates of x from fld(α1) ∪ ... ∪ fld(αr) so
that they are strictly greater than all of the i elements already
placed in x that are not n+1 (repetitions allowed). (Use n+1 if this
is impossible). If x is not adjacent to some αj, then go to 4.
Otherwise, choose y ∈ Q≥0^k such that x,y are not adjacent, update α
to α,y, and go to 3.

There are some ambiguities in this setup that need to be addressed. We
do want to have feasibly exponential searches here which are practical
for small parameters.

The number of order invariant graphs on Q^k grows very rapidly, and so
unless k is 2, or possibly 3, we want to fix a single graph G(k,m)
generated by step 1.

Also, for 4, we want to use a fixed pseudorandom function that
generates the initial placement of some numbers 0,...,n+1 in positions
of x, from r.

The placement of the remaining rationals in x should be by a fixed
pseudorandom function applied to the set fld(α1) ∪ ... ∪ fld(αr),
where the elements are processed only in terms of their positions in
the strictly increasing enumeration.

The goal is to run the algorithm above, to generate "long"
certificates α1,...,αr.

For a given r, there is an obvious tree of finite sequences that can
be constructed, and the vertices can be tested according to 3. Once a
vertex does not pass 3, the part of the tree emanating from it does
not have to be constructed. We look for a leaf that passes 3. These
are the desired certificates.

This is the right kind of setup for NP problems. However, there is an
issue with 3. If n or r is appreciable, then testing whether n[α1] ∪
... ∪ n[αr] is a clique can take up too much resources.

In this case, we use randomized testing for being a clique, randomly
generating many pairs to test for adjacency. To the extent that we
weaken 3 this way, we may be able to create lower quality but longer
certificates α1,...,αr.

We know from Con(SRP) that for any positive integers k,n,m, and no
matter what random number generators are used, arbitrarily long
certificates α1,...,αr do exist.

However, we can place a much stronger requirement on certificates
α1,...,αr. We can require that if we use a different pseudorandom
generator, then we can find another certificate β1,...,βr such that 3
holds in the stronger sense that n[α1] ∪ ... ∪ n[αr] ∪ n[β1] ∪ ... ∪
n[βr] is a clique. The second pseudorandom generator can of course be
the same as the first pseudorandom generator but with a different
initialization or setting. The different setting should be generated
by a suitable physical process (e.g., looking at a fast clock) AFTER
the first certificate α1,...,αr was produced.

We know that these strong certificates α1,...,αr,β1,...,βr exist. The
reason is that we can start with an n-invariant maximal clique in G,
using Con(SRP). However, we have no idea how to actually find such a
strong certificate.

As these certificates are actually produced (not the stronger ones),
we can view them as providing highly nontrivial indisputably verified
predictions made by mathematical methods going well beyond the usual
ZFC axioms for mathematics. (The prediction is that certain algorithms
will in fact create certificates). In fact, the consistency of the
underlying set theoretic principles suffice to make these predictions
- i.e., Con(SRP).

We can go further and discuss how these highly nontrivial indisputably
verified predictions constitute confirmation of the consistency of
these underlying principles. This is beyond the scope of the
discussion.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 501st 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-449 can be found
in the FOM archives at
http://www.cs.nyu.edu/pipermail/fom/2010-December/015186.html

450: Maximal Sets and Large Cardinals II  12/6/10  12:48PM
451: Rational Graphs and Large Cardinals I  12/18/10  10:56PM
452: Rational Graphs and Large Cardinals II  1/9/11  1:36AM
453: Rational Graphs and Large Cardinals III  1/20/11  2:33AM
454: Three Milestones in Incompleteness  2/7/11  12:05AM
455: The Quantifier "most"  2/22/11  4:47PM
456: The Quantifiers "majority/minority"  2/23/11  9:51AM
457: Maximal Cliques and Large Cardinals  5/3/11  3:40AM
458: Sequential Constructions for Large Cardinals  5/5/11  10:37AM
459: Greedy CLique Constructions in the Integers  5/8/11  1:18PM
460: Greedy Clique Constructions Simplified  5/8/11  7:39PM
461: Reflections on Vienna Meeting  5/12/11  10:41AM
462: Improvements/Pi01 Independence  5/14/11  11:53AM
463: Pi01 independence/comprehensive  5/21/11  11:31PM
464: Order Invariant Split Theorem  5/30/11  11:43AM
465: Patterns in Order Invariant Graphs  6/4/11  5:51PM
466: RETURN TO 463/Dominators  6/13/11  12:15AM
467: Comment on Minimal Dominators  6/14/11  11:58AM
468: Maximal Cliques/Incompleteness  7/26/11  4:11PM
469: Invariant Maximality/Incompleteness  11/13/11  11:47AM
470: Invariant Maximal Square Theorem  11/17/11  6:58PM
471: Shift Invariant Maximal Squares/Incompleteness  11/23/11  11:37PM
472. Shift Invariant Maximal Squares/Incompleteness  11/29/11  9:15PM
473: Invariant Maximal Powers/Incompleteness 1  12/7/11  5:13AMs
474: Invariant Maximal Squares  01/12/12  9:46AM
475: Invariant Functions and Incompleteness  1/16/12  5:57PM
476: Maximality, CHoice, and Incompleteness  1/23/12  11:52AM
477: TYPO  1/23/12  4:36PM
478: Maximality, Choice, and Incompleteness  2/2/12  5:45AM
479: Explicitly Pi01 Incompleteness  2/12/12  9:16AM
480: Order Equivalence and Incompleteness
481: Complementation and Incompleteness  2/15/12  8:40AM
482: Maximality, Choice, and Incompleteness 2  2/19/12 7:43AM
483: Invariance in Q[0,n]^k  2/19/12  7:34AM
484: Finite Choice and Incompleteness  2/20/12  6:37AM__
485: Large Large Cardinals  2/26/12  5:55AM
486: Naturalness Issues  3/14/12  2:07PM
487: Invariant Maximality/Naturalness  3/21/12  1:43AM
488: Invariant Maximality Program  3/24/12  12:28AM
489: Invariant Maximality Programs  3/24/12  2:31PM
490: Invariant Maximality Program 2  3/24/12  3:19PM
491: Formal Simplicity  3/25/12  11:50PM
492: Invariant Maximality/conjectures  3/31/12  7:31PM
493: Invariant Maximality/conjectures 2  3/31/12  7:32PM
494: Inv Max Templates/Z+up, upper Z+ equiv  4/5/12  4:17PM
495: Invariant Finite Choice  4/5/12  4:18PM
496: Invariant Finite Choice/restatement  4/8/12  2:18AM
497: Invariant Maximality Restated  5/2/12 2:49AM
498: Embedded Maximal Cliques 1  9/18/12  12:43AM
499. Embedded Maximal Cliques 2  9/19/12  2:50AM
500: Embedded Maximal Cliques 3  9/20/12  10:15PM

Harvey Friedman