[FOM] 248:Relational System Theory 2/restated

Harvey Friedman friedman at math.ohio-state.edu
Thu May 26 01:46:10 EDT 2005


We begin with a minor correction to #245, Relational System Theory 1,
http://www.cs.nyu.edu/pipermail/fom/2005-May/008948.html

There I wrote in the sixth paragraph,

"We can form an object x which holds of any objects y,z,w if and only if a
given first order formula holds of y,z,w, where x does not appear and where
parameters for objects are allowed."

This should read

"We can form an object x which holds of any argumental objects y,z,w if and
only if a given first order formula holds of y,z,w, where x does not appear
and where parameters for objects are allowed, and all quantifiers range over
argumental objects only."

#######################################

This is a restatement of #246, Relational System Theory 2,
http://www.cs.nyu.edu/pipermail/fom/2005-May/008949.html. There were a
number of misstatements there in sections 4 and 5. Sections 2,3 remain the
same.

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

###2. Ternary.###

The base theory for our investigation is the system Ternary. Ternary is a
one sorted theory, with only equality and x[y,z,w].

We say that x is an argument (arg) if and only if there exists y,z,w such
that y[x,z,w] or y[z,x,w] or y[z,w,x].

Here are the axioms of Ternary.

COMPLEMENTATION. (therexists x)(forall args y,z,w)(x[y,z,w] iff not
u[y,z,w]).

UNION. (therexists x)(forall y,z,w)(x[y,z,w] iff (u[y,z,w] or v[y,z,w])).

ATOMIC COMPREHENSION. (therexists x)(forall args y,z,w)(x[y,z,w] iff phi),
where phi is an atomic formula not mentioning x.

PROJECTION. (therexists x)(forall args y,z,w)(x[y,z,w] iff (therexists
u)(v[u,z,w])). 

Obviously, every one of these axioms is a single sentence, except Atomic
Comprehension. But here there are only finitely many instances up to change
of variables. E.g., we can insist that phi be an atomic formula whose
variables are among y,z,w,t,u,v.

###3. Systems, Subsystems, Reductions, Full Systems, Complete Systems.###

We say that x is argumental if and only if x is an argument. We say that x
is nonargumental if and only if x is not an argument. We use the term
"object" for any x. Hence objects can be argumental or nonargumental.

We say that x is a subobject of y if and only if (forall t,u,v)(x[t,u,v]
implies y[t,u,v]). We write this as x containedin y. We write x triplebar y
if and only if x containedin y and y containedin x.

Note that x containedin y does not really say that x is similar to y - at
least not very strongly. We would also like the inner workings of x to be
the same as the inner workings of y, with regard to objects that fall within
the purview of x. This motivates the following definition.

We say that x' is a restriction of x if and only if for all arguments t,u,v
of x', x[t,u,v] iff x'[t,u,v].

We will not be using the above definition. Instead, we work with triples of
objects x,y,z. The components of the triple x,y,z are x and y and z.

We say that t is an argument of the triple x,y,z if and only if t is an
argument of at least one of its three components.

Let t,u be distinct. We say that t,u are related by x if and only if x holds
of some three objects that include both t,u.

A 3-system is a triple x,y,z, where each of its three components are each
nonempty (i.e., have at least one argument), and any two distinct arguments
of the triple x,y,z are related by at least one of its three components.

We say that x',y',z' is a subsystem of the 3-system x,y,z if and only if
x',y',z' is a 3-system such that for all arguments t,u,v of the 3-system
x',y',z', 

x[t,u,v] iff x'[t,u,v];
y[t,u,v] iff y'[t,u,v];
z[t,u,v] iff z'[t,u,v].

We introduce two related notions of reduction.

An a-reduction of a 3-system S is a subsystem of S, where the argumental
components of S remain the same, and the nonargumental components of S
become argumental.

An na-reduction of a 3-system S is a subsystem of S, where the argumental
components of S remain the same, and the nonargumental components of S
remain nonargumental, but not triplebar.

We say that a 3-system S is full if and only if every subobject of an
argument of S is an argument of S.

We say that a 3-system S is complete if and only if every argumental object
agrees with some argument of S at all triples of arguments of S.

We are now prepared to state the following axioms.

A-REDUCTION. Every 3-system has an a-reduction.
NA-REDUCTION. Every 3-system has an na-reduction.
FULL A-REDUCTION. Every full 3-system has a full a-reduction.
FULL NA-REDUCTION. Every full 3-system has a full na-reduction.
COMPLETE A-REDUCTION. Every complete 3-system has a complete a-reduction.
COMPLETE NA-REDUCTION. Every complete 3-system has a complete na-reduction.

There is a weak form of A-Reduction that we work with. We say that a
3-system is argumental if and only if each of its three components is
argumental.

ARGUMENTAL SUBSYSTEM. Every 3-system has an argumental subsystem.

###4. Results###

THEOREM 4.1. Ternary + A-Reduction is mutually interpretable with Z_2 =
second order arithmetic. The same is true of Ternary + Argumental Subsystem.

THEOREM 4.2. Ternary + NA-Reduction is mutually interpretable with NBG + "On
is a Ramsey cardinal". In particular, it interprets ZFC + "There exists an
almost Ramsey cardinal", and is interpretable in ZF\P + "there exists a
Ramsey cardinal". The same is true of Ternary + A-Reduction + Full
A-Reduction + NA-Reduction.

THEOREM 4.3. Ternary + Full A-Reduction is mutually interpretable with ZFC.
The same is true of Ternary + A-Reduction + Full A-Reduction.

THEROEM 4.4. Ternary + Full NA-Reduction, Ternary + Complete A-Reduction,
are both inconsistent.

We say that V(kappa) is strongly inaccessible if and only if every function
from an element of V(kappa) into V(kappa) is itself an element of V(kappa).

THEOREM 4.5. Ternary + Complete NA-reduction interprets NBG + {there exists
a nontrivial Sigma_n elementary embedding from V into V}_n, and is
interpretable in ZF + "there exists a cardinal kappa and a nontrivial
elementary embedding from V(kappa+1) into V(kappa+1), where V(kappa) is
strongly inaccessible". The same is true of Ternary + A-Reduction + Full
A-Reduction + NA-Reduction + Complete NA-Reduction.

COROLLARY 4.6. Ternary + Complete NA-reduction interprets ZFC +
"there exists a nontrivial embedding from a rank into itself".

Here a Ramsey cardinal is a cardinal kappa such that for all partitions of
the finite subsets of kappa into two pieces, there is a subset of ( of
cardinality ( such that any two finite subsets of the subset of the same
finite cardinality lie in the same piece.

An almost Ramsey cardinal is an uncountable cardinal kappa such that for all
partitions of the finite subsets of kappa into two pieces, there is a subset
of kappa, of any given cardinality < kappa, such that any two finite subsets
of the subset of the same finite cardinality lie in the same piece.

Almost Ramsey cardinals are incompatible with the axiom of constructability.

In [Mi79], the Dodd Jensen core model is used in order to establish the
mutual interpretability of

ZFC + "there exists a Jonsson cardinal".
ZFC + "there exists a Ramsey cardinal".

For our results (Theorems 4.2, 5.3), we use the mutual interpretability of
the following triple and the following pair: , we use the mutual
interpretabilty of

NBG + "On is a Jonsson cardinal".
NBG\P + "On is a Jonsson cardinal".
NBG + "On is a Ramsey cardinal".

ZF\P + "there exists a Jonsson cardinal".
ZF\P + "there exists a Ramsey cardinal".

Mitchell has confirmed that his published proof will establish this with
"tentative strong belief".

It is well known that NBG + {there exists a nontrivial Sigma_n elementary
embedding from V into V}_n is stronger than ZFC + many
measurable cardinals. Using known inner model theory, it is well known that
it is stronger than ZFC + projective determinacy, or ZFC + Woodin cardinals.
Woodin, using forcing arguments, has shown that NBG + {there exists a
nontrivial Sigma_n elementary embedding from V into V}_n V interprets ZFC
+ "there exists a nontrivial elementary embedding from a rank into itself".
Hence Corollary 4.6.

###5. Schematic Versions.###

We now freely use schemes. While we believe that the avoidance of schemes is
an important development, we also believe that there is still some
importance to be attached to the systems based on schemes.

The most mild use of schemes is to use the following.

ARGUMENTAL COMPREHENSION. (therexists x)(forall args y,z,w)(x[y,z,w] iff
phi), where phi is a formula not mentioning x, whose quantifiers range over
argumental objects only.

We can also use this stronger form.

COMPREHENSION. (therexists x)(forall args y,z,w)(x[y,z,w] iff phi), where
phi is a formula not mentioning x.

THEOREM 5.1. All of the systems discussed in 4.1 - 4.6 are equivalent to the
systems obtained by replacing Ternary with Atom + Argumental Comprehension.

If we use Atom + Comprehension instead of Ternary, then the systems are
somewhat stronger. We restate the results using Atom + Comprehension as
follows.

THEOREM 5.2. Atom + Comprehension + A-Reduction is mutually interpretable
with Z_3 = third order arithmetic. The same is true of Atom + Comprehension
+ Argumental Subsystem.

THEOREM 5.3. Atom + Comprehension + NA-Reduction is mutually interpretable
with ZF\P + "there exists a Ramsey cardinal". In particular, it interprets
ZFC + "There exists an almost Ramsey cardinal", and is interpretable in ZFC
+ "there exists a Ramsey cardinal". The same is true of Atom + Comprehension
+ A-Reduction + Full A-Reduction + NA-Reduction.

THEOREM 5.4. Atom + Comprehension + Full A-Reduction is mutually
interpretable with MKGC = Morse Kelley with Global Choice. The same is true
of Atom + Comprehension + A-Reduction + Full A-Reduction.

THEROEM 5.5. Atom + Comprehension + Full NA-Reduction, Atom + Comprehension
+ Complete A-Reduction, are both inconsistent.

THEOREM 5.6. Atom + Comprehension + Complete NA-reduction interprets MK +
{there exists a nontrivial Sigma_n elementary embedding from V into V}_n,
and is interpretable in ZF + "there exists a cardinal kappa and a nontrivial
elementary embedding from V(kappa+1) into V(kappa+1), where V(kappa) is
strongly inaccessible". The same is true of Atom + Comprehension +
A-Reduction + Full A-Reduction + NA-Reduction + Complete NA-Reduction.

COROLLARY 5.7. Atom + Comprehension + Complete NA-reduction interprets ZFC +
"there exists a nontrivial embedding from a rank into itself".

There are other ways in which schemes can be used for alternative
formulations of Relational System Theory. We will not go into this here.
Earlier versions of this work employed schemes in many ways that we have
avoided here.

All of our results (sections 4 and 5) remain the same if we use
extensionality. Of course, if we use extensionality, then there is no need
to use triplebar.

REFERENCES

[Fr03] `Restrictions and extensions', February 17, 2003, 3 pages, draft,
http://www.math.ohio-state.edu/%7Efriedman/manuscripts.html

[Fr04] Working with Nonstandard Models, in: Nonstandard Models of Arithmetic
and Set Theory, American Mathematical Society, ed. Enayat and Kossak, 71-86,
2004. 

[Mi79] W. Mitchell, Ramsey Cardinals and Constructibility, JSL, Vol. 44, No.
2 (June 1979), 260-266.


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

I use www.math.ohio-state.edu/~friedman/ for downloadable manuscripts.
This is the 248th 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-149 can be found at
http://www.cs.nyu.edu/pipermail/fom/2003-May/006563.html in the FOM
archives, 5/8/03 8:46AM. Previous ones counting from #150 are:

150:Finite obstruction/statistics  8:55AM  6/1/02
151:Finite forms by bounding  4:35AM  6/5/02
152:sin  10:35PM  6/8/02
153:Large cardinals as general algebra  1:21PM  6/17/02
154:Orderings on theories  5:28AM  6/25/02
155:A way out  8/13/02  6:56PM
156:Societies  8/13/02  6:56PM
157:Finite Societies  8/13/02  6:56PM
158:Sentential Reflection  3/31/03  12:17AM
159.Elemental Sentential Reflection  3/31/03  12:17AM
160.Similar Subclasses  3/31/03  12:17AM
161:Restrictions and Extensions  3/31/03  12:18AM
162:Two Quantifier Blocks  3/31/03  12:28PM
163:Ouch!  4/20/03  3:08AM
164:Foundations with (almost) no axioms 4/22/03  5:31PM
165:Incompleteness Reformulated  4/29/03  1:42PM
166:Clean Godel Incompleteness  5/6/03  11:06AM
167:Incompleteness Reformulated/More  5/6/03  11:57AM
168:Incompleteness Reformulated/Again 5/8/03  12:30PM
169:New PA Independence  5:11PM  8:35PM
170:New Borel Independence  5/18/03  11:53PM
171:Coordinate Free Borel Statements  5/22/03  2:27PM
172:Ordered Fields/Countable DST/PD/Large Cardinals  5/34/03  1:55AM
173:Borel/DST/PD  5/25/03  2:11AM
174:Directly Honest Second Incompleteness  6/3/03  1:39PM
175:Maximal Principle/Hilbert's Program  6/8/03  11:59PM
176:Count Arithmetic  6/10/03  8:54AM
177:Strict Reverse Mathematics 1  6/10/03  8:27PM
178:Diophantine Shift Sequences  6/14/03  6:34PM
179:Polynomial Shift Sequences/Correction  6/15/03  2:24PM
180:Provable Functions of PA  6/16/03  12:42AM
181:Strict Reverse Mathematics 2:06/19/03  2:06AM
182:Ideas in Proof Checking 1  6/21/03 10:50PM
183:Ideas in Proof Checking 2  6/22/03  5:48PM
184:Ideas in Proof Checking 3  6/23/03  5:58PM
185:Ideas in Proof Checking 4  6/25/03  3:25AM
186:Grand Unification 1  7/2/03  10:39AM
187:Grand Unification 2 - saving human lives 7/2/03 10:39AM
188:Applications of Hilbert's 10-th 7/6/03  4:43AM
189:Some Model theoretic Pi-0-1 statements  9/25/03  11:04AM
190:Diagrammatic BRT 10/6/03  8:36PM
191:Boolean Roots 10/7/03  11:03 AM
192:Order Invariant Statement 10/27/03 10:05AM
193:Piecewise Linear Statement  11/2/03  4:42PM
194:PL Statement/clarification  11/2/03  8:10PM
195:The axiom of choice  11/3/03  1:11PM
196:Quantifier complexity in set theory  11/6/03  3:18AM
197:PL and primes 11/12/03  7:46AM
198:Strong Thematic Propositions 12/18/03 10:54AM
199:Radical Polynomial Behavior Theorems
200:Advances in Sentential Reflection 12/22/03 11:17PM
201:Algebraic Treatment of First Order Notions 1/11/04 11:26PM
202:Proof(?) of Church's Thesis 1/12/04 2:41PM
203:Proof(?) of Church's Thesis - Restatement 1/13/04 12:23AM
204:Finite Extrapolation 1/18/04 8:18AM
205:First Order Extremal Clauses 1/18/04 2:25PM
206:On foundations of special relativistic kinematics 1 1/21/04 5:50PM
207:On foundations of special relativistic kinematics 2  1/26/04  12:18AM
208:On foundations of special relativistic kinematics 3  1/26/04  12:19AAM
209:Faithful Representation in Set Theory with Atoms 1/31/04 7:18AM
210:Coding in Reverse Mathematics 1  2/2/04  12:47AM
211:Coding in Reverse Mathematics 2  2/4/04  10:52AM
212:On foundations of special relativistic kinematics 4  2/7/04  6:28PM
213:On foundations of special relativistic kinematics 5  2/8/04  9:33PM
214:On foundations of special relativistic kinematics 6  2/14/04 9:43AM
215:Special Relativity Corrections  2/24/04 8:13PM
216:New Pi01 statements  6/6/04  6:33PM
217:New new Pi01 statements  6/13/04  9:59PM
218:Unexpected Pi01 statements  6/13/04  9:40PM
219:Typos in Unexpected Pi01 statements  6/15/04  1:38AM
220:Brand New Corrected Pi01 Statements  9/18/04  4:32AM
221:Pi01 Statements/getting it right  10/7/04  5:56PM
222:Statements/getting it right again  10/9/04  1:32AM
223:Better Pi01 Independence  11/2/04  11:15AM
224:Prettier Pi01 Independence  11/7/04  8:11PM
225:Better Pi01 Independence  11/9/04  10:47AM
226:Nicer Pi01 Independence  11/10/04  10:43AM
227:Progress in Pi01 Independence  11/11/04  11:22PM
228:Further Progress in Pi01 Independence  11/12/04  2:49AM
229:More Progress in Pi01 Independence  11/13/04  10:41PM
230:Piecewise Linear Pi01 Independence  11/14/04  9:38PM
231:More Piecewise Linear Pi01 Independence  11/15/04  11:18PM
232:More Piecewise Linear Pi01 Independence/correction  11/16/04  8:57AM
233:Neatening Piecewise Linear Pi01 Independence  11/17/04  12:22AM
234:Affine Pi01 Independence  11/20/04  9:54PM
235:Neatening Affine Pi01 Independence  11/28/04  6:08PM
236:Pi01 Independence/Huge Cardinals  12/2/04  3:49PM
237:More Neatening Pi01 Affine Independence  12/6/04  12:56AM
238:Pi01 Independence/Large Large Cardinals/Correction  12/7/04  10:31PM
239:Pi01 Update  12/11/04  1:12PM
240:2nd Pi01 Update  12/13/04  2:49AM
241:3rd Pi01 Update  12/13/04  4:08AM
242:4th Pi01 Update  12/18/04  9:47PM
243:Inexplicit Pi01/Ordinals of Set Theories  12/19/04  11:48PM
244:LUB Systems  2/26/05  8PM
245:Relational System Theory 1  5/16/05  12:24PM
246:Relational System Theory 2  5/15/05  9:57PM
247:Inevitability of Logical Strength  5/15/05  9:57PM

Harvey Friedman



More information about the FOM mailing list