0
$\begingroup$

I'm trying to understand how the Levy hierarchy does not contradict the axiom schema of restricted separation.

In his paper on the set hierarchy Levy introduced satisfaction predicates which I think implies that for any fixed quantifier rank $k$, there is a predicate $\phi_k$ of the same rank with one additional free variable $x$ such that $\phi_k(x)$ is true precisely when the formula of rank $k$ with Godel number $x$ is also (assuming $x\in V_\omega$ is part of a Godel numbering scheme). Also, since such predicates deal with all formulas of a fixed rank they are not equivalent to formulas of a lesser rank.

Assuming I got that right, then I don't understand how we can have the separation axioms be consistent because we would have: $$\exists b\; \forall x\; x \in b \leftrightarrow \phi_k(x) \wedge x \in V_\omega$$ but the left side of the bi-conditional is just set membership, a formula of rank $0$, so how could it be equivalent to a formula of a much higher rank? Is the issue that I need to account for the set $b$ not being part of the language itself but rather the universe of a model? Thanks.

$\endgroup$
10
  • 2
    $\begingroup$ The natural number is in the meta theory. You can't quantify over all of them simultaneously. This is the same reason the Reflection theorem does not imply that ZF is inconsistent. $\endgroup$
    – Asaf Karagila ♦
    Commented May 31, 2023 at 13:29
  • 1
    $\begingroup$ Is there really anything essentially to do with the truth predicate here? It seems to me that you're just asking how we can have the axiom of separation $$ \exists b \forall x(x\in b \leftrightarrow \varphi(x) \land x\in a) $$ when it seems to say that an arbitrarily high complexity formula $\varphi(x)\land x\in a$ is equivalent to an atomic formula $x\in b.$ Am I missing something? $\endgroup$
    – spaceisdarkgreen
    Commented May 31, 2023 at 14:35
  • 2
    $\begingroup$ @AsafKaragila I don't see what that has to do with the question $\endgroup$
    – spaceisdarkgreen
    Commented May 31, 2023 at 14:44
  • $\begingroup$ @AsafKaragila But doesn't the von Neumann integers exist as a set due to the axiom of infinity and then we could do Godel numbering over them? Or am I totally wrong about the Levy satisfaction predicates- that they cannot "translate" von Neumann intergers when expressed as sets into their intended meaning? $\endgroup$
    – Ari
    Commented May 31, 2023 at 14:57
  • $\begingroup$ @spaceisdarkgreen Yeah I guess that is my question. I mean I cannot understand why the case by ZF is different from the Arithmetic Hierarchy. $\endgroup$
    – Ari
    Commented May 31, 2023 at 14:59

1 Answer 1

Reset to default
2
$\begingroup$

Is the issue that I need to account for the set $b$ not being part of the language itself but rather the universe of a model?

Yes, that's on the right track.

For example, it's not very elucidating to say every set is definable by an atomic formula just because we can instantiate some variable $b$ standing for some set and taking the formula $x=b.$ (Even though it's technically true, if by "definable" we mean "definable with parameters", so we need to be careful about what type of definability with mean...)

In the case of the Levy hierarchy, we say (for instance) that a formula $\varphi(x)$ is $\Sigma_n$ over some base theory $T$ if there is a (syntactically) $\Sigma_n$ formula $\psi(x)$ such that $T\vdash \forall x(\varphi(x)\leftrightarrow\psi(x)).$ Note there are no parameters here.

$\endgroup$
3
  • $\begingroup$ So does this mean that there exist subsets of $V_\omega$ (definable without parameters) that contain precisely the Godel numbers of true sentences in that model (up to a fixed rank)? I assume if no rank is fixed then it is impossible by Tarski's Theorem, right? $\endgroup$
    – Ari
    Commented May 31, 2023 at 17:42
  • 1
    $\begingroup$ @Ari It's a bit subtle because unlike the case of arithmetic we don't really have a canonical model we're in in the case of set theory. Though we can certainly talk about these concepts over models, let's stick to working over theories. In that case, what we can say is that for any $n\ge 1$, there is a formula $\operatorname{Sat}_n(x,y)$, $\Sigma_n$ over ZFC, such that for any $\Sigma_n$ formula $\varphi(x)$, $\mathsf{ZFC}\vdash \forall x(\varphi(x) \leftrightarrow \operatorname{Sat}_n(\ulcorner \varphi \urcorner, x)).$ Whereas no such formula exists where this holds for all formulas. $\endgroup$
    – spaceisdarkgreen
    Commented May 31, 2023 at 18:37
  • $\begingroup$ Thanks. Do we also have the existence of the following?: A $\Sigma_n$ formula $\operatorname{SetDef}_n$ such that for any $\Sigma_n$ formula $\varphi(x)$, $\mathsf{ZFC}\vdash \operatorname{SetDef}_n(\ulcorner \varphi \urcorner , y) \leftrightarrow \forall x(x\in y \leftrightarrow \varphi(x))$...I figure that $\forall x(x\in y \leftrightarrow \operatorname{Sat}_n(\ulcorner \varphi \urcorner, x))$ would be logically equivalent but I don't know how to make it $\Sigma_n$. $\endgroup$
    – Ari
    Commented Jun 6, 2023 at 0:45

You must log in to answer this question.

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