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\) 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:

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 v_1\ldots\forall v_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 v_1\ldots\forall v_n(\sF(x_1,\ldots, x_n,u^n_m)=\sF(x_1,\ldots, x_n,u^n_k))\\ &\qquad\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_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

\[\{(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

\[ s(U)=A, s(U')=A', s(P)=P^\ma, s(P')=P^{\ma'}. \]

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.