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 $$\phi$$ is logically equivalent to both $$\exists X_1\ldots \exists X_n\,\phi_1$$ and $$\forall Y_1\ldots \forall Y_m\phi_2,$$ where $$\phi_1$$ and $$\phi_2$$ are first order. W.l.o.g.

$\{X_1,\ldots, X_n\}\cap\{Y_1,\ldots, Y_m\}=\emptyset.$

Now $$\models\phi_1\to\phi_2$$. By the Craig Interpolation Theorem there is a first order $$\theta$$ such that $$\models\phi_1\to\theta$$, $$\models\theta\to\phi_2$$, and the symbols $$X_1,$$…, $$X_n,$$ $$Y_1,$$…, $$Y_m$$ do not occur in $$\theta$$. Hence $$\phi$$ is logically equivalent with $$\theta$$.

3. Here E 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 “x is an element of y", then the “element" x must be an element of U. We can easily build a model $$\mm$$ of $$\phi_1\land\phi_2$$ as follows. Let A be a set such that $$A\cap\P(A)=\emptyset$$. Here $$\P(A)$$ denotes the power set of A. 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 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,

$E^\mm=\{(a,b)\in A\times \P(A) : a\in b\}.$

The last conjunct $$\phi_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 $$\mm$$ 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 $$\mm$$ satisfies $$\theta$$. On the other hand, suppose $$\mn$$ is an arbitrary model of $$\theta$$. Let us take a set A 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

$E^\mm=\{(a,b)\in A\times \P(A) : a\in b\}$

we obtain a model $$\mm$$ (of $$\theta$$). Let $$\pi:U^\mn\to A$$ be a bijection. 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 sentence has a model at all, it has a model of cardinality $$\le\kappa$$.

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

6. Let $$T\subseteq \ZFC$$ be finite. Let L be Gödel’s model 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)\models T$$. Such $$\lambda$$ exist, because T is finite (by the Reflection Theorem, see, e.g., Kunen 1980). Let $$(N,E)\prec (L_{\lambda},\in)$$ be countable with $$\delta\in 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',\in)$$ and $$\pi:(N,E)\cong (N',\in)$$. Let $$\eta=\pi(\delta)$$. Let $$\mm\in N'$$ be a structure for the empty vocabulary such that $$M=\eta$$. Let s be an assignment such that $$s\in N'$$, $$s(P)=\eta$$ and $$s(R)=\omega$$. Then $$(N',\in)$$ is a countable transitive model of T with an element $$\eta$$ 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.