Fact-checked by Grok 2 weeks ago

Complete theory

In , a complete theory is a consistent theory T in a L such that for every L-sentence \phi, either T \models \phi or T \models \neg \phi, meaning the theory decides the truth value of every sentence in its . This property ensures that all models of T are elementarily equivalent, sharing the same properties up to elementary equivalence. Complete theories form a of , enabling the classification of structures based on their logical properties and facilitating the study of model classes through tools like . A key result, the Löś–Vaught test, states that if a theory T has only models and is \kappa-categorical for some \kappa \geq |L|, then T is complete. This categoricity condition implies that up to , T has a unique model of cardinality \kappa, highlighting the theory's structural uniformity. Furthermore, complete theories are often analyzed via notions of , such as \omega- or o-minimality, which describe the complexity of definable sets in their models and influence applications in , , and . Prominent examples of complete theories include the theory of dense linear orders without endpoints, which axiomatizes structures like the rational numbers \mathbb{Q}; the theory of algebraically closed fields of a fixed , encompassing fields like the complex numbers \mathbb{C}; real closed fields, such as the real numbers \mathbb{R}; and the theory of true arithmetic, capturing the standard model of Peano arithmetic. These examples illustrate how complete theories arise in diverse mathematical domains, providing a logical framework to explore isomorphisms, embeddings, and . Historically, the of completeness criteria, including Vaught's test and Shelah's , has deepened understanding of these theories, with significant advancements in the late 20th century through works on and categoricity.

Definition and Properties

Definition

In first-order logic, a theory T in a language L is complete if, for every sentence \phi in L, either T \vdash \phi or T \vdash \neg \phi. This formal condition ensures that the theory provides a definitive answer—via deduction—for every possible assertion expressible in its language. The intuition behind completeness is that such a theory resolves all propositions within its scope, eliminating any ambiguity or undecidability internal to T; no sentence remains "open" in the sense that both it and its negation are consistent with the theory. Unlike maximal theories, which are defined as maximal consistent extensions and thus inherently consistent while incorporating all logical consequences of their axioms, completeness imposes no such consistency requirement and does not necessitate encompassing every possible truth in the language. The concept of a complete theory emerged from foundational developments in during the 1930s and 1940s, primarily through the work of and his collaborators at the Warsaw School, who explored semantic notions of truth, consequence, and structure in formal languages.

Basic Properties

A complete theory in is necessarily consistent, as the standard definition identifies it with a maximally consistent set of sentences that decides every without deriving a . Complete theories are deductively closed, meaning they contain all logical consequences of their axioms; for any \phi, if the theory proves \phi, then \phi belongs to the . If T is a complete and consistent , then any consistent extension T' of T must equal T and is therefore complete, since adding any new to T would contradict its completeness and lead to inconsistency. By Lindenbaum's lemma, every consistent admits at least one complete extension, constructed by maximally enlarging the while preserving , though such completions are generally not unique, as multiple maximal consistent supersets may exist depending on the choice of added . Non-trivial complete cannot be finitely axiomatizable; assuming a finite axiomatization leads to a via the , as the finite axioms could not enforce the infinite array of required for in with infinite models, whereas trivial complete —those with models of fixed finite —are finitely axiomatizable.

Characterizations

Standard Characterization

A consistent first-order theory T is complete if and only if every pair of models of T is elementarily equivalent, that is, they satisfy exactly the same sentences. In symbols, for any models M, N \models T, M \equiv N. This equivalence means that the theory T uniquely determines the properties of its models up to logical indistinguishability. A proof sketch for the proceeds in two directions. First, assume T is . Let M, N \models T and let \phi be any sentence with M \models \phi. Since T is and consistent, T \models \phi (for if T \models \neg \phi, then M \models \neg \phi, a contradiction). Thus, N \models \phi as well. For the converse, assume all models of T are elementarily equivalent. For any sentence \phi, either every model satisfies \phi (so T \models \phi) or no model does (so T \models \neg \phi); hence T is . This relies on the and of , ensuring that semantic entailment aligns with syntactic deduction. A direct is that complete theories possess a unique complete extension describing the of their models, up to elementary equivalence. Equivalently, T is complete if T = \mathrm{[Th](/page/TH)}(M) for some model M \models T.

Equivalent Conditions

A T is complete if and only if every true in some model of T is provable from T. This follows from the fact that ensures all models of T are elementarily equivalent, so any satisfied in one model holds in all models and thus is a of T; conversely, if a \phi is consistent with T but not provable, then \phi holds in some model, implying by the principle that T \vdash \phi, yielding . For theories that admit (meaning every is equivalent modulo T to a quantifier-free ), T is complete its quantifier-free fragment decides every quantifier-free . This equivalence arises because quantifier elimination reduces all definable sets to quantifier-free ones, making the logical consequences of T determined by the atomic diagram of its models. Regarding types, a complete theory T connects to the omitting types theorem, which states that for countable complete T, every non-principal consistent type can be omitted in some countable model of T. A type p(x) is omitted in a model M of T if there exists no a \in M such that M \models p(a). In theories, where every consistent type is principal (isolated by a single ), a countable such is complete and admits a prime model that elementarily embeds into every other model, reflecting the isolation of all types.

Examples

Notable Complete Theories

The theory of dense linear orders without endpoints, often denoted , is axiomatized by the axioms of linear orders together with the density stating that between any two distinct s there exists another , and the absence of endpoints ensuring no minimal or maximal s exist. This is complete because any two countable models are isomorphic, a consequence of its in the language of strict orders. The rational numbers under the usual order form a prime model of , illustrating its structure as a countable dense order without boundaries. For a fixed prime p, the theory of algebraically closed fields of characteristic p, denoted ACF_p, consists of the axioms for fields together with the axiom schema asserting that every non-constant polynomial has a root. ACF_p is complete due to its quantifier elimination in the language of rings, which ensures that all models are elementarily equivalent. The algebraic closure of the finite field \mathbb{F}_p provides a prototypical example, highlighting the theory's focus on fields where polynomials factor completely into linear terms. The theory of real closed fields, RCF, axiomatizes ordered fields where every positive element has a , every odd-degree has a root, and the ordering is compatible with the field operations. This theory is complete, as established by Tarski, through in the language of ordered rings, making it the theory of the real numbers as an . The real algebraic numbers ordered by magnitude exemplify a dense submodel, underscoring RCF's role in capturing ordered structures intermediate between and reals. True arithmetic, denoted Th(\mathbb{N}), is the set of all first-order sentences in the language of arithmetic (with successor, addition, and multiplication) that are true in the standard model of natural numbers. It is complete because every sentence in this language is either true or false in \mathbb{N}, so Th(\mathbb{N}) decides all such sentences decisively. However, unlike the previous examples, Th(\mathbb{N}) is not recursively axiomatizable, as its axioms are precisely the true sentences, which cannot be effectively listed due to undecidability results. The theory of the , also known as the or the theory of the countable universal homogeneous graph, is axiomatized by the extension axioms ensuring that for any finite of , there exists a adjacent to all in one set and none in the other. This theory is complete and \aleph_0-categorical, meaning it has a unique countable model up to , which is the itself. The 's homogeneity property embeds every countable graph as an , demonstrating its universality in .

Notable Incomplete Theories

Peano arithmetic (PA), a first-order axiomatization of the natural numbers with induction, is incomplete because it contains undecidable sentences, as demonstrated by Gödel's first incompleteness theorem, which constructs a sentence true in the standard model but unprovable within the system. Specifically, PA cannot prove its own consistency, highlighting its failure to decide all arithmetic truths. Zermelo–Fraenkel set theory with the axiom of choice (ZFC), the standard foundation for mathematics, is also incomplete, as it interprets sufficient arithmetic to invoke Gödel's incompleteness theorems, rendering some set-theoretic statements undecidable. A prominent example is the continuum hypothesis (CH), which asserts no cardinal exists between the cardinality of the reals and the integers; Gödel showed CH is consistent with ZFC in 1940, while Cohen proved the negation is also consistent in 1963, establishing CH's independence. Robinson arithmetic (Q), a weaker finitely axiomatized fragment of PA without full induction, remains incomplete despite its simplicity, as it is strong enough to encode Gödel numbering and thus susceptible to the first incompleteness theorem, yielding undecidable sentences within the system. This illustrates that even minimal arithmetic theories fail completeness when capable of representing recursive functions. The first-order theory of groups, axiomatized by identity, inverses, and associativity, is incomplete because its elementary theory is undecidable, as finitely presented groups can encode arithmetic computations leading to unprovable statements, such as those related to the word problem. For instance, it cannot decide whether all groups are abelian, as this property holds in some models but not others.

Implications and Extensions

Decidability and Computability

A theory T in a language is decidable if there exists a that, given any \phi in the language, halts and outputs "yes" if T \vdash \phi and "no" otherwise. This means the set of theorems of T is recursive, allowing algorithmic determination of provability for any . Certain complete theories are decidable. For instance, , which formalizes the natural numbers with addition and order but excludes multiplication, is complete and admits a decision procedure via . Similarly, the theory \mathrm{ACF}_0 of algebraically closed fields of characteristic zero is complete and decidable, as it admits in the language of rings, enabling an algorithm to resolve the truth of any sentence. However, not all complete theories are decidable. True arithmetic, denoted \mathrm{Th}(\mathbb{N}, +, \times), consists of all true first-order sentences about the standard natural numbers under addition and multiplication; it is complete but undecidable, as its theorems form a non-recursive set. This undecidability arises because true arithmetic captures all arithmetical truths, including those unprovable in weaker systems like Peano arithmetic. Gödel's first incompleteness theorem demonstrates that no consistent, recursively axiomatizable sufficiently strong to interpret (such as containing ) can be complete. Since any recursively axiomatizable complete in a countable is decidable—by enumerating proofs until either \phi or \neg \phi appears as a —this implies no such can be both complete and recursively axiomatizable if it extends . True evades this limitation by being complete yet not recursively axiomatizable, as its non-recursive set of axioms prevents algorithmic enumeration.

Model-Theoretic Consequences

A fundamental model-theoretic consequence of is that all models of a complete theory are elementarily equivalent, meaning they satisfy precisely the same sentences. This follows directly from the definition, as the complete theory determines the of every in the . Complete theories exhibit varying degrees of categoricity, which measures the uniqueness of their models up to in a given . For instance, the theory of dense linear orders without endpoints (DLO) is \aleph_0-categorical, possessing a unique countable model up to , whereas the theory of algebraically closed fields (ACF) of characteristic zero is complete but not \aleph_0-categorical, admitting many non-isomorphic countable models due to differing transcendence degrees over the prime field. Atomic complete theories admit a unique prime model (up to isomorphism), which can be elementarily embedded into every other model of the theory; for example, the theory of dense linear orders has the rational numbers as its prime model. Additionally, every complete theory admits saturated models of cardinality \kappa for all sufficiently large cardinals \kappa (specifically, for \kappa \geq 2^{|T|} satisfying certain regularity conditions), which realize all possible types over parameter sets of size less than \kappa. Vaught's theorem establishes that no countable complete theory has exactly two non-isomorphic countable models (the "never-two" result), and more generally, the number cannot be finite and greater than 1. Vaught's conjecture, which remains open, asserts that the number is either at most 1 or exactly $2^{\aleph_0}. This dichotomy highlights the structural rigidity or abundance possible in models of complete theories. The back-and-forth argument is a key technique for establishing uniqueness in countable models, as seen in , where it constructs an isomorphism between any two countable dense linear orders without endpoints by alternately extending partial isomorphisms to include elements from each structure. A complete is exactly the set of all sentences true in some (equivalently, any) model of the theory. Stability notions further classify complete theories based on the behavior of types and definable sets.