9
$\begingroup$

It is known that adjunctive set theory interprets Robinson arithmetic, and that extensionality is not needed for that. (Montagna and Mancini, "A minimal predicative set theory", Notre Dame Journal of Formal Logic, 1994).

I wonder whether it is known if the following weak set theory (without extensionality) also interprets Robinson arithmetic. Axioms:

  1. $\exists y\forall x(x\notin y)$

  2. For every n, $\forall x_1\ldots\forall x_n\exists y\forall z(z\in y\leftrightarrow z=x_1 \vee \ldots\vee z=x_n)$

$\endgroup$
0

1 Answer 1

9
$\begingroup$

This theory was introduced by Vaught, and it does not interpret Robinson’s arithmetic. See Visser [1] for a thorough discussion of related theories; Vaught’s theory is denoted VS in the paper. (Note that the axioms are stated more concisely there: axiom 1 is a special case of axiom 2 for $n=0$.)

That VS does not interpret Robinson’s arithmetic Q follows by the following argument:

  • Q is finitely axiomatized. Thus, if it were interpretable in VS, it would be interpretable in its finite fragment.

  • VS is locally interpretable in the theory of nonsurjective pairing (using the obvious construction of $n$-tuples from pairs).

  • However, said theory of pairing is known to have decidable extensions, hence it does not interpret Q (or indeed, all of VS, which is also an essentially undecidable theory). Cf. Theorem 2 in [1,§3.2].

Reference:

[1] Albert Visser, Pairs, sets and sequences in first-order theories, Archive for Mathematical Logic 47 (2008), no. 4, pp. 299–326.

$\endgroup$
5
  • $\begingroup$ By bizarre coincidence, I was just looking at this very paper following an internet search for literature on a different matter (Craig's Trick, in fact). $\endgroup$ Apr 15, 2016 at 21:49
  • $\begingroup$ Does that mean this paper is incorrect in stating that what they call AS (page 8) interprets Q? Perhaps the author meant to use $\in$ rather than $=$ in the first disjunct. $\endgroup$
    – user76284
    Oct 28, 2021 at 22:49
  • $\begingroup$ There's a related open question here. $\endgroup$
    – user76284
    Oct 28, 2021 at 23:13
  • $\begingroup$ @user76284 AS is well known to be mutually interpretable with Q. What makes you think this is incorrect? $\endgroup$ Oct 29, 2021 at 6:36
  • $\begingroup$ @user76284 Oh, I see. Yes, there is a typo in the second axiom of AS in that paper. $\endgroup$ Oct 29, 2021 at 6:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.