3
$\begingroup$

This is a followup to this question.

Consider $\mathbb{C}$ as a structure - in the sense of first-order logic - with the graphs of addition and multiplication. Let $\mathcal{X}$ be the substructure with underlying set $\{2^n: n\in\mathbb{N}\}$.

Question: is there a relation on $\mathcal{X}$ which is definable in $\mathbb{C}$ together with a predicate for $\mathcal{X}$, but which is not definable in $\mathcal{X}$ itself?

Here "definable" is with respect to first-order logic. The motivation for this question is the following: if we replace $\mathcal{X}$ with $\mathbb{Z}$ we get a negative answer, but this relies on the expressive power of $\mathbb{Z}$ - specifically, the fact that $\mathbb{Z}$ interprets an algebraically closed field of characteristic zero and infinite transcendence degree together with a predicate naming the integers. By contrast, considered on its own $\mathcal{X}$ "is" just a copy of $(\mathbb{N};+)$, and so the previous argument breaks down immediately.

Improve this question
$\endgroup$
8
  • $\begingroup$ I admit I'm a little confused about what signature we're talking about: $\mathbb{C}$ with only the relations of $+$ and $\times$ and equality? $\endgroup$
    – cody
    Commented yesterday
  • 1
    $\begingroup$ @cody Yes, that's correct. $\endgroup$
    – Noah Schweber
    Commented yesterday
  • 1
    $\begingroup$ Minor note which you may already know, van den Dries showed in this paper that the theory of $(\mathbb{R},+,\cdot,\{2^n : n \in \mathbb{N}\})$ is decidable. This interprets the structure you're talking about (and is probably biinterpretable with it), so $\mathbb{Z}$ is not definable in the structure in this question. $\endgroup$
    – James E Hanson
    Commented yesterday
  • $\begingroup$ @JamesEHanson Ooh, I didn't know that - that's neat (although I don't think it immediately helps here)! $\endgroup$
    – Noah Schweber
    Commented yesterday
  • $\begingroup$ The paper shows more than just "it's decidable" - it uses quantifier elimination, and I think a corollary of the QE result is that the definable subsets of $\mathcal{X}$ are exactly the subsets definable in $\mathcal{X}$. If I'm right, that gives an answer to this question as well, because anything definable in the structure in the question would also be definable in this structure that interprets it. $\endgroup$
    – paste bee
    Commented yesterday

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .