[PDF] Recursive Logic Frames 5 oct. 2020 logic frame

View - Download Recursive Logic Frames

Previous PDF

Next PDF

Recursive Logic Frames

Saharon Shelah

y

Institute of Mathematics

Hebrew University

Jerusalem, IsraelJouko Vaananen

z

Department of Mathematics

University of Helsinki

Helsinki, Finland

October 5, 2020

Abstract

We dene the concept of alogic frame, which extends the concept of an abstract logic by adding the concept of a syntax and an axiom system. In arecursivelogic frame the syntax and the set of axioms are recursively coded. A recursive logic frame is called complete (re- cursively compact, countably compact), if every nite (respectively: recursive, countable) consistent theory has a model. We show that for logic frames built from the cardinality quantiers "there exists at least" completeness always implies countable compactness. On the other hand we show that a recursively compact logic frame need not be countably compact.

1 Introduction

For the denition of an abstract logic and a generalized quantier the reader is refereed to [4], [13], and [14]. Undoubtedly the most important among abstract logics are the ones that have a complete axiomatization of validity. This is an extended version of Preprint # 593 of the Centre de Recerca Matematica, Barcelona. The second author is grateful for the hospitality of the CRM in April 2004. yThis research was supported by The Israel Science Foundation. Publication number [ShVa:790] zResearch partially supported by grant 40734 of the Academy of Finland.

1Paper Sh:790, version 2004-10-2111. See https://shelah.logic.at/papers/790/ for possible updates.

In many cases, most notably when we combine even the simplest generalized quantiers, completeness of an axiomatization cannot be proved in ZFC alone but depends of principles like CH or}. Examples of logics that have a complete axiomatization are:

The innitary languageL!1![10].

Logic with the generalized quantier1

9 @1x(x;~y)() jfx:(x;~y)gj @1[27]:

Logic with theconality quantier

Q cof@

0xy(x;y;~z)() fhx;yi:(x;y;~z)gis a linear order

of conality@0[24]:

Logic with thecub-quantier

Q cub@

1xy(x;y;~z)() fhx;yi:(x;y;~z)gis an@1-like linear order

in which a cub of initial segments have a sup [24]:

Logic with theMagidor-Malitz quantier, assuming}

Q MM@

1xy(x;y;~z)() 9X(jXj @1^ 8x;y2X(x;y;~z)) [15]:

The extensionL(9) of rst order logic was introduced by Andrzei Mostowski in 1957. Here9is the generalized quantier

Mj=9x(x;~a)() jfb2M:Mj=(b;~a)gj :

Mostowski asked whetherL(9) is@0-compact (i.e. every countable set of sentences, every nite subset of which has a model, has itself a model) and observed thatL(9@0) is not. In 1963 Gerhard Fuhrken [7] proved that L(9) is@0-compact if@0is small for(i.e. ifn< forn < !, thenQ nLemmaY nThis quantier is usually denoted byQ1.

2Paper Sh:790, version 2004-10-2111. See https://shelah.logic.at/papers/790/ for possible updates.

for ultraltersFon!and rst order sentencescan be proved for2 L(9) if@0is small for. The@0-compactness follows from the Los Lemma immediately. Vaught [27] proved@0-compactness ofL(9@1) by proving what is now known as Vaught's Two-Cardinal Theorem and Chang [5] extended this to L(9+) by proving (!1;!)!(+;), when<=. Jensen [9] extended this to allunder the assumption GCH+2, which he showed to follow fromV=L. Keisler [11] proved with a dierent method@0-compactness of L(9) whenis a singular strong limit cardinal. This led to the important observation that if there are no inaccessible cardinals inL, thenL(9) is recursively axiomatizable and@0-compact for all > !. Also, if GCH holds, thenL(9) is@0-compact for all > !. We still do not know if this is provable in ZFC: Open Problem:Is it provable in ZFC thatL(9)is@0-compact for all > !? In particular, is it provable in ZFC thatL(9@2)is@0-compact? The best result today towards solving this problem is: Theorem 1([26]) It is consistent, relative to the consistency of ZF that

L(9@1;9@2)is not@0-compact.

and every regular cardinal is a successor cardinal (i.e. there are no weakly inaccessible cardinals), Our approach is to look for ZFC-provable relationships between complete- ness, recursive compactness and countable compactness in the context of a particular logic in the hope that such relationships would reveal important features of the logic even if we cannot settle any one of these properties per se. For example, the countable compactness of the logicL!!(9@1;9@2;9@3;:::) cannot be decided in ZFC, but we prove in ZFC that if this logic is recur- sively compact, it is countably compact. We show by example that recursive compactness does not in general imply countable compactness.

2 Logic Frames

Our concept of a logic frame captures the combination of syntax, semantics and proof theory of an extension of rst order logic. This is a very gen- eral concept and is not dened here with mathematical exactness, as we do

3Paper Sh:790, version 2004-10-2111. See https://shelah.logic.at/papers/790/ for possible updates.

not prove any general results about logic frames. All our results are about concrete examples. Denition 21. A logic frame is a tripleL=hL;j=L;Ai;where (a)hL;j=Liis a logic in the sense of Denition 1.1.1 in [4]. (b)Ais a class ofL-axioms andL-inference rules. We write`A ifis derivable using the axioms and rules inA, and call a set TofL-sentencesA-consistentif no sentence together with its negation is derivable fromT.

2. A logic frameL= (L;j=L;A)isrecursiveif

(a) There is an eective algorithm which gives for each nite vocabu- larythe setL[]and for each2 L[]a second order formula2 which denes the semantics of. (b) There is an eective algorithm which gives the axioms and rules ofA.

3. A logic frameL=hL;j=L;Aiis ah;i-logic frame, if each sen-

tence contains less thanpredicate, function and constant symbols, andjL[]j whenever the vocabularyhas less thatsymbols alto- gether.

4. A logic frameL=hL;j=L;Aiis:

(a)completeif every niteA-consistentL-theory has a model. (b)recursively compactif everyA-consistentL-theory, which is re- cursive in the set of axioms and rules, has a model. (c)(;)-compactif everyL-theory of cardinality, every subset of cardinality< of which isA-consistent, has a model. (d)countably compact, if it is(!;!)-compact.2 Second order logic represents a strong logic with an eectively dened syntax. It is not essential, which logic is used here as long as it is powerful enough.

4Paper Sh:790, version 2004-10-2111. See https://shelah.logic.at/papers/790/ for possible updates.

Note that

countable compactness recursive compactness completeness The weakest condition is thus completeness. We work in this paper al- most exclusively with complete logic frames investigating their compactness properties.

Denition 3A logic frameL=hL;j=L;Aihas

1.nite recursive characterif for every possible universe3V0

V

0j= (Lis complete)Lis recursively compact):

2.nite characterif for every possible universeV0

V

0j= (Lis complete)Lis countably compact):

3.recursive characterif for every possible universeV0

V

0j= (Lis recursively compact)Lis countably compact):

Finite (recursive) "(;)-character" means nite (respectively recursive) char- acter with "countably compact" replaced by "(;)-compact". "Strong char- acter", means(;!)-character for all.

Example 4Let

L(9+) =hL(9+);j=L(9+);A(9+)i;

where

Mj=9x(x;~y)() jfx:Mj=(x;~y)j 3

I.e. inner model or forcing extension.

5Paper Sh:790, version 2004-10-2111. See https://shelah.logic.at/papers/790/ for possible updates.

andA(9+)has as axioms the basic axioms of rst order logic and :9 +(x=y_x=z)

8x(! )!(9+x! 9+x )

9 +x(x)$ 9+y (y);where(x;:::)is a formula of

L(9+)in whichydoes not occur

9 +y9x! 9x9+y_ 9+x9y; and Modus Ponens as the only rule. The logicL(9+)was introduced by Mostowski [18] and the above frame for=@0by Keisler [12]. The logic frameL(9+)is an eectiveh!;!i-logic frame. The logic frameL(9@1)is countably compact, hence has nite character for a trivial reason. If=<, then by Chang's Two-Cardinal Theorem,L(9+)is countably compact, in fact(;!)-compact ([22]). If V=L, thenL(9+)is(;!)-compact for all (Jensen [9]). Example 5Supposeis a singular strong limit cardinal. Let

L(9) =hL(9);j=L(9);A(9)i;

whereA(9)has as axioms the basic axioms of rst order logic, a rather complicated set of special axioms (no simple set of axioms is known at present), and Modus Ponens as the only rule. The logic frameL(9)is(;!)-compact for each < ([11],[22]). Example 6Supposeis strong limit!-Mahlo4cardinal. Let

L(9) =hL(9);j=L(9);A(9)i;

whereA(9)has as axioms the basic axioms of rst order logic, axioms given in [20], and Modus Ponens as the only rule. The logic frameL(9) is(;!)-compact for each < ([21],[22]).

Example 7Supposeis a regular cardinal. Let

L(Qcof) =hL(Qcof);j=L(Qcof);A(Qcof)i;4

is 0-Mahlo if it is regular, (n+ 1)-Mahlo, if there is a stationary set ofn-Mahlo cardinals below, and!-Mahlo if it isn-Mahlo fo alln < !.

6Paper Sh:790, version 2004-10-2111. See https://shelah.logic.at/papers/790/ for possible updates.

whereMj=Qcofxy(x;y;~z)if and only iffhx;yi:Mj=(x;y;~z)gis a linear order of conality, andA(Qcof)has as axioms the basic axioms of rst order logic, the axioms from [24], and Modus Ponens as the only rule. The logic frameL(Qcof)isfullycompact i.e.(;!)-compact for all, hence has nite character for a trivial reason. ([24]).

Example 8Let

L(Qcub@

1) =hL(Qcub@

1);j=L(Qcub@1);A(Qcub@

1)i; whereMj=Qcub@

1xy(x;y;~z)if and only iffhx;yi:Mj=(x;y;~z)gis an@1-

like linear order in which a cub of initial segments have a sup, andA(Qcub@ 1) has as axioms the basic axioms of rst order logic, and axioms from [3]. The logic frameL(Qcub@

1)is countably compact ([24]), hence has nite character

for a trivial reason. We shall give explicit axioms for the logic frame later.

Example 9Magidor-Malitz quantier logic frame is

L(QMM) =hL(QMM);j=;AMMi;

where Q

MMxy(x;y;~z)() 9X(jXj ^XX fhx;yi:(x;y~z)g)

andAMMis the set of axioms and rules introduced by Magidor and Malitz in [15]. The logic frameL(QMM +)is an eectiveh!;!i-logic frame. The logic frameL(QMM +)is complete, if we assume3,3and3+, but there is a forcing extension in whichL(QMM@

1)is not countably compact [1].

Example 10Let

L =hL;j=L;Ai; whereAhas as axioms the obvious axioms and Chang's Distributive Laws, and as rules Modus Ponens, Conjunction Rule, Generalization Rule and the Rule of Dependent Choices from [10]. This an old example of a logic frame introduced by Tarski in the late 50's and studied intensively, e.g. by Karp [10]. The logic frameLis ah;i-logic frame. It is eective and(;!)- compact for all, if==!. It is complete, if=!1;=!. The logic

7Paper Sh:790, version 2004-10-2111. See https://shelah.logic.at/papers/790/ for possible updates.

frameLis complete also if

1: =+and<=, or

2: is strongly inaccessible, or

3: is weakly inaccessible,is regular and

(8 < )(8 < )(< )[10]; although in these cases the completeness is not as useful as in the case asL!! andL!1!.Lis not complete if=is a successor cardinal (D.Scott, see [10]).Lis not(;)-compact unlessis weakly compact, and then also L is(;)-compact.Lis not strongly compact unlessis and then also L is. The logic frameLis not of nite(;)-character, unless=!, since it is in some possible universes complete, but not(;)-compact. Example 11Let@0< < be compact cardinals. A sublogicL1ofL, extendingL(9), is dened in [8]. This logic is likeLin that it allowsquotesdbs_dbs33.pdfusesText_39

[PDF] s'y connaitre en

[PDF] je connais un bon

[PDF] le grand livre de l'orthographe pdf gratuit

[PDF] créance sur le trésor définition

[PDF] conte mille et une nuit shéhérazade

[PDF] création monnaie fiduciaire

[PDF] poésie ville maurice careme

[PDF] poeme sur la ville de lyon

[PDF] six sigma exemple dapplication

[PDF] la société

[PDF] cours de mathematique terminale c pdf

[PDF] tome 2 : mission azerty pdf

[PDF] la société tome 2 pdf

[PDF] la société tome 1 qui de nous deux ebook gratuit

[PDF] faites-vous ou faites vous