## 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,

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

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

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:

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

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

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.