[FOM] 483:Invariance in Q[0,n]^k
Harvey Friedman
friedman at math.ohio-state.edu
Sat Feb 18 19:33:27 EST 2012
THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION
*****************************************
THIS POSTING IS ENTIRELY SELF CONTAINED
****************************************
In this posting, we discuss the invariance conditions used in 482:
Maximality, Choice, and Incompleteness 2 in more detail. We show how
the particular choices of invariance conditions (for the conclusions)
are essentially forced by the context.
1. Invariance, complete invariance, Q*, Q[0,n]^k.
2. Equivalence relations on Q*.
3. Restricted shift functions on Q*.
4. Invariance and complete invariance.
5. Results.
1. INVARIANCE, COMPLETE INVARIANCE, Q*, Q[0,n]^k.
Let Q be the set of all rationals. Let Q[0,n] be Q intersect [0,n].
We use three kinds of invariance conditions in the conclusion.
In particular, we use the following invariance conditions.
S containedin Q]0,n]^k is upper integral invariant.
S containedin Q[0,n]^k is completely Z+up invariant.
F:Q[0,n]^k into Q[0,n]^k is upper integral invariant.
F:Q[0,n]^k into Q[0,n]^k is completely Z+up invariant.
This depends on a particular equivalence relation on Q* called "upper
integral equivalence"; and a particular function from Q* into Q*
called Z+up.
In the above, F:Q[0,n]^k into Q[0,n]^k is treated as a subset of
Q[0,n]^2k.
Here the first means that for all upper integral equivalent x,y in
Q[0,n]^k, x in S implies y in S.
The second means that for all x,Z+up(x) in Q[0,n]^k, x in S iff Z
+up(x) in S.
The third means that for all upper integral equivalent x,y in
Q]0,n]^2k, x in graph(f) implies y in graph(f).
The fourth means that for all x,Z+up(x) in Q[0,n]^2k, x in graph(f)
iff Z+up(x) in graph(f).
2. EQUIVALENCE RELATIONS ON Q*.
For the hypotheses of the statements, we use order equivalence on Q*.
This equivalence relation is entirely transparent. It has certain
important properties, which we use to drive the consideration of
further equivalence relations used for the conclusions of the
statements.
Recall that x,y in Q* are order equivalent if and only if
i. x,y have the same length.
ii. for all 1 <= i,j <= lth(x), x_i < x_j iff y_i < y_j.
Order equivalence on Q* has these three fundamental properties.
a. it is length preserving. I.e., x ~ y implies lth(x) = lth(y).
b. it is essentially binary. .I.e., (x_1,...,x_k) ~ (y_1,...,y_k) iff
(forall 1 <= i,j <= k)((x_i,x_j) iff (y_i,y_j)).
c. it can be expressed as a Boolean combination of inequalities
between the variables. I.e., x_1,...,x_k ~ y_1,...,y_k can be written
as a Boolean combination of statements of the form v < w, where v,w
are among x_1,...,x_k,y_1,...,y_k. No constants are allowed.
We can understand the equivalence relations obeying 1-3 in terms of
generators.
THEOREM 1. All equivalence relations obeying 1-3 are determined by
which of the following hold.
i. (1,1) ~ (2,2).
ii. (1,2) ~ (1,3).
iii. (1,3) ~ (2,3).
iv. (1,2) ~ (2,1).
There are nine equivalence relations obeying a-c.
The second equivalence relation on Q*, used for the conclusions in
482: Maximality, Choice, and Incompleteness 2 is upper integral
invariance. Here we use Z+ as a distinguished subspace of Q.
Upper integral invariance is a member of a considerably wider family
of equivalence relations on Q*. The Z+-regular equivalence relations
on Q* are the equivalence relations on Q* obey these three fundamental
properties.
a. It is length preserving. I.e., x ~ y implies lth(x) = lth(y).
b. It is essentially binary. .I.e., (x_1,...,x_k) ~ (y_1,...,y_k) iff
(forall 1 <= i,j <= k)((x_i,x_j) iff (y_i,y_j)).
c'. For each k, (x_1,...,x_k) ~ (y_1,...,y_k) can be expressed as a
Boolean combination of inequalities between the variables
x_1,...,x_k,y_1,...,y_k, and membership of x_1,...,x_k,y_1,...,y_k in Z
+.
Upper integral equivalence is used in 482: Maximality, Choice, and
Incompleteness 2. We know that it is the least Z+-regular equivalence
relation on Q* such that
(0,1,2) ~ (0,2,3).
We have been investigating which of the finitely many Z+-regular
equivalence relations on Q* can be used in 482: Maximality, Choice,
and Incompleteness 2
We have not completed this determination. However, we have completed
the determination for all Z+-regular equivalence relations on Q* such
that (1,2) ~ (1,3).
THEOREM 2. There is a maximum Z+-regular equivalence relation on Q*
relating (1,2) and (1,3) that can be used in 482: Maximality, Choice,
and Incompleteness 2. It is the least Z+-regular equivalence relation
on Q* relating (0,1,2) and (0,2,3). This is the same as "upper
integral invariance" as defined in 482: Maximality, Choice, and
Incompleteness 2.
We will be elaborating on Theorem 2 further in section 4, including
its metamathematical properties.
In 482: Maximality, Choice, and Incompleteness 2 we define x,y in Q*
to be 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+.
3. RESTRICTED SHIFT FUNCTIONS ON Q*.
In addition to "upper integral invariance" arising out of the
equivalence relation "upper integral equivalent", in 482: Maximality,
Choice, and Incompleteness 2 we also use a second notion of
invariance, which arising out of the function Z+up:Q* into Q*. Here Z
+up(x) is the result of adding 1 to all coordinates greater than all
coordinates not in Z+. E.g.,
Z+up(0,1,3/2,2,4) = (0,1,3/2,3,5).
Z+up:Q* into Q* has the following fundamental properties.
a. It is length preserving.
b. Z+up(x_1,...,x_k) results in adding 1 to a sublist of x_1,...,x_k.
c. For each 1 <= i <= k, the relation "1 is added to x_i under Z+up"
can be defined as a Boolean combination of inequalities between the
variables x_1,...,x_k, and membership of x_1,...,x_k in Z+.
We call such an F:Q* into Q* a Z+-regular restricted shift function on
Q*.
THEOREM 3. Let F:Q* into Q* be a Z+-regular restricted shift function
on Q*. The following are equivalent.
i. F adds 1 to a tail of the coordinates greater than all coordinates
not in Z+.
ii. For all x in Q*, x,F(x) are upper integral equivalent.
iv. F can be used in 482: Maximality, Choice, and Incompleteness 2.
********************************************
I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 482nd 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
Harvey Friedman
More information about the FOM
mailing list