Movatterモバイル変換

1. Classical sources for second-order logic areHilbert& Ackermann (1938) andChurch(1956).

2. Suppose a formula \(\phi\) is logically equivalent to both \(\existsX_1\ldots \exists X_n\,\phi_1\) and \(\forall Y_1\ldots \forallY_m\phi_2,\) where \(\phi_1\) and \(\phi_2\) are first order. W.l.o.g.

Now \(\models\phi_1\to\phi_2\). By the Craig Interpolation Theoremthere is a first order \(\theta\) such that\(\models\phi_1\to\theta\), \(\models\theta\to\phi_2\), and thesymbols \(X_1,\)…, \(X_n,\) \(Y_1,\)…, \(Y_m\) do notoccur in \(\theta\). Hence \(\phi\) is logically equivalent with\(\theta\).

3. HereE is a kind of membership relation. Indeed, the formula\(\phi_1\) resembles the Axiom of Extensionality of ZFC set theory.Formula \(\phi_2\) says that if \(E(x,y)\) is read as “xis an element ofy", then the “element"x must bean element ofU. We can easily build a model \(\mm\) of\(\phi_1\land\phi_2\) as follows. LetA be a set such that\(A\cap\P(A)=\emptyset\). Here \(\P(A)\) denotes the power set ofA. Note that \(A\cap\P(A)=\emptyset\) is always the case if,for example,A is a set of singletons \(\{a_i\}\), where each\(a_i\) has cardinality 2. We let \(M=A\cup \P(A)\). As theinterpretation of the unary relation variableU we chooseA. Finally, as the interpretation of the binary relationvariableE we choose the real membership relation, that is,

The last conjunct \(\phi_3\) says that ifX is a subset ofU, then there is somey such that exactly those elementsz ofU that satisfy \(E(z,y)\) are the ones that are inX. In a sensey “codes” the setX. Inour example model \(\mm\) we would choose \(y=X\) becauseM hasall the subsets ofA as elements. In other models we may not beable to choose \(y=X\) becauseX is not an element of themodel, just a subset ofU, coded byy. In (6) thevariableX is universally quantified. The effect of this isthatevery subset ofU is coded by some element of themodel. Thus the above \(\mm\) satisfies \(\theta\). On the other hand,suppose \(\mn\) is an arbitrary model of \(\theta\). Let us take a setA such that \(|A|=|U^\mn|\). We can assume\(A\cap\P(A)=\emptyset\), as above. Let \(M=A\cup\P(A)\). By letting\(U^\mm=A\) and

we obtain a model \(\mm\) (of \(\theta\)). Let \(\pi:U^\mn\to A\) be abijection. If \(b\in N\), let \(\pi(b)=\{a\in A:E^\mn(a,b)\}\). Now\(\pi:\mn\cong\mm\).

4. The smallest cardinal \(\kappa\) such that if a second-order sentencehas a model at all, it has a model of cardinality \(\le\kappa\).

5. The smallest cardinal \(\kappa\) such that if a second-order sentencehas a model of cardinality \(\ge\kappa\), it has arbitrarily largemodels.

6. Let \(T\subseteq \ZFC\) be finite. LetL be Gödel’smodel of constructible sets. Let \(\delta\) be an ordinal such that\(L\models {}\) “\(\delta\) is uncountable”. Let\(\lambda>\delta\) be a cardinal such that \((L_\lambda,\in)\modelsT\). Such \(\lambda\) exist, becauseT is finite (by theReflection Theorem, see, e.g., Kunen 1980). Let \((N,E)\prec(L_{\lambda},\in)\) be countable with \(\delta\in N\), by theLöwenheim-Skolem Theorem of first order logic. ByMostowski’s Collapsing Lemma (see e.g. Kunen 1980), there is atransitive \((N',\in)\) and \(\pi:(N,E)\cong (N',\in)\). Let\(\eta=\pi(\delta)\). Let \(\mm\in N'\) be a structure for the emptyvocabulary such that \(M=\eta\). Lets be an assignment suchthat \(s\in N'\), \(s(P)=\eta\) and \(s(R)=\omega\). Then \((N',\in)\)is a countable transitive model ofT with an element \(\eta\)such that \((N',\in)\models “\eta\mbox{ isuncountable}”,\) hence\((N',\in)\not\models“\mm\models_s\theta_{\textrm{EC}}(P,R)”,\)that is, if second-order logic is construed inside the transitivemodel \(N'\) of the finite partT of ZFC, then in the sense of\(N'\) the assignments does not satisfy\(\theta_{\textrm{EC}}(P,R)\) in \(\mm\), but still\(\mm\models_s\theta_{\textrm{EC}}(P,R)\), because \(\eta\) is acountable ordinal.

7. Here is an example: Suppose \(\phi\) is preserved under extensions ofthen-ary predicate symbolR, i.e., if\(\mm\models\phi\) and \(\mm'\) is the result of extending thepredicateR in \(\mm\), then \(\mm'\models\phi\). Then \(\phi\)is logically equivalent with a second-order sentence \(\psi\) in whichR occurs only positively. The proof is trivial: Let \(\phi'\)be the result of replacing \(R(t_1,\ldots, t_n)\) everywhere in\(\phi\) by \(X(t_1,\ldots, t_n)\). Let \(\psi\) be the sentence

8. Suppose \(\phi\) characterizes \(\ma\) up to isomorphism. Suppose theconstant, predicate and function symbols of \(\phi\) are \(c_1,\ldots,c_n,R_1,\ldots, R_m, F_1,\ldots, F_k\). Let us replace in \(\phi\)constant symbols by individual variables, predicate symbols byrelation variables and function symbols by function variablesobtaining \(\phi'\). Let \(\phi^*\) be the sentence

Note that \(\phi^*\) is a sentence of the empty vocabulary. If astructure (B) of the empty vocabulary satisfies \(\phi^*\), thestructure can be expanded to a model \(\mb\) of \(\phi\). Then\(\mb\cong\ma\), whence \(|B|=|A|\). Conversely, ifB is a setsuch that there is a bijection \(\pi:A\to B\), then \(\pi\) can beused to copy the structure of \(\ma\) onto (B) resulting in astructure \(\mb\). By construction, \(\mb\cong\ma\), whence\(\mb\models\phi\). Clearly now \((B)\models\phi^*\). We have shownthat \(\phi^*\) characterizes the cardinal \(|A|\) (i.e., thestructure of cardinality \(|A|\) of the empty vocabulary) up toisomorphism.

9. W.l.o.g. \(M=\kappa\). Since \(\kappa\) is measurable, there is anelementary embedding \(j:V\to N\) withN transitive and\({}^\kappa N\subseteq N\). Thus \(\mm\in N\). On the other hand\(N\models “j(\mm)\models\phi”\). Also \(N\models“\mm\models\phi”\). Clearly \(\mm\subseteq j(\mm)\). ThusinN the model \(j(\mm)\) has a submodel which containsX, is of size \(<j(\kappa)\) and is a model of \(\phi\).Sincej is elementary, \(\mm\) has a submodel of size\(<\kappa\) which containsX and is a model of \(\phi\).

10. A cardinal \(\kappa\) is weakly compact if it is stronglyinaccessible and every \(\kappa\)-tree, i.e., tree of height\(\kappa\) in which the levels have cardinality \(<\kappa\) has abranch of length \(\kappa\). We can express weak compactness of\(\kappa\) with a second-order sentence \(\phi\). Since \(\lambda\) isweakly compact, \((\lambda)\models\phi\). There cannot be a smallermodel of \(\phi\), because \(\lambda\) is the smallest weakly compactcardinal.

11. If a set-theoretical proof involves a setA, we can withouthesitation also consider the power set \(\P(A)\) and even the doublepower set \(\P(\P(A))\). In second-order logic the situation isdifferent. If we have a setA of individuals, we can talk aboutits subsets but we cannot collect them together into the power set\(\P(A)\). We can do it in third order logic, but then we cannot form\(\P(\P(A))\).

12. Mirroring means here the existence of translations in bothdirections. We shall now define these translations. To simplifynotation, let us assume that the individual variables of second-orderlogic are \(x_1,\) \(x_2,\)…, the constant symbols are \(c_1,\)\(c_2,\)…, then-ary relation variables are \(X^n_1,\)\(X^n_2,\)…, and then-ary function variables are\(F^n_1,\) \(F^n_2,\)…. Respectively, let the variables of ourmany-sorted logic be as follows:

Let \(\Gamma\) consist of the following first order sentences:

for \(n,m,k\in\oN\). We define a translation \(\phi\mapsto\phi^*\)from second-order logic to many-sorted logic as follows:

• \(x_n^*\) is \( v_n\), \(c^*_n=c_n\),
• \(F^n_m(t_1,\ldots, t_n)^*\) is \( \sF(t^*_1,\ldots,t^*_n,u^n_m)\),
• \(X^n_m(t_1,\ldots, t_n)^*\) is \( \sA(t^*_1,\ldots,t^*_n,w^n_m)\),
• \((t_1=t_2)^*\) is \( t^*_1=t^*_2\),
• \(R(t_1,\ldots, t_n)^*\) is \( R(t^*_1,\ldots, t^*_n)\),
• \((\neg\phi)^*\) is \( \neg\phi^*\),
• \((\phi\land\psi)^*\) is \( \phi^*\land\psi^*\),

similarly for \((\phi\lor\psi)^*\), \((\phi\to\psi)^*\), and\((\phi\leftrightarrow\psi)^*\),

• \((\exists x_n\,\phi)^*\) is \( \exists v_n\,\phi^*\),
• \((\exists X^n_m\,\phi)^*\) is \( \exists w^n_m\,\phi^*\),
• \((\exists F^n_m\,\phi)^*\) is \( \exists u^n_m\,\phi^*\),

similarly for \((\forall x_n\,\phi)^*\), \((\forall X^n_m\,\phi)^*\),and \((\forall F^n_m\,\phi)^*\).

A model \(\mm\) of \(\Gamma\) gives rise to a general model\((\mm^{\textrm{ms}}, \G^{\textrm{ms}})\) with\(M_{s^{\textrm{ind}}}\) as the domain and \(\G^{\textrm{ms}}\)consisting for each \(n\in\oN\) of the relations

where \(b\in M_{s^{\textrm{rel}}_n}\), and of the functions \(f:M_{\si}^n\to M_{\si}\) such that

where \(b\in M_{\sr}\). Conversely, every general model is of the form\((\mm^{\text{ms}},\G^{\text{ms}})\) for some many sorted model\(\mm\) of \(\Gamma\). Now for all second-order sentences \(\phi\) andall models \(\mm\) of \(\Gamma\) we have

Similarly to \(\phi\mapsto\phi^*\) there is also a translation fromthe many-sorted logic into second-order logic.

13. The proof is just as the proof given by Henkin for the CompletenessTheorem of first order logic. Suppose we have a countable theory whichis consistent in the sense that no contradiction can be derived. Weadd new constant symbols as witnesses for existential formulas\(\exists x\,\phi\), new predicate symbols as witnesses forexistential formulas \(\exists X\,\phi\), and new function symbols aswitnesses for existential formulas \(\exists F\,\phi\). Then we extendto a maximal consistent theory. From this we can form a general modelby using the new constants as the building blocks of the domain ofindividuals to get a model \(\mm\), the new predicate an functionsymbols as the building blocks of the \(\G\). Naturally, notall sets of individual end in \(\G\), only those that theconstruction yields as necessary witnesses. An alternative to thisproof is a translation of second-order logic to many sorted logic.Then one can use the Completeness Theorem of many sorted logic.

14. Every set of second-order sentences, every finite subset of which hasa Henkin model, has itself a Henkin model.

15. If a second-order sentence has a Henkin model \((\mm,\G)\) withM infinite, it has Henkin models \((\mm,\G)\) withM anyinfinite cardinal.

16. By the upward Löwenheim-Skolem Theorem, ifM is infinite,\(\textit{Mod}_H(\phi)\) has Henkin models of all infinitecardinalities.

17. I.e., \(\pi(x)=x\) for all \(x\in E\).

18. To prove the equivalence, let us first assume \(\theta(P)\) iscategorical and \(\mm\) is an arbitrary model. We show\(\mm\models\categ(\theta(P))\). For this, consider values \(R=s(P)\)and \(R'=s(P')\) of the variablesP and \(P'\) in \(\mm\). Let\(A=s(U)\) and \(A'=s(U')\) be values of the variablesU and\(U'\) in \(\mm\). Assume

Let \(\ma\) haveA as the domain and \(R\cap (A\times A)\) asthe interpretation ofP. Let \(\ma'\) have \(A'\) as the domainand \(R'\cap (A'\times A')\) as the interpretation ofP. Now\(\ma\models\theta(P)\) and \(\ma'\models\theta(P)\). By categoricitythere is an isomorphism \(\pi:\ma\cong\ma'\). By letting \(s(F)=\pi\)we see that

For the converse, suppose \(\models\categ(\theta(P))\). Let \(\ma\)and \(\ma'\) be two arbitrary models of \(\theta(P)\). We define amodel \(\mm\) of the empty vocabulary by letting \(M=A\cup A'\). Byassumption,

Let

Since

we have

Thus there is \(f:M\to M\) such that \(f\restriction A\) demonstratesthe isomorphism \(\ma\cong\ma'\).

19. The \(\Delta\)-extension of a logic \(\mathcal{L}\) is the smallestextension of \(\mathcal{L}\) to a logic \(\mathcal{L'}\) in whichevery model class, i.e., class of models of a fixed vocabulary whichis closed under isomorphisms, which is, and the complement of whichis, a class of (possibly many-sorted) reducts of an\(\mathcal{L}\)-definable model class, i.e., a class of all models ofa sentence of \(\mathcal{L}\), is definable. Such an \(\mathcal{L'}\)is denote \(\Delta(\mathcal{L})\). It can be shown that the\(\Delta\)-operation preserves many properties of logics, seeMakowsky,Shelah, and Stavi (1976).

20. The Löwenheim number of second-order logic is obviously\(>2^\omega\), i.e., there is a sentence \(\phi \) of second-orderlogic that has models but none of size \(\le 2^\omega\). If theLöwenheim number of a sublogic of second-order logic is\(<2^\omega\), then there cannot be any sentence of the sublogicequivalent to \(\phi\), and in this sense the sublogic is weaker thansecond-order logic.

21. This theorem states that every bounded sequence of real numberscontains a convergent subsequence.