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

One Hilbert axiomatization of classical propositional logic uses the schemas $A\to (B\to A)$, $[A\to (B\to C)]\to [(A\to B)\to (A\to C)]$ and $(\neg B\to \neg A)\to (A\to B)$, with modus ponens as its inference rule. Other connectives can be defined from implication and negation. Syntactic entailment $\Gamma ⊢A$ means that a finite formal proof derives $A$ from the schemas and members of $\Gamma$. Consistency means that no formula and its negation are both derivable, equivalently no contradiction is derivable.

Use the standard deduction theorem, closure of derivability under modus ponens, and the maximal-consistency properties: a maximal consistent set contains exactly one of $A,\neg A$, is closed under derivability, and satisfies $A\to B\in \Phi$ exactly when $A\notin \Phi$ or $B\in \Phi$. These follow from the deduction theorem and the classical schemas; in particular adjoining a missing formula to a maximal set must yield a contradiction. Define $v(p)=T$ iff $p\in \Phi$. Induction on formula construction now provesFor negation use the exactly-one property, and for implication use its displayed membership rule, which is precisely the Boolean truth table. Thus every member of $\Phi$ is true under $v$, providing the required valuation.

Add to the group axioms the sentences $\forall x(x^n=e\Rightarrow x=e)$ for every $n\ge 2$. Their models are precisely the torsion-free groups. This theory is not finitely axiomatizable. If a finite sentence or finite theory were equivalent to it, the compactness theorem would imply that finitely many of these power axioms already entailed the proposed axiomatization. A cyclic group of prime order greater than all the finitely listed exponents satisfies those power axioms but is not torsion-free, a contradiction.

The class of all torsion groups is not first-order axiomatizable at all. If a theory $T$ axiomatized it, add a new constant $c$ and the sentences $c^n\ne e$ for all $n\ge 1$. Every finite subset has a model: use a cyclic group of sufficiently large prime order, with $c$ a generator. Compactness gives a model of all of $T$ in which $c$ has infinite order, contradicting the claimed torsion property. These conclusions concern the ordinary first-order language of groups.