Vaught's theorem on axiomatizability by a scheme
type: Item
instance of: scholarly article
zbMATH Open document ID: 1272.03063
author: Albert Visser
published in: The Bulletin of Symbolic Logic
publication date: 2012-09-19T00:00:00Z
full work available at URL: https://projecteuclid.org/euclid.bsl/1344861888
full work available at URL: https://dspace.library.uu.nl/handle/1874/188137
Mathematics Subject Classification ID: 03B10
Mathematics Subject Classification ID: 03B30
Mathematics Subject Classification ID: 03F25
zbMATH DE Number: 6083933
zbMATH Keywords: predicate logic
zbMATH Keywords: Vaught's theorem
zbMATH Keywords: axiomatizability by a scheme
zbMATH Keywords: Vaught theory
zbMATH Keywords: unordered pairing
zbMATH Keywords: pair theory
MaRDI profile type: Publication
OpenAlex ID: W2122736112
cites work: THE NONARITHMETICITY OF THE CLASS OF REALIZABLE PREDICATE FORMULAS
cites work: A lattice of chapters of mathematics (interpretations between theorems [theories])
cites work: On the scheme of induction for bounded arithmetic formulas
cites work: Can We Make the Second Incompleteness Theorem Coordinate Free?
cites work: Q4001935
cites work: The computational complexity of logical theories
cites work: Finite Axiomatizability using additional predicates
cites work: On axiomatizability within a system
cites work: Schemata: The Concept of Schema in the History of Logic
cites work: Decidability of the theory of the natural integers with the Cantor pairing function and the successor
cites work: The predicative Frege hierarchy
cites work: Pairs, sets and sequences in first-order theories
DOI: 10.2178/BSL/1344861888
title: Vaught's theorem on axiomatizability by a scheme
review text: Vaught's set theory \(\mathsf{VS}\) is the theory (in the language with \(=\) and \(\in\)) with the axioms NEWLINE\[NEWLINE\forall x_0,\dots,x_{n - 1} \, \exists y \, \forall u \, (u \in y \leftrightarrow \bigvee_{i < n} u = x_i)\text{ for }n= 0,1,2,\dots.NEWLINE\]NEWLINE A Vaught theory is a theory that directly interprets (that is, the interpretation is not relativized and translates identity to identity) \(\mathsf{VS}\). Vaught's theorem says: all recursively enumerable Vaught theories are axiomatizable by a scheme.NEWLINENEWLINEThe theory of unordered pairing \(\mathsf{VS}_2\) is the theory (in the language with \(=\) and \(\in\)) with (essentially) the axiom \(\forall x_0,x_1 \, \exists y \, \forall u \, (u \in y \leftrightarrow u = x_0 \vee u = x_1)\). A pair theory is a theory that directly interprets \(\mathsf{VS}_2\). The main theorem of the paper under review says: all recursively enumerable pair theories are axiomatizable by a scheme.NEWLINENEWLINEVisser's theorem strictly improves Vaught's theorem (because there are consistent decidable pair theories but all consistent Vaught theories are essentially undecidable).
reviewed by: Jaime Gaspar
description: scientific article; zbMATH DE number 6083933