9
$\begingroup$

Today I was reading this paper, which includes discussion of essential undecidability of various weak theories. On page 24, I was surprised to find out that Vaught has showed that set theory with the following two axioms is essentially undecidable:

$$\forall x\exists y\neg(y\in x)$$ $$\forall x,y\exists u\forall z(z\in u\Leftrightarrow(z\in x\lor z\in y))$$

I was surprised as I have found in some recent paper (which I can't remember) that ST is the simplest known set theory which is essentially undecidable, while (arguably) Vaught's theory is simpler. I wasn't able to track down Vaught's work which would talk of this theory.

On the second thought, this theory seems unlikely to be essentially undecidable, because, first, it vacuously has an empty model, and second, less trivially, a finite model with $\in$ being empty relation seems to satisfy the theory as well, thus giving a decidable extension of the theory.

Can anyone provide a reference for where Vaught proves essential undecidability of this theory?

Thanks in advance.

Edit: Since the result seems to be false, the question arises whether the article I mention on the beginning has a typo. Finding a work of Vaught which the paper appears to be quoting might help clarify that, but again - I couldn't find anything.

$\endgroup$
8
  • $\begingroup$ $z\in z \:$ should presumably be replaced with $\: z\in x \;$. $\;\;\;\;$ $\endgroup$
    – user57159
    Nov 10, 2015 at 19:34
  • $\begingroup$ @RickyDemer Of course. Thank you. $\endgroup$
    – Wojowu
    Nov 10, 2015 at 19:39
  • 1
    $\begingroup$ Empty models are not allowed in usual first-order logic, but any (finite or infinite) model with an empty $\in$ relation would be enough to prove that extending the theory with $\forall x,y(x\notin y)$ produces a consistent theory, which will be trivially decidable. $\endgroup$
    – hmakholm left over Monica
    Nov 10, 2015 at 19:49
  • $\begingroup$ Just before the claim in question is a reference "(see [33]--[36])", and reference [33] is indeed a paper by Vaught. It would seem most meaningful if that is supposed to be the one that contains the result. $\endgroup$
    – hmakholm left over Monica
    Nov 10, 2015 at 20:03
  • $\begingroup$ Reference [33] links to a review that sounds like it's mostly about arithmetic, but ends with: "Der Verfasser gibt zum Schluß $R_0$ entsprechende Theorien in der Mengenlehre an und weist auf weitere Probleme hin." which sounds vaguely like it could be it. $\endgroup$
    – hmakholm left over Monica
    Nov 10, 2015 at 20:12

1 Answer 1

Reset to default
4
$\begingroup$

These are just typos. (The axioms as given do not form an essentially undecidable theory, as they have lots of finite models.)

The story on top of p. 24 is clearly meant to refer to the adjunctive set theory (AS) with axioms $$\exists x\:\forall y\:\neg(y\in x),$$

$$\forall x,y\:\exists u\:\forall z\:\bigl(z\in u\leftrightarrow(z\in x\lor z=y)\bigr).$$ Indeed, this theory extended with the axiom of extensionality was introduced and proved essentially undecidable by Szmielew and Tarski, and essential undecidability of the version here without extensionality was shown in Vaught’s paper On a theorem of Cobham concerning undecidable theories (Proc. Logic, Methodology and Philosophy of Science 1960, pp. 14–25). The theory AS is mutually interpretable with Robinson’s arithmetic Q.

An even weaker essentially undecidable theory, nowadays often called Vaught’s set theory (VS), was introduced in Vaught’s paper Axiomatizability by a schema (JSL 32 (1967), pp. 473–479). Its axioms consist of the schema $$\forall x_0,\dots,x_{n-1}\:\exists u\:\forall z\:\Bigl(z\in u\leftrightarrow\bigvee_{i<n}z=x_i\Bigr)$$ for all $n\ge0$. The theory VS interprets Robinson’s theory R; like R, and unlike AS or Q, it is not finitely axiomatizable. There is a mention of VS on p. 26 of Beklemishev’s paper (again, with a typo: the axioms need to be stated for $n\ge0$, not just $n\ge1$, i.e., including the axiom of the empty set).

$\endgroup$
7
  • $\begingroup$ Thanks a lot! I should have realized the theory from the cited papers has finite models, especially after I made the comment above about it being the case for empty set + the messed up adjunction axiom. Thank you for the references as well! $\endgroup$
    – Wojowu
    Oct 29, 2021 at 19:43
  • $\begingroup$ Is VS the weakest known essentially undecidable theory? $\endgroup$
    – user76284
    Oct 29, 2021 at 19:45
  • 1
    $\begingroup$ @user76284 Certainly not. E.g., Robinson’s R is strictly weaker (wrt computable interpretations) than VS. Theories like REP_U or REP_{PRF} from my paper “Recursive functions and existentially closed structures” are strictly weaker than R. For even weaker essentially undecidable theories, fix any recursively inseparable pair of r.e. sets $A,B\subseteq\omega$, and take the theory with constants $\{c_n:n\in\omega\}$, a unary predicate $P$, and axioms $P(c_n)$ for $n\in A$ and $\neg P(c_n)$ for $n\in B$. $\endgroup$
    – Emil Jeřábek
    Oct 29, 2021 at 20:06
  • $\begingroup$ @EmilJeřábek Sorry, I mean over a language with only a binary relation (like $\in$). $\endgroup$
    – user76284
    Oct 29, 2021 at 20:15
  • 1
    $\begingroup$ Same answer. You can encode any r.e. theory by a theory whose language only has a binary relation. $\endgroup$
    – Emil Jeřábek
    Oct 29, 2021 at 20:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .