9
$\begingroup$

Does the following principle follow from uniform elimination of imaginaries?

For every formula $\varphi(x;y)$ there is a formula $\vartheta(x;z)$ such that

$$\forall y\;\exists^{=1}z\;\forall x\;\Big[\varphi(x;y)\leftrightarrow\vartheta(x;z)\Big]$$

The answer is affirmative if we restrict the question to formulas such that $\forall y\;\exists x\;\varphi(x;y)$. Is this limitation necessary?

Edit (to answer a request in the comments). Uniform elimination of imaginaries says that every definable equivalence relation is the kernel of a function (that is, $aEb\leftrightarrow fa=fb$).

Elimination of imaginaries says that for every $\varphi(x;y)$ and every parameter $a$ there is a formula $\vartheta_a(x;z)$ such that

$$\exists^{=1}z\;\forall x\;\Big[\varphi(x;a)\leftrightarrow\vartheta_a(x;z)\Big]$$

Elimination of imaginaries is equivalent to uniform elimination under very weak hypotheses (there are two definable elements).

Improve this question
$\endgroup$
6
  • $\begingroup$ Can you remind us what "uniform elimination of imaginaries" means? $\endgroup$
    – Joel David Hamkins
    Mar 5, 2016 at 9:19
  • $\begingroup$ I don't think "every definable equivalence relation has a definable choice function" is a clear way of defining uniform elimination of imaginaries (UEI). UEI means that for every $0$-definable equivalence relation $E$ there is a $0$-definable function $f$ such that $aEb$ if and only if $f(a) = f(b)$. "$E$ has a definable choice function" makes it sound like you additionally want to have $a E f(a)$, which is stronger - for UEI, the codomain of $f$ could be a different sort entirely. $\endgroup$
    – Alex Kruckman
    Mar 6, 2016 at 19:20
  • $\begingroup$ I deleted my answer because it does exactly! not answer the question. I guess one can construct an counterexample in $ACF_0$ (if you allow your quantifiers to be tuples). $\endgroup$
    – TimZ
    Mar 7, 2016 at 11:32
  • $\begingroup$ @AlexKruckman You are right, thank you, I corrected. $\endgroup$
    – Domenico Zambella
    Mar 7, 2016 at 14:00
  • $\begingroup$ @TimZ A counterexample would be a perfect answer. (Indeed, variables are tuples.) $\endgroup$
    – Domenico Zambella
    Mar 7, 2016 at 14:02

1 Answer 1

Reset to default
2
$\begingroup$

Yes, the statement follows from uniform elimination of imaginaries, with a slight warning: you need to allow the range of the variable $z$ to be a definable set (of tuples), rather than all tuples of a given length. More on that caveat later.

Let $\varphi(x,y)$ be a formula in tuples $x$ and $y$. Define an equivalence $$y_1 E y_2 := \forall x : (\varphi(x,y_1) \leftrightarrow \varphi(x,y_2)).$$ That is, $a E b$ iff $\varphi(x,a)$ and $\varphi(x,b)$ define the same set. By uniform elimination of imaginaries, we have a definable $f$ such that $E$ is the kernel of $f$. Moreover, we can take $f$ to be surjective by considering its codomain to be its range, which is definable.

Now, set $$\vartheta(x,z) := \exists y : f(y) = z \wedge \varphi(x,y).$$ Fix $y$. We need to show existence and uniqueness of $z$ such that $\varphi(x,y)$ and $\vartheta(x,z)$ define the same set in $x$. Existence is easy: $z := f(y)$ works. For uniqueness, assume we have $z_1,z_2$ such that $\vartheta(x,z_1)$ and $\vartheta(x,z_2)$ both define the same set (in particular, that they both define $\varphi(x,y)$). By the surjectivity of $f$, take $y_1,y_2$ such that $f(y_1) = z_1, f(y_2) = z_2$. We now need only show that $y_1 E y_2$, which we already know from the definitions of $E$ and $\vartheta$.

About the caveat. The caveat appears necessary (though I don't have a counterexample) in order to consider $f$ surjective. I don't consider the caveat a problem, though, since there's no real reason to consider definable sets of tuples as "second class citizens." And even if you do, just make the definable set explicit by modifing the statement to say there is $\vartheta(x,z)$ and a definable set $Z$ such that $$(\forall y) (\exists^{=1} z \in Z) (\forall x) \varphi(x,y) \leftrightarrow \vartheta(x,z).$$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you Mike for your answer. There are many possible caveats that essentially dodge the question. (TimZ had a very similar answer.) I conjecture that the answer to the OP is "no", though I could not construct a counterexample yet. $\endgroup$
    – Domenico Zambella
    Apr 18, 2016 at 5:55
  • 2
    $\begingroup$ @DomenicoZambella I respectfully disagree that I've dodged the question. As I said, there is no good reason to treat definable subsets as second class citizens. In particular, given a definable set $Z$, you can modify $T$ by adding an additional sort for $Z$, a tuple of function symbols corresponding to a function from $Z$ to the appropriate tuple sort, and axioms saying that function is injective onto the original subset. This theory has equivalent $\operatorname{Def}(T)$ and doesn't eliminate any new imaginaries. If it makes a difference for your application, some context would be helpful. $\endgroup$
    – user71137
    Apr 18, 2016 at 14:44

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.