[FOM] 485:Large Large Cardinals

Sat Feb 25 22:50:51 EST 2012

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION

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

THIS POSTING IS ENTIRELY SELF CONTAINED

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

The state of the art Pi01 incompleteness is in

http://www.cs.nyu.edu/pipermail/fom/2012-February/016192.html This  
contains the state of the art implicitly Pi01 sentences. They are Pi01  
via the completeness theorem for predicate calculus.

http://www.cs.nyu.edu/pipermail/fom/2012-February/016199.html This  
contains the state of the art explicitly Pi01 sentences.

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

In this posting, we present some implicitly Pi01 sentences that can be  
proved from I2 but not from I3. Again, they are Pi01 via the  
completeness theorem for predicate calculus.

Here I3 is ZFC + "there is a nontrivial elementary embedding from some  
V(lambda) into V(lambda)".

I2 is NBG + AxC + "there is a nontrivial elementary embedding from V  
into some transitive class M such that V(lambda) lies in M, where  
lambda is the first fixed point above the critical point".

INCOMPLETENESS IN LARGE LAEGE CARDINALS
by
Harvey M. Friedman
February 25, 2012

1. Complementations.
2. Linearly ordered products.
3. The Complementation Embedding Theorem.

1. COMPLEMENTATIONS.

Let (D,<) be a linear ordering. We say that f:D^k into D^k is strictly  
dominating if and only if for all x in D^k, max(f(x)) > max(x).

Let f:D^k into D^k. A complementation of f is a set S contained in D^k  
such that f[S] = D^k\S.

We can rewrite this more explicitly as

for all x in D^k, x in S iff x notin f[S].

THEOREM 1.1. Let (A,<) be a linear ordering. The following are  
equivalent.
i. Every strictly dominating f:D^k into D^k has a complementation.
ii. Every strictly dominating f:D^k into D^k has a unique  
complementation.
iii. (D,<) is a well ordering.

We will need to focus on non well ordered (D,<).

2. LINEARLY ORDERED PRODUCTS.

We are going to work with linearly ordered systems (D,<,P,0,1,...),  
where (D,<) is a linear ordering, P:D^2 into D, and 0 < 1 < ... are  
distinguished elements of D. We call such a system a LOS.

There is a family of multivariate relations on A that we naturally  
associate to a LOS. The qf subsets of A^k are the subsets of A^k that  
can be defined by a Boolean combination of inequalities of the form

w_1 < w_2

where the w's are words in P, with constants from A, and variables  
among x_1,...,x_k.

The qf functions from D^k into D^k are the functions from D^k into D^k  
whose graph is a 2k-ary qf subset of D^2k. Here qf stands for  
"quantifier free".

This is analogous to a very familiar situation in core mathematics,  
where instead of using P:D^2 into D, we use addition and  
multiplication on an ordered real closed field. In that standard  
context, the qf relations are called the semialgebraic relations.

Let S be a subset of A^k. We say that S is embeddable by c if and only  
if

i. c lies in A.
ii. The function P(c,x) is one-one from fld(S) intersect (-infinity,c)  
into a proper subset of fld(S) intersect (-infinity,c).
ii. For all x_1,...,x_k in fld(S) intersect (-infinity,c),  
(x_1,...,x_k) in S iff (P(c,x_1),...,P(c,x_k)) in S.
iii. For all x notin fld(S) intersect (-infinity,c), P(c,x) = 0.

NOTE: There are some variants of this notion that will suffice for the  
result. This will be taken up later.

3. THE COMPLEMENTATION EMBEDDING THEOREM.

COMPLEMENTATION EMBEDDING THEOREM. There is a countable LOS where  
every strictly dominating qf function from any D^k into D^k has a  
complementation which is embeddable by points from the intervals (0,1), 
(1,2),(2,3),... .

The Complementation Embedding Theorem is clearly equivalent to the  
assertion that a particular effectively generated set of sentences in  
first order predicate calculus with equality is satisfiable. Thus it  
is implicitly Pi01 via the completeness theorem for predicate calculus.

THEOREM 3.1. The Complementation Embedding Theorem is provable in I2  
but not in I3. It follows from Con(I2) and implies Con(I3) over ACA'.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 485th 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  2/19/12 7:43AM
483: Invariance in Q[0,n]^k  2/19/12  7:34AM
484: Finite Choice and Incompleteness  2/20/12  6:37AM 