[FOM] 829: Tangible Incompleteness Restarted/3
Harvey Friedman
hmflogic at gmail.com
Mon Sep 23 23:20:20 EDT 2019
We now move from general discussion to mathematical specifics.
TANGIBLE INCOMPLETENESS
1. BOOLEAN RELATION THEORY - my website
2. INVARIANT MAXIMALITY
2.1. Emulation Theory - here
2.1.1. N, Z+, Q, Q[(a,b)], order equivalent, maximal emulator,
invariance, similarity - here
2.1.2. Invariant Maximal Emulation - here (statement)
2.2. Invariant Graph Theory - here
2.2.1. Graphs, order invariant graphs, cliques - here
2.2.2. Invariant Maximal Cliques - here (statement)
2.3. A...,A Classes - #3
2.3.1. (Q,<,rels) - #3
2.3.2. (D,<,rels), D containedin Q - #3
2.3.3. (D,<,fcns), D containedin Q - #3
2.3.4. (D,<,...), D containedin Q - #3
2.4. A...AE...E Clases - #3
2.4.1. (Q,<,rels) - #3
2.4.2. (D,<,rels), D containedin Q - #3
2.4.3. (D,<,fans), D containedin Q - #3
2.4.4. (D,<,...), D containedin Q - #3
3. SEQUENTIAL CONSTRUCTIONS - in development
################
2.1.1. N, Z+, Q, Q[(a,b)], ORDER EQUIVALENT, EMULATOR, INVARIANCE
DEFINITION 2.1.1.1. N, Z+, Q are, respectively, the set of all
nonnegative integers, the set of positive integers, and the
rationals.We use n,m,r,s,t,i,j,k, with or without subscripts, for
positive integers unless otherwise indicated. We use a,b,c,d,p,q, with
or without subscripts, for rationals unless otherwise indicated. We
use Q(a,b),Q(a,b],Q[a,b),Q[a,b] for Q intersected with
(a,b),(a,b],[a,b),[a,b] respectively. U. indicates disjoint union.
I.e., A U. B is A U B if A,B are disjoint; undefined otherwise.
(x_1,...,x_r) is the concatenation of the finite sequences
x_1,...,x_r.
DEFINITION 2.1.1.2. x,y in Q^k are order equivalent if and only if for
all i,j <= k, x_i < x_j iff y_i < y_j. S is an emulator of E
containedin Q[-n,n]^k if and only if S containedin Q[-n,n]^k, and for
all x,y in S, (x,y) is order equivalent to some (z,w) in E^2. S is a
maximal emulator of E containedin Q[-n,n]^k if and only if there is no
S U. {x} which is an emulator of E containedin Q[-n,n]^k.
Note how we are using E containedin Q[-n,n]^k to indicate that E is
drawn from the ambient space Q[-n,n]^k. The emulators of E do not
depend on the ambient space but the maximal emulators of E generally
depend on the ambient space.
THEOREM 2.1.1.1. Let E containedin Q[-n,n]^k. Every subset of an
emulator of E is an emulator of E. There exists finite E' containedin
E such that E containedin Q[0n,n]^k and E' containedin Q[-n,n]^k have
the same emulators. In fact, E' can be taken to be of cardinality at
most (8kn)!!. E has a maximal emulator.
We now come to invariance. We give a standard very general treatment.
DEFINITION 2.1.1.3. Let B containedin X. Let R be a binary relation
(set of ordered pairs). B is R invariant if and only if for all x,y in
X with x R y, we have x in B implies y in B. B is completely R
invariant if and only if for all x,y in X with x R y, we have x in B
iff y in B.
Note how we are using B containedin X to indicate that B is drawn from
the ambient space X.
THEOREM 2.1.1.2. Let B containedin X and R be a binary relation.
i. If R is symmetric then B is R invariant if and only if B is
completely R invariant.
ii. B containedin X is (completely) R invariant if and only if B
containedin X is (completely) R intersect X^2 invariant.
A particularly important case is where R is an equivalence relation.
We will be using a fundamental equivalence relation N tail related
(see 2.1.2 below).
THEOREM 2.1.1.2. B containedin X is R invariant if and only if B
containedin X is R* invariant, where R* is the least transitive
relation containing R intersect X^2. B containedin X is completely R
invariant if and only if B containedin X is R** invariant, where R**
is the least equivalence relation on X containing R intersect X^2,
2.1.2. N TAIL, N TAIL SHIFT, N TAIL RELATED
DEFINITION 2.1.2.1. The N tail of x in Q^k consists of the x_i such
that all x_j >= x_i lie in N. We view the N tail of x as a
distinguished part of x that is held in place.
DEFINITION 2.1.2.2. The N tail shift of x in Q^k is the k-tuple
obtained by adding 1 to the N tail of x.
According to Definition 2.1.1.3, we have N tail shift invariance and
complete N tail shift invariance.
There is a closely related fundamental equivalence relation on Q^k.
DEFINITION 2.1.2.3. x,y in Q^k are N tail related if and only if x,y
are order equivalent and agree off of their N tails.
2.1.2. INVARIANT MAXIMAL EMULATION
We now present our two lead statements in Emulation theory.
EMULATION 1. Every finite E containedin Q[-n,n]^k has a completely N
tail shift invariant maximal emulator.
EMULATION 2. Every finite E containedin Q[-n,n]^k has an N tail
related invariant maximal emulator.
In light of Theorem 2.1.1.1, we can remove "finite" without any effect.
THEOREM 2.1.2.1. Emulation 1,2 are implicitly Pi01 via Goedel's
Completeness Theorem.
THEOREM 2.1.2.2. Emulation 1,2 are provably equivalent to Con(SRP)
over WKL_0. They each imply Con(SRP) over RCA_0.
There is a clear sense in which we cannot improve on the equivalence
relation of N tail related.
THEOREM 2.1.2.3. (RCA_0) Let R be a binary relation on Q^k which
includes N tail related, but also relates some x,y in Q[-n,n]^k that
are not N tail related. Then the following is false. Every finite E
containedin Q[-n,n]^k has an R invariant maximal emulator.
2.2.1. ORDER INVARIANCE, GRAPHS, CLIQUES
DEFINITION 2.2.1.1. Let A containedin Q^k. A is order invariant if and
only if for all order equivalent x,y in Q^k, x in A iff y in A, More
generally, let A containedin B containeeidn Q^k. A is order invariant
if and only if for all order equivalent x,y in B, x in A iff y in A.
Thus here we treat B as the ambient space for A.
DEFINITION 2.2.1.2. A graph G is a pair (V,E) where V is a set, E
containedin V^2, E is symmetric and irreflexive. I.e., (v,w) in E iff
(w,v) in E, (v,v) notin E. V is the set of vertices and E is the set
of edges (ordered pairs). We say that G is a graph on V. A clique in G
is an S containedin V such that for all distinct x,y in S, (x,y) in E.
Let G be a graph on Q[-n,n]^k. G is order invariant if and only if its
edge set E containedin Q[-n,n]^2k is order invariant.
2.2.2. INVARIANT MAXIMAL CLIQUES
CLIQUES 1. Every order invariant graph on Q[-n,n]^k has a completely N
tail shift invariant maximal clique.
CLIQUES 2. Every order invariant graph on Q[-n,n]^k has an N tail
related invariant maximal clique.
THEOREM 2.2.2.1. Cliques 1,2 are implicitly Pi01 via Goedel's
Completeness Theorem.
THEOREM 2.2.2.2. Cliques 1,2 are provably equivalent to Con(SRP) over
WKL_0. They each imply Con(SRP) over RCA_0.
There is a clear sense in which we cannot improve on the equivalence
relation of N tail related.
THEOREM 2.2.2.3. (RCA_0) Let R be a binary relation on Q^k which
includes N tail related, but also relates some x,y in Q[-n,n]^k that
are not N tail related. Then the following is false. Every order
invariant graph on Q[-n,n]^k has an R invariant maximal clique.
************************************************************************
My website is at https://urldefense.proofpoint.com/v2/url?u=https-3A__u.osu.edu_friedman.8_&d=DwIBaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=xXZM6ZrkjVxXknjzIxhAvQ&m=rkdJBCddSVLYeoF3IdZF03H7rT-ukvBhlKKBHq5Q0Ow&s=zXGqaL6UMGbZnOMbQAy-2AI7kD05wPgnY53eZE_H5N4&e= and my youtube site is at
https://urldefense.proofpoint.com/v2/url?u=https-3A__www.youtube.com_channel_UCdRdeExwKiWndBl4YOxBTEQ&d=DwIBaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=xXZM6ZrkjVxXknjzIxhAvQ&m=rkdJBCddSVLYeoF3IdZF03H7rT-ukvBhlKKBHq5Q0Ow&s=yDbSXD5UUysPpGkM7Yu8qXNcoLcZn2lWdPeHfRP3_aA&e=
This is the 829th 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-799 can be found at
https://urldefense.proofpoint.com/v2/url?u=http-3A__u.osu.edu_friedman.8_foundational-2Dadventures_fom-2Demail-2Dlist_&d=DwIBaQ&c=slrrB7dE8n7gBJbeO0g-IQ&r=xXZM6ZrkjVxXknjzIxhAvQ&m=rkdJBCddSVLYeoF3IdZF03H7rT-ukvBhlKKBHq5Q0Ow&s=OfrdMx840NFn3tfwaraALUvtrqvBPcQUEvwDdBDRoy0&e=
800: Beyond Perfectly Natural/6 4/3/18 8:37PM
801: Big Foundational Issues/1 4/4/18 12:15AM
802: Systematic f.o.m./1 4/4/18 1:06AM
803: Perfectly Natural/7 4/11/18 1:02AM
804: Beyond Perfectly Natural/8 4/12/18 11:23PM
805: Beyond Perfectly Natural/9 4/20/18 10:47PM
806: Beyond Perfectly Natural/10 4/22/18 9:06PM
807: Beyond Perfectly Natural/11 4/29/18 9:19PM
808: Big Foundational Issues/2 5/1/18 12:24AM
809: Goedel's Second Reworked/1 5/20/18 3:47PM
810: Goedel's Second Reworked/2 5/23/18 10:59AM
811: Big Foundational Issues/3 5/23/18 10:06PM
812: Goedel's Second Reworked/3 5/24/18 9:57AM
813: Beyond Perfectly Natural/12 05/29/18 6:22AM
814: Beyond Perfectly Natural/13 6/3/18 2:05PM
815: Beyond Perfectly Natural/14 6/5/18 9:41PM
816: Beyond Perfectly Natural/15 6/8/18 1:20AM
817: Beyond Perfectly Natural/16 Jun 13 01:08:40
818: Beyond Perfectly Natural/17 6/13/18 4:16PM
819: Sugared ZFC Formalization/1 6/13/18 6:42PM
820: Sugared ZFC Formalization/2 6/14/18 6:45PM
821: Beyond Perfectly Natural/18 6/17/18 1:11AM
822: Tangible Incompleteness/1 7/14/18 10:56PM
823: Tangible Incompleteness/2 7/17/18 10:54PM
824: Tangible Incompleteness/3 7/18/18 11:13PM
825: Tangible Incompleteness/4 7/20/18 12:37AM
826: Tangible Incompleteness/5 7/26/18 11:37PM
827: Tangible Incompleteness Restarted/1
828: Tangible Incompleteness Restarted/2
Harvey Friedman
More information about the FOM
mailing list