3
$\begingroup$

Motivated by this question, I'd like to ask:

What is the complexity of the first-order theory of the two-element pure set $\bf 2$?

(Note that the answer will be the same if we replace ${\bf 2}$ by any finite pure set with more than one element.)

The argument of my answer to the linked question shows that both $\mathsf{SAT}$ reduces to the $\Sigma_1$ fragment of this problem: there is an efficient way to transform a propositional sentence $\varphi$ into a first-order sentence $\hat{\varphi}$ such that ${\bf 2}\models\hat{\varphi}$ iff $\varphi$ is satisfiable. Dually of course this means that $\mathsf{coSAT}$ reduces to the $\Pi_1$ fragment.

Considering the behavior of adding quantifiers, a natural guess at an answer is that it should be exactly the union of the levels in the polynomial hierarchy, but I don't immediately see the details.

$\endgroup$
7
  • 7
    $\begingroup$ Well. $1$ is the loneliest number that you'll ever do. $2$ can be as bad as one, it's the loneliest number since the number $1$. $\endgroup$
    – Asaf Karagila
    Commented Aug 20, 2020 at 17:38
  • $\begingroup$ @Asaf Karagila: Contrast this with $0,$ which by virtue of belonging to every other number, is the most social of all numbers. $\endgroup$ Commented Aug 20, 2020 at 18:32
  • 1
    $\begingroup$ @Dave: That's something you're going to have to take with Harry Nilsson... $\endgroup$
    – Asaf Karagila
    Commented Aug 20, 2020 at 18:33
  • 1
    $\begingroup$ @DougSpoonwood The identities of the particular elements of a structure don't matter, and in this case the structure on our set consists of just equality (that's what "pure set" means in model theory). And in this question they really don't matter, since we're ultimately forgetting the structure and just looking at the theory - the set of sentences true in the structure. Digging into the particular details of what the elements "actually are" isn't something the structure can do. $\endgroup$ Commented Aug 20, 2020 at 19:19
  • 1
    $\begingroup$ @DougSpoonwood Not within the structure itself - those questions have to be asked/answered outside the structure, from the perspective of the set-theoretic universe. And you know that they have to be, since they're not isomorphism-invariant. You should look up the definition of the satisfaction relation in the context of first-order logic. $\endgroup$ Commented Aug 20, 2020 at 20:21

1 Answer 1

4
$\begingroup$

Given that Quantified Boolean Formulas is PSPACE-complete and can be reduced to the pure first-order theory of $2$, it's PSPACE-hard. On the other hand, it's also clearly in PSPACE (since the obvious recursive algorithm is polynomial in space usage). So it's PSPACE-complete.

$\endgroup$
1
  • 1
    $\begingroup$ I didn't know about QBF, thanks for bringing it to my attention! $\endgroup$ Commented Aug 20, 2020 at 19:22

You must log in to answer this question.

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