Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 16H (Logic and Set Theory)

A sentence is a formula with no free variables. Thus its truth in an $L$-structure does not depend on a variable assignment.

A theory in $L$ is a set of $L$-sentences. Here a theory need not already contain every sentence derivable from it.

An $L$-structure $M$ is a model of $T$ when

A theory $T$ is consistent when no contradiction is derivable from it, equivalently when $T⊬\perp$. In a classical proof system this is also equivalent to there being no sentence $\sigma$ for which both $T⊢\sigma$ and $T⊢\neg \sigma$.

Suppose first that $M\models T$. By the soundness theorem for first-order logic, every theorem of $T$ is true in $M$. A contradiction cannot be true in a structure, so $T$ is consistent.

Conversely, the Godel completeness theorem says that every semantically valid consequence is derivable. Its equivalent model-existence form says directly that every consistent first-order theory has a model. Hence

The compactness theorem states that a set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model.

The forward implication follows by using the same model for every finite subset. Conversely, suppose every finite subset of $T$ has a model. If $T$ were inconsistent, a formal derivation of $\perp$ from $T$ would use only finitely many assumptions, say those in $T_0\subseteq T$. Then $T_0$ would be inconsistent. By part (b), $T_0$ would have no model, contrary to the hypothesis. Thus $T$ is consistent, and part (b) gives a model of $T$.

Take $T_f$ to consist of $T$ together with the following sentences.

This includes $f(c)=c$ for each constant symbol $c$.

The first pair of axioms makes the interpretation $\vartheta$ a bijection. The remaining schemes say exactly that it preserves every operation and relation, so $(M,\vartheta )\models T_f$ exactly when $M\models T$ and $\vartheta \in \mathrm{Aut}(M)$.

Finally, $T$ is consistent and hence has a model $M$ by part (b). Expanding $M$ by interpreting $f$ as the identity automorphism gives a model of $T_f$, so $T_f$ is consistent.

A model of $T_G$ consists of a model $M\models T$ and automorphismssuch that ${\vartheta }_g{\vartheta }_h={\vartheta }_{gh}$ and ${\vartheta }_g\ne {\vartheta }_h$ whenever $g\ne h$. Thus $g\mapsto {\vartheta }_g$ is an injective homomorphism $G\hookrightarrow \mathrm{Aut}(M)$. Conversely, any such embedding supplies interpretations of the $f_g$ and hence a model of $T_G$.

Therefore $G$ is $T$-good exactly when $T_G$ has a model. By part (b), this is equivalent to consistency of $T_G$, and hence

Suppose $T_G$ is inconsistent. By the compactness theorem, some finite subset $\Delta \subseteq T_G$ is inconsistent. Only finitely many added symbols $f_g$ occur in $\Delta$; let $X\subseteq G$ be the finite set of their indices. Every sentence of $\Delta$ belongs to the sublanguage $L_X$, soConsequently $T_G\cap L_X$ is inconsistent.

If $T_G\cap L_X$ is inconsistent for some finite $X\subseteq G$, then its superset $T_G$ is inconsistent. Together with parts (i) and (ii), this proves the equivalence of all three conditions.

We describe a collection of finite multiplication patterns. For finite setswriteCall $(E,D)$ $T$-forbidden if the following theory, in $L$ expanded by unary symbols $f_1,\dots ,f_n$, is inconsistent:

Let $T^{\ast }$ contain the group axioms and, for every $T$-forbidden finite pattern, the sentenceThis is a first-order theory in the language of groups.

Suppose $G$ is $T$-good. Choose $M\models T$ and an embedding $\rho :G\hookrightarrow \mathrm{Aut}(M)$. If a tuple $(g_1,\dots ,g_n)$ in $G$ realized a forbidden pattern, interpreting $f_i$ as $\rho (g_i)$ would give a model of its supposedly inconsistent automorphism theory. Thus no such tuple exists, and $G\models T^{\ast }$.

Conversely, suppose $G$ is $T$-bad. By part (e), there is a finite set $X=\{g_1,\dots ,g_n\}\subseteq G$ for which $T_G\cap L_X$ is inconsistent. LetThe associated automorphism theory is precisely $T_G\cap L_X$, up to renaming its function symbols, so $(E,D)$ is $T$-forbidden. But $(g_1,\dots ,g_n)$ realizes $P_{E,D}$ in $G$, and therefore $G$ violates the corresponding forbidding axiom. Hence $G/\models T^{\ast }$.

We have proved