A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.

Finite Axiomatizability and Complete Theories

Research Depth 91 in the knowledge graph ☐ I know this ☆ Set as goal
2topics build on this
519prerequisites beneath it
See this on the map →
Complete First-Order TheoriesCompactness Theorem in Model Theory→→Undecidability of First-Order Theories
axiomatization completeness finiteness

Core Idea

Many natural theories are not finitely axiomatizable: Peano arithmetic, the theory of algebraically closed fields, and ZFC all require infinitely many axioms as first-order theories. By a classical result, a complete theory is finitely axiomatizable if and only if it is decidable. The compactness theorem shows finite axiomatizability implies uniformity of model structure.

Explainer

You know that a complete theory is one that decides every first-order sentence: for every sentence φ, either T ⊢ φ or T ⊢ ¬φ. And you know from compactness that if every finite subset of an infinite set of sentences has a model, then the whole set has a model. These two tools together let us ask a sharp question: when can a theory be captured by finitely many axioms, versus requiring an infinite axiom scheme?

Consider the theory of groups: three axioms (associativity, identity, inverses) — finitely axiomatizable. Now consider Peano arithmetic (PA): the axioms include the induction scheme, which is an infinite family of axioms (one for each formula φ(x) — "if φ(0) and ∀x(φ(x) → φ(x+1)) then ∀x φ(x)"). Can we replace all of these with finitely many axioms? The compactness theorem says no. If PA were equivalent to a finite set F of axioms, then F alone would have all the models that PA has. But one can construct a model that satisfies F and violates some instance of the induction scheme — a non-standard model — by compactness. More precisely, one adds a constant c and the axioms c > 0, c > 1, c > 2, … Each finite subset is satisfiable (by ordinary arithmetic with c set to a large integer), so by compactness the whole set is satisfiable, yielding an element larger than all standard naturals. A finitely axiomatized theory cannot rule this out, but the full induction scheme can.

The classical equivalence result is: a complete theory is finitely axiomatizable if and only if it is decidable. This connects two apparently different notions. The forward direction: if T is complete and finitely axiomatized, you can decide any sentence φ by running through all proofs from the finite axioms; since T is complete, eventually either a proof of φ or a proof of ¬φ will appear. The backward direction uses the fact that decidable complete theories can be "compressed" — their logical closure has a predictable structure.

A theory that *is* finitely axiomatizable tends to have uniform models: the finite axioms bound the variation in model structure. Compactness makes this precise — if a finite theory has arbitrarily large finite models, it has an infinite model, so the models form a coherent infinite family. The theory of algebraically closed fields of characteristic 0 (ACF₀) is complete but not finitely axiomatizable: it requires the axiom scheme "every polynomial of degree n has a root" for each n, plus infinitely many axioms ruling out characteristic p > 0. These infinite axiom schemes are not mere technical overhead — they are what allows the theory to pin down model structure with enough precision to be complete.

Practice Questions 5 questions

Prerequisite Chain

Understanding Zero → The Number Zero → Counting to Five → Counting to 10 → Counting to 20 → Counting a Set of Objects Up to 20 → Cardinality: The Last Number Counted → Matching Numerals to Quantities → Subitizing Small Quantities → Addition Within 10 → Number Bonds to 10 → Addition Within 20 → Doubles and Near Doubles → Doubles Facts Within 10 → Near Doubles Facts Within 20 → Mental Math Strategies for Addition → Mental Math: Adding and Subtracting Tens → Addition Within 100 → Repeated Addition as Multiplication → Multiplication as Equal Groups → Multiplication: Arrays → Basic Multiplication Facts (0s, 1s, 2s, 5s, 10s) → Multiplication Facts Within 100 → Division as Equal Sharing → Division as Grouping (Measurement Division) → Division: Grouping (Repeated Subtraction) Model → Division: Fair Sharing Model → Division as Equal Sharing → Division as Grouping → Basic Division Facts → Division Facts Within 100 → Multiplication and Division Fact Families → Relationship Between Multiplication and Division → Division Facts as Inverse of Multiplication → Remainders and Quotients in Division → Division Word Problems → Multi-Step Word Problems → Solving Multi-Step Word Problems → Multiplication Word Problems → Division Word Problems → Introduction to Long Division → Factors and Multiples → Prime and Composite Numbers → Equivalent Fractions → Relating Fractions and Decimals → Decimal Place Value → Integers and the Number Line → Comparing and Ordering Integers → Absolute Value → Adding Integers → Subtracting Integers → Multiplying Integers → Introduction to Exponents → Order of Operations → Integer Order of Operations → Variable Expressions → The Distributive Property → Variables and Expressions Review → Introduction to Polynomials → Adding and Subtracting Polynomials → Multiplying Polynomials → Factorial → Permutations → Combinations → Counting Principles: Addition and Multiplication Rules → Introduction to Graph Theory → Propositional Logic Foundations → Logical Equivalences → Boolean Algebra → Introduction to Propositional Logic → Introduction to Predicate Logic (First-Order Logic) → First-Order Logic Syntax → Terms and Atomic Formulas in FOL → Variable Binding and Scope → Open and Closed Formulas in First-Order Logic → Variable Substitution and Capture-Avoidance in First-Order Logic → Quantifier Instantiation Rules in First-Order Proof Systems → Universal Quantification: Meaning and Scope → Free Variables and Bound Variables → Substitution and Instantiation in Predicate Logic → Terms and Atomic Formulas → Formulas and Well-Formed Expressions → Structures and Interpretations → Model Interpretation and Satisfaction → Interpretation, Truth, and Satisfaction of Formulas → Logical Consequence and Entailment → Satisfiability and Unsatisfiability → Consistency and Inconsistency of Theories → Consistency and Inconsistency → Basic Model Theory → Compactness Theorem in Model Theory → Finite Axiomatizability and Complete Theories

Longest path: 92 steps · 519 total prerequisite topics

Prerequisites (2)

Leads To (1)