[FOM] 405: Some Countable Model Theory 1

Wed Mar 24 13:03:00 EDT 2010

THIS RESEARCH WAS PARTIALLY SUPPORTED BY THE JOHN TEMPLETON FOUNDATION.

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

We present some very simple model theoretic properties of countable  
structures. However, for some combinations of them, it is necessary  
and sufficient to use large cardinals to prove that there is an  
example. The existence statements are provably equivalent to  
consistency statements.

This differs from the examples we have been discussing at length on  
the FOM, because we freely employ the notion of DEFINABLE RELATIONS  
AND FUNCTIONS.

SOME COUNTABLE MODEL THEORY 1
by
Harvey M. Friedman
March 24, 2010

1. TWO BASIC CONDITIONS.
2. UNIVERSALITY CONDITION.
3. ELEMENTARY EMBEDDING CONDITIONS.

1. TWO BASIC CONDITIONS.

Let M be a relational structure in a finite relational type.

Here, definable always means M definable with parameters, and 0- 
definable means M definable without parameters.

We say that A is SMALL if and only if A is a definable subset of  
dom(M) such that there is no definable multivariate function from A  
onto dom(M).

THEOREM 1.1. For every M, any definable subset of any small set is  
small.

We now put some conditions on M.

C1. There is a one-one definable unary function from some small set  
into a proper subset.
C2. For every small A there is a small B such that there is no  
definable multivariate function from A onto B.

THEOREM 1.2. (Q,<,f) obeys C1,C2, where f(q) = q+1 if q < 0; q  
otherwise.

2. UNIVERSALITY CONDITION.

Now consider the following universality condition UC.

UC. There is a 0-definable subset R of dom(M)^2 whose cross sections  
comprise the small sets without repetition.

Actually, quite a lot can be done - but not everything that we want to  
do - with the weaker form of UC that uses "definable" instead of "0- 
definable".

THEOREM 2.1. Let R be a subset of N^2 whose cross sections are the  
finite subsets of N, with no repetition. Then (N,R) obeys C2,UC, but  
not C1.

THEOREM 2.2. There is a countable M obeying conditions C1,UC.

PROPOSITION 2.3. There is a countable M obeying conditions C1,C2,UC.  
ZFC level

THEOREM 2.4. ACA' proves the equivalence of Theorem 2.2 with Con(Z_2).  
In particular, Theorem 2.2 cannot be proved in countable set theory  
(ZFC\P).

THEOREM 2.5. ACA' proves the equivalence of Proposition 2.3. with  
Con(ZFC). In particular, Proposition 2.3 cannot be proved from any  
consequence of ZFC that is consistent with RCA_0. These results hold  
even if we replace "0-definable" by "definable" in UC.

3. ELEMENTARY EMBEDDING CONDITIONS.

Here "elementary embedding" means an elementary embedding from M into  
M. Nontrivial means "not the identity".

E1. There is an elementary embedding whose set of fixed points is small.
E2. There is a nontrivial elementary embedding mapping small sets onto  
small sets.
E3. There is an elementary embedding whose set of fixed points is  
small, and which maps small sets onto small sets.
E4. There is an elementary embedding which maps some small set onto a  
proper small subset.

PROPOSITION 3.1. There is a countable M obeying UC,E1. In fact, there  
is a countable M obeying UC,E1,C1,C2.

PROPOSITION 3.2. There is a countable M obeying UC,E2. In fact, there  
is a countable M obeying UC,E1,E2,E3,C1,C2.

PROPOSITION 3.3. There is a countable M obeying UC,E4. In fact, there  
is a countable M obeying UC,E1,E2,E3,E4,C1,C2.

THEOREM 3.4. Proposition 3.1 is equivalent to Con(SRP) over ACA'.  
Proposition 3.2 is equivalent to Con(HUGE) over ACA'. Proposition 3.3  
implies Con(I3) and is implied by Con(I2), over ACA'.

Here SRP = ZFC + {there exists a k-SRP ordinal}_k. HUGE = ZFC + there  
exists a k-huge cardianl}_k. I3 = ZFC + "there exists a nontrivial  
elementary embedding from some rank into itself". I2 is a technical  
consequence of I1 = ZFC + "there exists a nontrivial elementary  
embedding from some V(alpha + 1) into V(alpha + 1). ACA' = ACA_0 +  
"for all k in N and x contained in N, the k-th Turing jump of x exists".

THEOREM 3.5. There is a countable M obeying C1,C2,E1,E2,E3,E4. We can  
use M = (Q,<,f), where f(q) = q-1 if q < sqrt(2); q otherwise.

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

I use http://www.math.ohio-state.edu/~friedman/ for downloadable
manuscripts. This is the 405th 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-349 can be found at http://www.cs.nyu.edu/pipermail/fom/2009-August/014004.html
in the FOM archives.

350: one dimensional set series  7/23/09  12:11AM
351: Mapping Theorems/Mahlo/Subtle  8/6/09  10:59PM
352: Mapping Theorems/simpler  8/7/09  10:06PM
353: Function Generation 1  8/9/09  12:09PM
354: Mahlo Cardinals in HIGH SCHOOL 1  8/9/09  6:37PM
355: Mahlo Cardinals in HIGH SCHOOL 2  8/10/09  6:18PM
356: Simplified HIGH SCHOOL and Mapping Theorem  8/14/09  9:31AM
357: HIGH SCHOOL Games/Update  8/20/09  10:42AM
358: clearer statements of HIGH SCHOOL Games  8/23/09  2:42AM
359: finite two person HIGH SCHOOL games  8/24/09  1:28PM
360: Finite Linear/Limited Memory Games  8/31/09  5:43PM
361: Finite Promise Games  9/2/09  7:04AM
362: Simplest Order Invariant Game  9/7/09  11:08AM
363: Greedy Function Games/Largest Cardinals 1
364: Anticipation Function Games/Largest Cardinals/Simplified 9/7/09
11:18AM
365: Free Reductions and Large Cardinals 1  9/24/09  1:06PM
366: Free Reductions and Large Cardinals/polished  9/28/09  2:19PM
367: Upper Shift Fixed Points and Large Cardinals  10/4/09  2:44PM
368: Upper Shift Fixed Point and Large Cardinals/correction  10/6/09
8:15PM
369. Fixed Points and Large Cardinals/restatement  10/29/09  2:23PM
370: Upper Shift Fixed Points, Sequences, Games, and Large Cardinals
11/19/09  12:14PM
371: Vector Reduction and Large Cardinals  11/21/09  1:34AM
372: Maximal Lower Chains, Vector Reduction, and Large Cardinals
11/26/09  5:05AM
373: Upper Shifts, Greedy Chains, Vector Reduction, and Large
Cardinals  12/7/09  9:17AM
374: Upper Shift Greedy Chain Games  12/12/09  5:56AM
375: Upper Shift Clique Games and Large Cardinals 1
376: The Upper Shift Greedy Clique Theorem, and Large Cardinals
12/24/09  2:23PM
377: The Polynomial Shift Theorem  12/25/09  2:39PM
378: Upper Shift Clique Sequences and Large Cardinals  12/25/09  2:41PM
379: Greedy Sets and Huge Cardinals 1
380: More Polynomial Shift Theorems  12/28/09  7:06AM
381: Trigonometric Shift Theorem  12/29/09  11:25AM
382: Upper Shift Greedy Cliques and Large Cardinals  12/30/09  2:51AM
383: Upper Shift Greedy Clique Sequences and Large Cardinals 1
12/30/09  3:25PM
384: THe Polynomial Shift Translation Theorem/CORRECTION  12/31/09
7:51PM
385: Shifts and Extreme Greedy Clique Sequences  1/1/10  7:35PM
386: Terrifically and Extremely Long Finite Sequences  1/1/10  7:35PM
387: Better Polynomial Shift Translation/typos  1/6/10  10:41PM
388: Goedel's Second Again/definitive?  1/7/10  11:06AM
389: Finite Games, Vector Reduction, and Large Cardinals 1  2/9/10
3:32PM
390: Finite Games, Vector Reduction, and Large Cardinals 2  2/14/09
10:27PM
391: Finite Games, Vector Reduction, and Large Cardinals 3  2/21/10
5:54AM
392: Finite Games, Vector Reduction, and Large Cardinals 4  2/22/10
9:15AM
393: Finite Games, Vector Reduction, and Large Cardinals 5  2/22/10
3:50AM
394: Free Reduction Theory 1  3/2/10  7:30PM
395: Free Reduction Theory 2  3/7/10  5:41PM
396: Free Reduction Theory 3  3/7/10  11:30PMs
397: Free Reduction Theory 4  3/8/10  9:05AM
398: New Free Reduction Theory 1  3/10/10  5:26AM
399: New Free Reduction Theory 2  3/12/10  9:36AM
400: New Free Reduction Theory 3  3/14/10  11:55AM
401: New Free Reduction Theory 4  3/15/10  4:12PM
402: New Free Reduction Theory 5  3/19/10  12:59PM
403: Set Equation Tower Theory 1  3/22/10  2:45PM
404: Set Equation Tower Theory 2

Harvey Friedman