Skip to main content
MathOverflow

Return to Answer

expand
Source Link
Emil Jeřábek
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

With respect to question 3: one way to do this is to restrict the quantifier complexity of the formulas. That is, for every constant $k$, one can define a formula $\delta_k(x)$ expressing “$x$ is definable by a $\Sigma_k$-formula with parameters”. Here, a formula $\phi(\vec x)$ is $\Sigma_k$ (in the Lévy hierarchy) if it can be written in the form $\exists y_1\,\forall y_2\,\exists y_3\,\dots Qy_k\,\theta(\vec x,\vec y)$, where all quantifiers in $\theta$ are bounded.

$\def\Tr{\mathrm{Tr}}$EDIT: Let me clarify how exactly $\Sigma_k$-formulas can be used to answer question 3. What I wrote above is true, but useless by itself, because definability of sets by formulas allowing arbitrary parameters is not an interesting notion (every set is trivially definable from itself as a parameter). But the Lévy hierarchy provides more than that:

  • For every $k>0$, there is a truth definition for $\Sigma_k$-formulas, which is itself $\Sigma_k$. That is, there is a $\Sigma_k$-formula $\Tr_k(n,x)$ such that ZF proves $$\phi(x)\leftrightarrow\Tr_k(\ulcorner\phi\urcorner,x)$$ for every $\Sigma_k$-formula $\phi(x)$, where $\ulcorner\phi\urcorner$ is the Gödel number of $\phi$. This is essentially optimal: if a class of formulas has a truth definition, it is up to equivalence included in some $\Sigma_k$ (because the truth definition itself is in $\Sigma_k$ for some $k$).

  • If $k>0$, and $X$ is a class of possible parameters which includes $\omega$ and is closed under pairing (that is, $X\times X\subseteq X$), there is a formula $\delta(x)$ which expresses “$x$ is $\Sigma_k$-definable using parameters from $X$”, namely $$\delta(x)=\exists n\in\omega\,\exists z\in X\,\forall y\,(y\in x\eq\Tr_k(n,\langle y,z\rangle)).$$ (Here, the pairing operation on $X$ does not have to be the standard Kuratowski pair. For example, one can define an injection $\mathrm{Ord}\times\mathrm{Ord}\to\mathrm{Ord}$, which allows us to take $X=\mathrm{Ord}$, so this generalizes ordinal definability. Also, I believe the assumption $\omega\subseteq X$ is redundant as long as $|X|\ge2$, because one can reconstruct a suitable copy of $\omega$ inside $X$ using the pairing operation.)

With respect to question 3: one way to do this is to restrict the quantifier complexity of the formulas. That is, for every constant $k$, one can define a formula $\delta_k(x)$ expressing “$x$ is definable by a $\Sigma_k$-formula with parameters”. Here, a formula $\phi(\vec x)$ is $\Sigma_k$ (in the Lévy hierarchy) if it can be written in the form $\exists y_1\,\forall y_2\,\exists y_3\,\dots Qy_k\,\theta(\vec x,\vec y)$, where all quantifiers in $\theta$ are bounded.

With respect to question 3: one way to do this is to restrict the quantifier complexity of the formulas. That is, for every constant $k$, one can define a formula $\delta_k(x)$ expressing “$x$ is definable by a $\Sigma_k$-formula with parameters”. Here, a formula $\phi(\vec x)$ is $\Sigma_k$ (in the Lévy hierarchy) if it can be written in the form $\exists y_1\,\forall y_2\,\exists y_3\,\dots Qy_k\,\theta(\vec x,\vec y)$, where all quantifiers in $\theta$ are bounded.

$\def\Tr{\mathrm{Tr}}$EDIT: Let me clarify how exactly $\Sigma_k$-formulas can be used to answer question 3. What I wrote above is true, but useless by itself, because definability of sets by formulas allowing arbitrary parameters is not an interesting notion (every set is trivially definable from itself as a parameter). But the Lévy hierarchy provides more than that:

  • For every $k>0$, there is a truth definition for $\Sigma_k$-formulas, which is itself $\Sigma_k$. That is, there is a $\Sigma_k$-formula $\Tr_k(n,x)$ such that ZF proves $$\phi(x)\leftrightarrow\Tr_k(\ulcorner\phi\urcorner,x)$$ for every $\Sigma_k$-formula $\phi(x)$, where $\ulcorner\phi\urcorner$ is the Gödel number of $\phi$. This is essentially optimal: if a class of formulas has a truth definition, it is up to equivalence included in some $\Sigma_k$ (because the truth definition itself is in $\Sigma_k$ for some $k$).

  • If $k>0$, and $X$ is a class of possible parameters which includes $\omega$ and is closed under pairing (that is, $X\times X\subseteq X$), there is a formula $\delta(x)$ which expresses “$x$ is $\Sigma_k$-definable using parameters from $X$”, namely $$\delta(x)=\exists n\in\omega\,\exists z\in X\,\forall y\,(y\in x\eq\Tr_k(n,\langle y,z\rangle)).$$ (Here, the pairing operation on $X$ does not have to be the standard Kuratowski pair. For example, one can define an injection $\mathrm{Ord}\times\mathrm{Ord}\to\mathrm{Ord}$, which allows us to take $X=\mathrm{Ord}$, so this generalizes ordinal definability. Also, I believe the assumption $\omega\subseteq X$ is redundant as long as $|X|\ge2$, because one can reconstruct a suitable copy of $\omega$ inside $X$ using the pairing operation.)

"to to" -> "to do"
Source Link
Hans-Peter Stricker
Hans-Peter Stricker
  • 9.7k
  • 5
  • 53
  • 113

With respect to question 3: one way to to do this is to restrict the quantifier complexity of the formulas. That is, for every constant $k$, one can define a formula $\delta_k(x)$ expressing “$x$ is definable by a $\Sigma_k$-formula with parameters”. Here, a formula $\phi(\vec x)$ is $\Sigma_k$ (in the Lévy hierarchy) if it can be written in the form $\exists y_1\,\forall y_2\,\exists y_3\,\dots Qy_k\,\theta(\vec x,\vec y)$, where all quantifiers in $\theta$ are bounded.

With respect to question 3: one way to to this is to restrict the quantifier complexity of the formulas. That is, for every constant $k$, one can define a formula $\delta_k(x)$ expressing “$x$ is definable by a $\Sigma_k$-formula with parameters”. Here, a formula $\phi(\vec x)$ is $\Sigma_k$ (in the Lévy hierarchy) if it can be written in the form $\exists y_1\,\forall y_2\,\exists y_3\,\dots Qy_k\,\theta(\vec x,\vec y)$, where all quantifiers in $\theta$ are bounded.

With respect to question 3: one way to do this is to restrict the quantifier complexity of the formulas. That is, for every constant $k$, one can define a formula $\delta_k(x)$ expressing “$x$ is definable by a $\Sigma_k$-formula with parameters”. Here, a formula $\phi(\vec x)$ is $\Sigma_k$ (in the Lévy hierarchy) if it can be written in the form $\exists y_1\,\forall y_2\,\exists y_3\,\dots Qy_k\,\theta(\vec x,\vec y)$, where all quantifiers in $\theta$ are bounded.

Source Link
Emil Jeřábek
Emil Jeřábek
  • 47.1k
  • 4
  • 147
  • 208

With respect to question 3: one way to to this is to restrict the quantifier complexity of the formulas. That is, for every constant $k$, one can define a formula $\delta_k(x)$ expressing “$x$ is definable by a $\Sigma_k$-formula with parameters”. Here, a formula $\phi(\vec x)$ is $\Sigma_k$ (in the Lévy hierarchy) if it can be written in the form $\exists y_1\,\forall y_2\,\exists y_3\,\dots Qy_k\,\theta(\vec x,\vec y)$, where all quantifiers in $\theta$ are bounded.