Processing math: 26%

Notes to Second-order and Higher-order Logic

1. Classical sources for second-order logic are Hilbert & Ackermann (1938) and Church (1956).

2. Suppose a formula ϕ is logically equivalent to both X1Xnϕ1 and Y1Ymϕ2, where ϕ1 and ϕ2 are first order. W.l.o.g.

{X1,,Xn}{Y1,,Ym}=.

Now ϕ1ϕ2. By the Craig Interpolation Theorem there is a first order θ such that ϕ1θ, θϕ2, and the symbols X1,…, Xn, Y1,…, Ym do not occur in θ. Hence ϕ is logically equivalent with θ.

3. Here E is a kind of membership relation. Indeed, the formula ϕ1 resembles the Axiom of Extensionality of ZFC set theory. Formula ϕ2 says that if E(x,y) is read as “x is an element of y", then the “element" x must be an element of U. We can easily build a model M of ϕ1ϕ2 as follows. Let A be a set such that AP(A)=. Here P(A) denotes the power set of A. Note that AP(A)= is always the case if, for example, A is a set of singletons {ai}, where each ai has cardinality 2. We let M=AP(A). As the interpretation of the unary relation variable U we choose A. Finally, as the interpretation of the binary relation variable E we choose the real membership relation, that is,

EM={(a,b)A×P(A):ab}.

The last conjunct ϕ3 says that if X is a subset of U, then there is some y such that exactly those elements z of U that satisfy E(z,y) are the ones that are in X. In a sense y “codes” the set X. In our example model M we would choose y=X because M has all the subsets of A as elements. In other models we may not be able to choose y=X because X is not an element of the model, just a subset of U, coded by y. In (6) the variable X is universally quantified. The effect of this is that every subset of U is coded by some element of the model. Thus the above M satisfies θ. On the other hand, suppose N is an arbitrary model of θ. Let us take a set A such that |A|=|UN|. We can assume AP(A)=, as above. Let M=AP(A). By letting UM=A and

EM={(a,b)A×P(A):ab}

we obtain a model M (of θ). Let π:UNA be a bijection. If bN, let π(b)={aA:EN(a,b)}. Now π:NM.

4. The smallest cardinal κ such that if a second-order sentence has a model at all, it has a model of cardinality κ.

5. The smallest cardinal κ such that if a second-order sentence has a model of cardinality κ, it has arbitrarily large models.

6. Let TZFC be finite. Let L be Gödel’s model of constructible sets. Let δ be an ordinal such that Lδ is uncountable”. Let λ>δ be a cardinal such that (Lλ,)T. Such λ exist, because T is finite (by the Reflection Theorem, see, e.g., Kunen 1980). Let (N,E)(Lλ,) be countable with δN, by the Löwenheim-Skolem Theorem of first order logic. By Mostowski’s Collapsing Lemma (see e.g. Kunen 1980), there is a transitive (N,) and π:(N,E)(N,). Let η=π(δ). Let MN be a structure for the empty vocabulary such that M=η. Let s be an assignment such that sN, s(P)=η and s(R)=ω. Then (N,) is a countable transitive model of T with an element η such that (N',\in)\models “\eta\mbox{ is uncountable}”, hence (N',\in)\not\models“\mm\models_s\theta_{\textrm{EC}}(P,R)”, that is, if second-order logic is construed inside the transitive model N' of the finite part T of ZFC, then in the sense of N' the assignment s does not satisfy \theta_{\textrm{EC}}(P,R) in \mm, but still \mm\models_s\theta_{\textrm{EC}}(P,R), because \eta is a countable ordinal.

7. Here is an example: Suppose \phi is preserved under extensions of the n-ary predicate symbol R, i.e., if \mm\models\phi and \mm' is the result of extending the predicate R in \mm, then \mm'\models\phi. Then \phi is logically equivalent with a second-order sentence \psi in which R 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

\exists X(\forall x_1\ldots\forall x_n(X(x_1,\ldots, x_n)\to R(x_1,\ldots, x_n))\land\phi').

8. Suppose \phi characterizes \ma up to isomorphism. Suppose the constant, 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 by relation variables and function symbols by function variables obtaining \phi'. Let \phi^* be the sentence

\exists x_1\ldots \exists x_n\,\exists X_1\ldots\exists X_m\,\exists F_1\ldots F_k\phi'.

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

9. W.l.o.g. M=\kappa. Since \kappa is measurable, there is an elementary embedding j:V\to N with N 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). Thus in N the model j(\mm) has a submodel which contains X, is of size <j(\kappa) and is a model of \phi. Since j is elementary, \mm has a submodel of size <\kappa which contains X and is a model of \phi.

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

11. If a set-theoretical proof involves a set A, we can without hesitation also consider the power set \P(A) and even the double power set \P(\P(A)). In second-order logic the situation is different. If we have a set A of individuals, we can talk about its 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 both directions. We shall now define these translations. To simplify notation, let us assume that the individual variables of second-order logic are x_1, x_2,…, the constant symbols are c_1, c_2,…, the n-ary relation variables are X^n_1, X^n_2,…, and the n-ary function variables are F^n_1, F^n_2,…. Respectively, let the variables of our many-sorted logic be as follows:

The variables of sort \si are v_1,v_2,\ldots, the n-ary relation variables are w^n_1,w^n_2,\ldots, and the n-ary function variables are u^n_1,u^n_2,\ldots.

Let \Gamma consist of the following first order sentences:

\begin{align} &\exists v_1(v_1=c_n), \\ &\forall w^n_m\forall w^n_k(\forall x_1\ldots\forall x_n(\sA(x_1,\ldots, x_n,w^n_m)\leftrightarrow \sA(x_1,\ldots, x_n,w^n_k))\\ &\qquad\to w^n_m=w^n_k), \\ &\forall u^n_m\forall u^n_k(\forall x_1\ldots\forall x_n(\sF(x_1,\ldots, x_n,u^n_m)=\sF(x_1,\ldots, x_n,u^n_k))\to u^n_m=u^n_k) \\ \end{align}

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(t_1,\ldots, t_n)^* is \sF(t^*_1,\ldots, t^*_n,u_n),
  • X_n(t_1,\ldots, t_n)^* is \sA(t^*_1,\ldots, t^*_n),
  • (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\,\phi)^* is \exists w_n\,\phi^*,
  • (\exists F_n\,\phi)^* is \exists u_n\,\phi^*,

similarly for (\forall x_n\,\phi)^*, (\forall X_n\,\phi)^*, and (\forall F_n\,\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

\{(a_1,\ldots,a_n) \in M_{s^{\text{ind}}}^n: \mm\models \sA(a_1,\ldots,a_n,b)\},

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

f(a_1,\ldots,a_n)= \sF(a_1,\ldots,a_n,b),

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 and all models \mm of \Gamma we have

(\mm^{\textrm{ms}},\G^{\textrm{ms}})\models\phi\iff \mm\models\phi^*.

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

13. The proof is just as the proof given by Henkin for the Completeness Theorem of first order logic. Suppose we have a countable theory which is consistent in the sense that no contradiction can be derived. We add new constant symbols as witnesses for existential formulas \exists x\,\phi, new predicate symbols as witnesses for existential formulas \exists X\,\phi, and new function symbols as witnesses for existential formulas \exists F\,\phi. Then we extend to a maximal consistent theory. From this we can form a general model by using the new constants as the building blocks of the domain of individuals to get a model \mm, the new predicate an function symbols as the building blocks of the \G. Naturally, not all sets of individual end in \G, only those that the construction yields as necessary witnesses. An alternative to this proof 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 has a Henkin model, has itself a Henkin model.

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

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

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

18. To prove the equivalence, let us first assume \theta(P) is categorical 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 variables P and P' in \mm. Let A=s(U) and A'=s(U') be values of the variables U and U' in \mm. Assume

\mm\models_s\theta(P)^{(U)}\land\theta(P')^{(U')}.

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

\mm\models_s\isom(U,P,U',P').

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

\mm\models\categ(\theta(P)).

Let

\begin{aligned} s(U)&=A, \\ s(U')&=A', \\ s(P)&=P^\ma, \\ s(P')&=P^{\ma'}.\\ \end{aligned}

Since

\mm\models\categ(\theta(P)),

we have

\mm\models_s\isom(U,P,U',P').

Thus there is f:M\to M such that f\restriction A demonstrates the isomorphism \ma\cong\ma'.

19. The \Delta-extension of a logic \mathcal{L} is the smallest extension of \mathcal{L} to a logic \mathcal{L'} in which every model class, i.e., class of models of a fixed vocabulary which is closed under isomorphisms, which is, and the complement of which is, a class of (possibly many-sorted) reducts of an \mathcal{L}-definable model class, i.e., a class of all models of a 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, see Makowsky, 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-order logic that has models but none of size \le 2^\omega. If the Löwenheim number of a sublogic of second-order logic is <2^\omega, then there cannot be any sentence of the sublogic equivalent to \phi, and in this sense the sublogic is weaker than second-order logic.

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

Copyright © 2019 by
Jouko Väänänen <jouko.vaananen@helsinki.fi>

This is a file in the archives of the Stanford Encyclopedia of Philosophy.
Please note that some links may no longer be functional.
[an error occurred while processing the directive]