ω-complete theory

Short description: Property of an arithmetical theory

In mathematical logic, an ω-complete theory is a formal theory in first-order logic, containing arithmetics, such that whenever it proves every natural number instance of a formula, it also proves the corresponding universal sentence. A theory with the complementary property is called ω-incomplete. The ω in the name refers to the set of natural numbers.

The terminology was established in the 1958 paper The Classical and the ω-Complete Arithmetic by Andrzej Grzegorczyk, Andrzej Mostowski, and Czesław Ryll-Nardzewski.

Definition

Consider a first-order language that contains terms for the natural numbers $\overline{0},\overline{1},\overline{2},\dots$. For example, the standard language for Peano arithmetic contains the two symbols $0,S$, with which we can write down the terms for all the natural numbers: $0,S0,SS0,\dots$.

Let $T$ be a theory in the language. $T$ is ω-complete iff, for every formula $\phi (x)$ with one free variable,$$T⊢\phi (\overline{n})\text{ for every }n\in \omega ⟹T⊢\mathrm{\forall }x\phi (x).$$The implication may appear obvious. However, one must distinguish between $⊢$, which is a consequence within the object-theory, and $⟹$, which is a consequence in the meta-theory. A theory is ω-complete if it can perform this consequence within the object-theory, rather than perform it outside in the meta-theory.

Examples

It is possible for a theory to be ω-incomplete, because the theory may have a model ${ℳ}$ with non-standard integers. In the model, we can have ${ℳ}\models \phi (\overline{0}),{ℳ}\models \phi (\overline{1}),\dots$, but nevertheless have ${ℳ}\models ̸\phi (c)$ for a certain non-standard integer $c$ in the model.

A standard weak example is Robinson arithmetic $Q$. It proves each instance of $0+\overline{n}=\overline{n}$, while the universal sentence $\mathrm{\forall }x(0+x=x)$ lies beyond its theorems. This can be computably demonstrated by building a computable nonstandard model of $Q$, in which $0+c\ne 0$ for a non-standard integer element $c$. Accordingly, $Q$ is ω-incomplete.

Peano arithmetic repairs many weak failures of that kind, yet standard incompleteness arguments still yield ω-incompleteness under the usual consistency assumption. In particular, Gödel's second incompleteness theorem provide an example. Consider a Gödel numbering of all proofs in PA, and let $\phi (\overline{n})$ to mean "If number $n$ is a valid proof in PA, then its conclusion is not $0=1$". Then, $PA⊢\phi (\overline{0}),PA⊢\phi (\overline{1}),\dots$, but $PA⊬\mathrm{\forall }x\phi (x)$ by incompleteness. This argument applies to any recursively axiomatized theory that contains PA.

Relation to nearby notions

ω-completeness is closely related to ω-consistency. A theory is ω-consistent when no formula $\psi (x)$ yields both the existential sentence $\mathrm{\exists }x\psi (x)$ and every numeral instance $\mathrm{\neg }\psi (\overline{n})$. The two notions mark different syntactic patterns in the study of formal theories.

By the completeness theorem, a consistent theory is ω-incomplete if and only if it can be extended to a consistent but ω-inconsistent theory.

ω-completeness is also connected with the ω-rule,$$A(0),A(1),A(2),\dots \Rightarrow \mathrm{\forall }nA(n).$$Proof systems using the ω-rule build the passage from all numeral instances to the universal conclusion directly into the proof system.

See also

• Gödel's incompleteness theorems
• Peano arithmetic
• ω-consistency
• ω-rule

Further reading

• "Gödel’s Incompleteness Theorems". Stanford Encyclopedia of Philosophy. 2025-10-08. https://plato.stanford.edu/entries/goedel-incompleteness/. Retrieved 2026-04-17. 
• Hájek, Petr; Pudlák, Pavel (1993). Metamathematics of First-Order Arithmetic. Berlin: Springer.