6
$\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$
  • $\begingroup$ $z\in z \:$ should presumably be replaced with $\: z\in x \;$. $\;\;\;\;$ $\endgroup$ – user57159 Nov 10 '15 at 19:34
  • $\begingroup$ @RickyDemer Of course. Thank you. $\endgroup$ – Wojowu Nov 10 '15 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$ – Henning Makholm Nov 10 '15 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$ – Henning Makholm Nov 10 '15 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$ – Henning Makholm Nov 10 '15 at 20:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.