[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