[FOM] 485:Large Large Cardinals
Harvey Friedman
friedman at math.ohio-state.edu
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
More information about the FOM
mailing list