[FOM] 476:Maximality, Choice, and Incompleteness
Harvey Friedman
friedman at math.ohio-state.edu
Sun Jan 22 23:49:21 EST 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
******************************************
We now officially adopt "detached choice" as a path to ZFC
independence, in addition to the "maximality" that we have been using.
We now prefer to use "detached choice" for all of the explicitly Pi01
forms. we have been using independent dominators not as a competitor
for maximal cliques - but for motivating certain explicitly Pi01
forms. Now that we are using "detached choice" instead, we have (at
least at present) no need for independent dominators - maximal cliques
are much more widely known than the dual notion of independent
dominators.
Below we give an organized list of all of the main independent
statements, including ones based on "detached choice" - without
definitions. We will give the definitions after we give the list.
As usual, all of the infinite incompleteness statements are Pi01 via
satisfiability in predicate calculus - see the NOTES below.
BASIC THEOREMS.
A1. Every binary relation has a maximal square.
A2. Every graph has a maximal clique.
A3. Every reflexive symmetric relation has a detached choice function.
NOTE: We only care about the countable case, which can be proved very
explicitly - see the NOTES below.
INFINITE UNPROVABLE THEOREMS WITH 16,16.
B1. Every order invariant subset of Q[0,16]^32 has a completely Z+up
invariant maximal square.
B2. Every order invariant graph on Q[0,16]^16 has a completely Z+up
invariant maximal clique.
B3. Every order invariant reflexive symmetric relation on Q[0,16]^16
has a Z+up commuting detached choice function.
INFINITE UNPROVABLE THEOREMS WITH k,n.
C1. For all k,n >= 1, every order invariant subset of Q[0,k]^2n has a
completely Z+up invariant maximal square.
C2. For all k,n >= 1, every order invariant graph on Q[0,k]^n has a
completely Z+up invariant maximal clique.
C3. For all k,n >= 1, every order invariant reflexive symmetric
relation on Q[0,k]^n has a Z+up commuting detached choice function.
FINITE UNPROVABLE THEOREM.
D. For all k,n,r >= 1, every order invariant reflexive symmetric
relation on Q[0,k]^n contains a finite Z+up commuting detached
function whose r-composites are defined on {0,...,k}^n.
USING UPPER INTEGRAL INVARIANCE.
In B1,B2,C1,C2, we replace "completely Z+up invariant" we can replace
by the stronger "upper integral invariant". These are B1',B2',C1',C2'.
********************************************
DEFINITIONS
Q[0,k] is the set of rationals in [0,k].
A binary relation is a set of ordered pairs. A square in a binary
relation is a subset of the form A x A. A maximal square in a binary
relation is a square in the binary relation which is not properly
contained in any square in the binary relation.
A graph is a pair (V,E), where V is a set and E is an irreflexive
symmetric binary relation on V (the adjacency relation). A clique in a
graph is a set of vertices, where any two distinct elements are
adjacent. A maximal clique in a graph is a clique in the graph which
is not properly contained in any clique in the graph.
A choice function for a relation is a function whose graph is
contained in the relation and which has the same domain as the
relation. A detached function for a relation is a function where no
two distinct values are related.
We distinguish four kinds of relevant invariance conditions.
i. A set is invariant under a relation.
ii. A set is invariant under a function.
iii. A set is completely invariant under a function.
iv. Functions f,g commute. Equivalently, f is g commuting.
The first three notions depend on the set S being a subset of an
ambient space K. The fourth notion does not involve an ambient space.
S is R invariant if and only if for all x,y in K with R(x,y), we have
x in S implies y in S.
S is f invariant if and only if for all x,f(x) in K, we have x in S
implies f(x) in S.
S is completely f invariant if and only if for all x,f(x) in K, we
have x in S iff f(x) in S.
f,g commute (f is g commuting) if and only if fog and gof agree on
dom(f) intersect rng(f).
The relevant ambient spaces for order invariance are Q[0,k]^2n,
Q[0,16]^32.
The relevant ambient spaces for Z+up invariance is Q[0,k]^2n,
Q[0,16]^32 for the statements with squares, and Q[0,k]^n, Q[0,16]^16
for the statements with cliques.
Order invariance refers to the relation of order equivalence on Q* =
the set of all nonempty finite sequences from Q. x,y in Q* are order
equivalent if and only if x,y have the same length, and for all 1 <=
i,j <= lth(x), x_i < x_j iff y_i < y_j.
Z+up invariance refers to the function Z+up:Q* into Q*. For x in Q*, Z
+up(x) is the result of adding 1 to all coordinates of x greater than
all coordinates outside Z+.
Let f:A^n into A^n be partial. The composites of f are the partial
functions from A^n into A given by expressions involving f_1,...,f_n,
and variables x_1,...,x_n. The r-composites are the composites that
use at most r functions, counting multiplicities.
Upper integral invariance refers to the relation of upper integral
equivalence on Q*. x,y in Q* are upper integral equivalent if and only
if x,y are order equivalent, and for all 1 <= i <= lth(x), if x_i not=
y_i then every x_j >= x_i lies in Z+ and every y_j >= y_i lies in Z+.
NOTES
A1,A2,A3 are theorems of ZFC, and are equivalent to the axiom of
choice over ZF. However, we will only care about the countable case,
where there is no problem proving these in RCA_0. There are important
sharpened forms that are provably equivalent to ACA_0 over RCA_0.
B1-B3,C1-C3,D,B1',B2',C1',C2' are provable using suitable large
cardinals but not in ZFC. All of these, other than D, can easily be
seen to be Pi01 through the Goedel completeness theorem for predicate
calculus.
In particular, note that B1,B2,C1,C2,B1',B2',C1',C2' assert the
satisfiability of each of (in)finitely many A...AE...E sentences in
predicate calculus with equality, whereas B3,C3 assert the
satisfiability of each of (in)finitely many A...A sentences in
predicate calculus in predicate calculus with equality. Finite forms
of satisfiability of A...A sentences are familiar in general algebra,
and our use of
r-composites in D is a simple way of giving such familiar finite forms.
D is explicitly Pi02. Moreover, D is easily seen to be Pi01 through
the well known decision procedure for dense linear orderings with
endpoints. Alternatively, at most double exponential upper bounds can
be placed on the numerators and denominators of the rationals involved.
*****************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 476th 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
Harvey Friedman
More information about the FOM
mailing list