[FOM] 161:Restrictions and Extensions
Harvey Friedman
friedman at math.ohio-state.edu
Mon Mar 31 00:18:08 EST 2003
A PDF version of this abstract will be available in a few days on
http://www.mathpreprints.com/math/Preprint/show/
RESTRICTIONS AND EXTENSIONS
by
Harvey M. Friedman
Ohio State University
February 17, 2003
Abstract. We consider a number of statements involving restrictions
and extensions of algebras, and derive connections with large
cardinal axioms.
1. Introduction.
By an algebra M we mean a nonempty set dom(M) together with a finite
list of functions on dom(M) of various finite arities >= 0. The
signature of M is the list of arities of the functions of M.
Let M,N be algebras. We say that M is a restriction of N if and only
if M,N have the same signature, dom(M) containedin dom(N), and the
functions of M are restrictions of the respective functions of N. We
say that N is an extension of M if and only if M is a restriction of
N.
We use kappa,lambda for cardinals throughout the paper.
We write R(kappa,fg) if and only if every algebra of cardinality
kappa has a proper restriction with the same finitely generated
restrictions up to isomorphism.
We write R(kappa,lambda) if and only if every algebra of cardinality
kappa has a proper restriction with the same restrictions of
cadinality lambda up to isomorphism.
We write E(kappa,fg) if and only if every algebra of cardinality
kappa has a proper extension with the same finitely generated
restrictions up to isomorphism.
We write E(kappa,lambda) if and only if every algebra of cardinality
kappa has a proper extension with the same restrictions of cardinality
lambda up to isomorphism.
In this paper, we will restrict attention to the case lambda = omega.
All theorems are proved in ZFC.
R(kappa,fg), R(kappa,omega) are easily treated as follows.
THEOREM 1.1. The following are equivalent.
i) R(kappa,fg);
ii) R(kappa,omega);
iii) kappa > 2^omega.
Our main results concern sufficiently large kappa.
THEOREM 1.2. The following are equivalent.
ii) for all sufficiently large kappa, E(kappa,fg);
ii) for all sufficiently large kappa, E(kappa,omega);
iii) there exists a measurable cardinal.
There is a corresponding result concerning the "turning point".
THEOREM 1.3. The following are equivalent.
i) kappa is least such that for all lambda >= kappa, E(lambda,fg);
ii) kappa is least such that for all lambda >= kappa, E(lambda,omega);
iii) kappa is the least measurable cardinal.
The Beth function is the cardinal function given by
Beth_0 = omega, Beth_alpha+1 = 2^Beth_alpha, Beth_lambda =
Union{Beth(beta): beta < lambda}.
A Beth number is a cardinal of the form Beth_alpha. Under the GCH,
for all alpha, Beth_alpha = Aleph_alpha, and so the Beth numbers are
just the infinite cardinals.
THEOREM 1.4. The following are equivalent for all Beth numbers kappa.
i) E(kappa,fg);
ii) E(kappa,omega);
iii) kappa is weakly compact or there is a measurable cardinal <= kappa.
We present two related results concerning arbitrary cardinals kappa.
THEOREM 1.5. Let kappa be least such that E(kappa,fg). kappa is a
weakly Mahlo cardinal > 2^omega, and kappa is satisfied in L to be a
weakly compact cardinal.
THEOREM 1.6. The following are mutually interpretable.
i) ZFC + there exists kappa such that E(kappa,fg);
ii) ZFC + there exists kappa such that E(kappa,omega);
iii) ZFC + there exists a weakly compact cardinal.
The following is proved by a forcing argument.
THEOREM 1.7. The following are mutually interpretable.
i) ZFC + CH + (therexists kappa < 2^omega_1)(E(kappa,omega));
ii) ZFC + there exists a weakly compact cardinal.
We now consider the use of languages (lang) for properties R and E.
Informally, we define
R(kappa,lang) if and only if every algebra of cardinality kappa has a
proper restriction satisfying the same sentences of lang.
E(kappa,lang) if and only if every algebra of cardinality kappa has a
proper extension satisfying the same sentences of lang.
We will consider the three languages WSOL, L_omega_1,omega, and SOL.
Here SOL is second order logic, and WSOL is weak second order logic.
WSOL is the same as second order logic except that the set
quantifiers range over finite relations (rather than arbitrary
relations) on the domain.
THEOREM 1.8. In Theorems 1.1 - 1.7, we can replace E(kappa,fg),
E(kappa,omega) by E(kappa,L_omega_1,omega), and R(kappa,fg),
R(kappa,omega) by R(kappa,L_omega_1,omega).
THEOREM 1.9. In Theorems 1.2 - 1.4, 1.6, we can replace E(kappa,fg),
E(kappa,omega) by E(kappa,WSOL). The following are equivalent.
i) R(kappa,WSOL);
ii) kappa > omega.
THEOREM 1.10. Let kappa be least such that E(kappa,WSOL). kappa is a
weakly Mahlo cardinal > omega, and kappa is satisfied in L to be a
weakly compact cardinal.
The following is proved by forcing.
THEOREM 1.11. The following are mutually interpretable.
i) ZFC + (therexists kappa < 2^omega)(E(kappa,WSOL);
ii) ZFC + there exists a weakly compact cardinal.
We can also consider
R'(kappa,lang) if and only if every algebra of cardinality kappa has
a proper elementary submodel in the sense of lang.
E'(kappa,lang) if and only if every algebra of cardinality kappa has
a proper elementary extension in the sense of lang.
THEOREM 1.12. For any of lang = WSOL, L_omega_1,omega, SOL, we have
E'(kappa,lang) iff E(kappa,lang), and R'(kappa,lang) iff
R(kappa,lang).
A cardinal kappa is extendible if and only if for all alpha there
exists beta and an elementary embedding from V(alpha) into V(beta)
with critical point kappa.
THEOREM 1.13. The following are equivalent.
i) for all sufficiently large kappa, E(kappa,SOL);
ii) for all sufficiently large kappa, R(kappa,SOL);
iii) there exists an extendible cardinal.
THEOREM 1.14. The following are equivalent.
i) kappa is least such that for all lambda >= kappa, E(lambda,SOL);
ii) kappa is the least extendible cardinal.
A cardinal is called totally indescribable if and only if it is
Pi-n-m indescribable for all n,m < omega.
THEOREM 1.15. Each of the following implies the next.
i) there exists a subtle cardinal;
ii) there exists a Beth number kappa such that E(kappa,SOL);
iii) there exists a totally indescribable cardinal.
THEOREM 1.16. Let kappa be the least Beth number such that
E(kappa,SOL). kappa is a totally indescribable cardinal, greater than
kappa totally indescribable cardinals, and less than any
subtle cardinal.
THEOREEM 1.17. Let kappa be least such that E(kappa,SOL). Then kappa
is a weakly Mahlo cardinal > omega and kappa is satisfied in L to be
a totally indescribable cardinal that is greater than kappa totally
indescribable cardinals.
THEOREM 1.18. Each of the following is interpretable in the next.
Each proves the consistency of the previous.
i) ZFC + there exists a totally indescribable cardinal;
ii) ZFC + there exists kappa such that E(kappa,SOL);
iii) ZFC + there exists a subtle cardinal.
We now consider R(kappa,SOL).
THEOREM 1.19. Each of the following implies the next.
i) there exists an extendible cardinal;
ii) for all sufficiently large kappa, R(kappa,SOL);
iii) there exists a nontrivial elementary embedding from some
V(kappa+kappa) into some V(alpha).
THEOREM 1.20. Let kappa be least such that for all lambda >= kappa,
R(lambda,SOL). Then there is a nontrivial elementary embedding from
V(kappa+kappa) into some V(alpha), and there is no extendible
cardinal <= kappa.
THEOREM 1.21. Each of the following implies the next.
i) there exists a third order indescribable cardinal;
ii) there exists a Beth number kappa such that R(kappa,SOL);
iii) there exists a second order indescribable cardinal.
THEOREM 1.22. Let kappa be the least Beth number such that
R(kappa,SOL). kappa is a second order indescribable cardinal, greater
than kappa second order indescribable cardinals, and less than any
third order indescribable cardinal.
THEOREM 1.23. Let kappa be least such that R(kappa,SOL). Then kappa
is a weakly Mahlo cardinal > omega and kappa is satisfied in L to be
a second order indescribable cardinal that is greater than kappa
second order indescribable cardinals.
THEOREM 1.24. Each of the following is interpretable in the next.
Each proves the consistency of the previous.
i) ZFC + there exists a third order indescribable cardinal;
ii) ZFC + there exists kappa such that E(kappa,SOL);
iii) ZFC + there exists a second order indescribable cardinal.
The following is proved by forcing.
THEOREM 1.25. Suppose ZFC + "there exists a subtle cardinal" is
consistent. Then ZFC + (therexists kappa < 2^omega)(R(kappa,SOL) &
E(kappa,SOL)) + (therexists kappa <
2^omega_1)(E(kappa,L_omega_1,omega)) is consistent.
Finally, we define
R(kappa,kappa,SOL) if and only if every algebra of cardinality kappa
has a proper restriction of cardinality kappa satisfying the same
sentences of SOL.
E(kappa,kappa,SOL) if and only if every algebra of cardinality kappa
has a proper extension of cardinality kappa satisfying the same
sentences of SOL.
THEOREM 1.26. The following are equivalent for all Beth numbers kappa.
i) R(kappa,kappa,SOL);
ii) R(kappa,kappa,SOL);
iii) there is a nontrivial elementary embedding from V(kappa+1) into
V(kappa+1).
*********************************************
I use http://www.mathpreprints.com/math/Preprint/show/ for manuscripts with
proofs. Type Harvey Friedman in the window.
This is the 161st in a series of self contained postings to FOM covering
a wide range of topics in f.o.m. Previous ones counting from #100 are:
100:Boolean Relation Theory IV corrected 3/21/01 11:29AM
101:Turing Degrees/1 4/2/01 3:32AM
102: Turing Degrees/2 4/8/01 5:20PM
103:Hilbert's Program for Consistency Proofs/1 4/11/01 11:10AM
104:Turing Degrees/3 4/12/01 3:19PM
105:Turing Degrees/4 4/26/01 7:44PM
106.Degenerative Cloning 5/4/01 10:57AM
107:Automated Proof Checking 5/25/01 4:32AM
108:Finite Boolean Relation Theory 9/18/01 12:20PM
109:Natural Nonrecursive Sets 9/26/01 4:41PM
110:Communicating Minds I 12/19/01 1:27PM
111:Communicating Minds II 12/22/01 8:28AM
112:Communicating MInds III 12/23/01 8:11PM
113:Coloring Integers 12/31/01 12:42PM
114:Borel Functions on HC 1/1/02 1:38PM
115:Aspects of Coloring Integers 1/3/02 10:02PM
116:Communicating Minds IV 1/4/02 2:02AM
117:Discrepancy Theory 1/6/02 12:53AM
118:Discrepancy Theory/2 1/20/02 1:31PM
119:Discrepancy Theory/3 1/22.02 5:27PM
120:Discrepancy Theory/4 1/26/02 1:33PM
121:Discrepancy Theory/4-revised 1/31/02 11:34AM
122:Communicating Minds IV-revised 1/31/02 2:48PM
123:Divisibility 2/2/02 10:57PM
124:Disjoint Unions 2/18/02 7:51AM
125:Disjoint Unions/First Classifications 3/1/02 6:19AM
126:Correction 3/9/02 2:10AM
127:Combinatorial conditions/BRT 3/11/02 3:34AM
128:Finite BRT/Collapsing Triples 3/11/02 3:34AM
129:Finite BRT/Improvements 3/20/02 12:48AM
130:Finite BRT/More 3/21/02 4:32AM
131:Finite BRT/More/Correction 3/21/02 5:39PM
132: Finite BRT/cleaner 3/25/02 12:08AM
133:BRT/polynomials/affine maps 3/25/02 12:08AM
134:BRT/summation/polynomials 3/26/02 7:26PM
135:BRT/A Delta fA/A U. fA 3/27/02 5:45PM
136:BRT/A Delta fA/A U. fA/nicer 3/28/02 1:47AM
137:BRT/A Delta fA/A U. fA/beautification 3/28/02 4:30PM
138:BRT/A Delta fA/A U. fA/more beautification 3/28/02 5:35PM
139:BRT/A Delta fA/A U. fA/better 3/28/02 10:07PM
140:BRT/A Delta fA/A U. fA/yet better 3/29/02 10:12PM
141:BRT/A Delta fA/A U. fA/grammatical improvement 3/29/02 10:43PM
142:BRT/A Delta fA/A U. fA/progress 3/30/02 8:47PM
143:BRT/A Delta fA/A U. fA/major overhaul 5/2/02 2:22PM
144: BRT/A Delta fA/A U. fA/finesse 4/3/02 4:29AM
145:BRT/A U. B U. TB/simplification/new chapter 4/4/02 4:01AM
146:Large large cardinals 4/18/02 4:30AM
147:Another Way 7:21AM 4/22/02
148:Finite forms by relativization 2:55AM 5/15/02
149:Bad Typo 1:59PM 5/15/02
150:Finite obstruction/statisics 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
159.Elemental Sentential Reflection
160.Similar Subclasses
More information about the FOM
mailing list