In model theory, a branch of mathematical logic, the Łoś–Vaught test is a criterion for a theory to be complete, unable to be augmented without becoming inconsistent. For theories in classical logic, this means that for every sentence, the theory contains either the sentence or its negation but not both.
Statement A theory T {\displaystyle T} with signature σ is κ {\displaystyle \kappa } -categorical for an infinite cardinal κ {\displaystyle \kappa } if T {\displaystyle T} has exactly one model (up to isomorphism) of cardinality κ . {\displaystyle \kappa .}
The Łoś–Vaught test states that if a first-order satisfiable theory is κ {\displaystyle \kappa } -categorical for some κ ≥ | σ | {\displaystyle \kappa \geq |\sigma |} and has no finite model, then it is complete. This theorem was proved independently by Jerzy Łoś (1954) and Robert L. Vaught (1954), after whom it is named.
Applications The Łoś–Vaught test is used to prove that the theory of closed first-order logic formulas true on the Rado graph is complete.
See also Robinson's joint consistency theorem – Theorem of mathematical logic
Notes
References Enderton, Herbert B. (1972), A mathematical introduction to logic, Academic Press, New York-London, p. 147, ISBN 978-0-08-057038-9, MR 0337470. Łoś, Jerzy (1954), "On the categoricity in power of elementary deductive systems and some related problems", Colloquium Mathematicum, 3: 58–62, doi:10.4064/cm-3-1-58-62, MR 0061561. Marker, David (2002), Model theory, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, ISBN 0-387-98760-6, MR 1924282 Vaught, Robert L. (1954), "Applications to the Löwenheim-Skolem-Tarski theorem to problems of completeness and decidability", Indagationes Mathematicae, 16: 467–472, doi:10.1016/S1385-7258(54)50058-2, MR 0063993.