19
$\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?

Improve this question
$\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$
    – Andreas Blass
    Commented Apr 8, 2017 at 14:23
  • 1
    $\begingroup$ "Complete for level $\omega$" looks plausible. $\endgroup$
    – Andreas Blass
    Commented 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$
    – Joel David Hamkins
    Commented 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$
    – François G. Dorais
    Commented 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$
    – Samuel Coskey
    Commented Apr 14, 2017 at 20:09

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Emil Jeřábek
    Commented Aug 18, 2017 at 7:33

You must log in to answer this question.

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