20
$\begingroup$

The collection of

binary relations $R$ on the natural numbers such that $(\mathbb{N},R) \models ZFC$

forms a Borel set, neither closed nor open -- assuming Con(ZFC).

  • Can you show it's not $F_\sigma$ or $G_\delta$?

  • Is it actually complete for level $\omega$ of the Borel hierarchy?

$\endgroup$
6
  • 2
    $\begingroup$ Usually, "complete for X" means (1) in X and (2) at least as complicated as anything else in X. Presumably, by "in some sense complete for finite levels of the Borel hierarchy", you meant only (2). $\endgroup$ Apr 8, 2017 at 14:23
  • 1
    $\begingroup$ "Complete for level $\omega$" looks plausible. $\endgroup$ Apr 8, 2017 at 16:46
  • $\begingroup$ I think that Sam Coskey was looking at the isomorphism relation on these models under Borel reducibility, aiming to place it in the hierarchy of Borel reducibility. $\endgroup$ Apr 11, 2017 at 19:18
  • 4
    $\begingroup$ By reading the axioms (i.e. every axiom is satisfied, as a formalized statement) it's a $\Pi^0_{\omega+1}$ set (since satisfying a first-order sentence is $\Pi^0_n$ for some $n$). I think that it's not $\Pi^0_n$ for $n<\omega$ amounts to the fact that ZFC is not finitely axiomatizable. $\endgroup$ Apr 11, 2017 at 20:52
  • 6
    $\begingroup$ My student Samuel Dworetzky showed that the isomorphism relation for countable models of ZFC is Borel complete (in the sense of Borel complexity theory). I don't think it affects this particular question, though. $\endgroup$ Apr 14, 2017 at 20:09

1 Answer 1

1
$\begingroup$

@FrançoisG.Dorais commented:

By reading the axioms (i.e. every axiom is satisfied, as a formalized statement) it's a $\Pi^0_{\omega+1}$ set (since satisfying a first-order sentence is $\Pi^0_n$ for some $n$). I think that it's not $\Pi^0_n$ for $n<\omega$ amounts to the fact that ZFC is not finitely axiomatizable.

$\endgroup$
1
  • 1
    $\begingroup$ Can someone turn this from a vague impression into a proof? This is an interesting question, and I don't think this comment answers it. $\endgroup$ Aug 18, 2017 at 7:33

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.