Questions: Finite Axiomatizability and Complete Theories

Question 1

A logician claims that Peano arithmetic (PA) can be replaced by a finite set of equivalent axioms. Why does the compactness theorem refute this claim?

• A. The compactness theorem says PA is incomplete, so it cannot be finitely axiomatized
• B. By compactness, one can construct a model satisfying any finite subset of PA's axioms yet containing non-standard elements that violate some instance of the induction scheme — no finite axiom set can rule this out
• C. The compactness theorem applies only to uncountable languages, and PA is countable
• D. Compactness implies PA is categorical, meaning all its models are isomorphic to the standard natural numbers

Answer: (B)

The argument: suppose PA were equivalent to a finite set F. Add to the language a constant c and the infinite set of sentences {c > 0, c > 1, c > 2, ...}. Every finite subset is satisfiable (interpret c as a large standard integer). By compactness, the whole set is satisfiable — giving a model of F with a non-standard element c larger than every standard natural. But the full induction scheme would exclude this non-standard element, while the finite set F cannot. So F is not equivalent to PA.

Question 2

A theory T is complete and finitely axiomatizable. What follows from these two properties together?

• A. T has only finitely many models up to isomorphism
• B. T is decidable — there is an algorithm to determine, for any sentence φ, whether T ⊢ φ
• C. T is categorical — all models of T are isomorphic to each other
• D. T has no infinite models

Answer: (B)

The classical equivalence: a complete theory is finitely axiomatizable if and only if it is decidable. The forward direction is straightforward: enumerate all proofs from the finite axiom set. Since T is complete, for any sentence φ, either a proof of φ or a proof of ¬φ will eventually appear — giving a decision procedure. Categoricity (all models isomorphic) and finiteness of models are separate, stronger conditions that don't follow. Many complete, finitely axiomatizable theories have infinitely many non-isomorphic models.

Question 3

The theory of algebraically closed fields of characteristic 0 (ACF₀) is complete but requires infinitely many axioms because each degree n requires its own axiom asserting that every degree-n polynomial has a root.

• T. True
• F. False

Answer: True

ACF₀ is indeed complete (proved by Tarski via quantifier elimination) but not finitely axiomatizable. It requires: (1) the field axioms (finitely many); (2) for each n ≥ 1, the axiom 'every monic polynomial of degree n has a root' (infinitely many); (3) for each prime p, the axiom 'the characteristic is not p' (infinitely many). The infinite axiom schemes are not redundant — they jointly pin down model structure precisely enough to make the theory complete.

Question 4

A finitely axiomatizable theory can seldom have any infinite models, since finitely many axioms can mainly describe structures of bounded size.

• T. True
• F. False

Answer: False

This is a common misconception. Finitely many axioms can — and typically do — have infinite models. The group axioms (three sentences) have infinite models. The field axioms have infinite models like ℝ and ℂ. The compactness theorem actually shows the opposite: if a finite theory has arbitrarily large finite models, it must have an infinite model. What finite axiomatizability constrains is the logical structure of the theory, not the size of its models.

Question 5

Explain why the compactness theorem implies that Peano arithmetic cannot be finitely axiomatized, using the concept of non-standard models.

Model answer: Suppose PA were finitely axiomatizable by a set F. Expand the language with a new constant symbol c and add the infinite set of sentences Σ = {c > n : n ∈ ℕ} (one sentence for each standard natural number). Every finite subset of F ∪ Σ is satisfiable: take the standard natural numbers as a model and interpret c as any sufficiently large integer. By the compactness theorem, the entire set F ∪ Σ has a model M. In M, c is an element greater than every standard natural — a non-standard element. M satisfies all of F but contains this non-standard element. However, the full induction scheme in PA would derive a contradiction from the existence of such an element (induction on the predicate 'x < c' would show no natural number is less than c, contradicting the successor structure). Since F cannot rule out non-standard elements but PA can, F is strictly weaker than PA and not equivalent to it.

The key move is using compactness to build a non-standard model of any finite fragment of PA. This technique — adding a constant and infinitely many lower bounds, then applying compactness — is a general method for showing theories are not finitely axiomatizable. It demonstrates that the infinite induction scheme does genuine logical work: each instance excludes a specific kind of non-standard behavior that no finite set of axioms can collectively exclude.