I'm having some trouble understanding the following definition from Marker's Model Theory, Definition 1.3.9:
We say that an $\cal L_0$-structure $\cal N$ is interpretable in an $\cal L$-structure $\cal M$ if there is a definable $X \subseteq M^n$, a definable equivalence relation $E$ on $X$, and for each symbol of $\cal~L_0$ we can find definable $E$-invariant sets on $X$ (where “definable” means definable in $\cal L$) such that $X/E$ with the the induced structure is isomorphic to $\cal N$.
I don't get what in this context, "$E$-invariant is". I'm also a little confused about this overall definition as I can't picture a single example.
Before the definition, the author motivated it with an "example" from group theory using quotient groups, but after the rigorous definition, the example he gives is much more convoluted using projective n-spaces over fields (which I'm not very familiar with).
if possible, can you give me a clear example using group theory of a structure being interpretable within another structure that might help me grasp this concept?
I was trying to work with the example Noah Schweber gave in his answer and this is what I got: Using the notation from the definition, and for the sake of having two different languages at play, let $\mathcal L_0=\{+,e\}$ be the language of groups, and $\mathcal L=\{+,-,\cdot ,0,1\}$ be the language of rings. Let $\mathcal N = (\mathbb Q,+,0)$ be an $\mathcal L_0$-structure and $\mathcal M = (\mathbb Z,+,-,\cdot,0,1)$ be an $\mathcal L$-structure. We want to show that $\mathcal N$ is interpretable in $\mathcal M$.
Let $X\subseteq \mathbb Z^2$ be the definable subset given by $X=\{(a,b)\in \mathbb Z^2 : \phi(a,b)\}$ with $\phi(a,b):=(b\neq 0)$.
Now, let $E\subseteq X^2$ be an equivalence relation given by $E=\{((a,b),(c,d))\in X^2:\psi((a,b),(c,d))\}$, with $\psi((a,b),(c,d)):=(a\cdot d = b\cdot c)$
This is where my first question arises: $E$, is an equivalence relation in $X$, thus it must be a subset of $X^2$. But $E$ is definable in $\mathcal L$, thus it must be a subset of $\mathbb Z^n$, for some n (since $\mathbb Z$ is the universe of the structure $\cal M$.) This seems like a contradiction. How can both be correct?
Now, If I'm not mistaken, the main goal is to create a new $\mathcal L_0$-structure, $\mathcal K=(X/E,\oplus,I)$ in the language of groups, such that the projection map $\pi:\mathbb Q \to X/E$ given by $\pi(p/q)=[(p,q)]_E$ is an isomorphism between the structures $\mathcal N$ and $\mathcal K$. Is this correct?
This is where my second question arises: I'm having a lot of trouble defining the operations $\oplus$ and the constant $I$ for the following reason:
- $I$ is a constant, so how can it be a "definable $E$-invariant set"?
- $\oplus$ is a function from $(X/E)^2\to X/E$, thus $\oplus$ should be a subset of $(X/E)^2\times (X/E)$ but, once again, because of the definition of definability, it should be a subset of $\mathbb Z^n$ for some $n$.
Also, what does the author mean by "Induced structure" at the end of the definition?
The notion of invariance here has nothing to do with model theory. Given a set $X$ and an equivalence relation $E$ on $X$, a subset $A\subseteq X$ is $E$-invariant iff whenever $aEb$ then $(a\in X)\leftrightarrow (b\in X)$. Put another way, an $E$-invariant set is a union of $E$-classes.
To motivate the terminology, think in terms of characteristic functions. Given a set $A$ with characteristic function $\chi_A$, $A$ is $E$-invariant iff $\chi_A(a)$ doesn't change value when we replace $a$ with some $b$ which is $E$-related to $a$. This is easiest to think about when $E$ itself comes from some reasonably-natural group action $G$ on $X$ (in the sense that $aEb\leftrightarrow\exists g\in G(ga=b)$), but applies just as well even when this isn't the case.
Here are a couple of examples:
The set of odd integers is invariant, with respect to the relation "has the same parity as" on the integers.
More generally, if $G$ is a group and $N$ is a normal subgroup of $G$, each coset of $N$ in $G$ is $\sim_N$-invariant (where $a\sim_Nb$ iff $a/N=b/N$).
Another way to think about things is that "$E$-invariant" means "makes sense in $X/E$."
To see how model theory enters the picture, consider the usual interpretation of $\mathbb{Q}$ in $\mathbb{Z}$ (both considered as rings) where we think of a rational as an equivalence class of ordered pairs of integers - intuitively, $(a,b)$ represents ${a\over b}$. Here we have:
$n=2$,
$X=\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$ (we don't allow zero as a denominator), and
$(a,b)E(c,d)\leftrightarrow ad=bc$.
(It's a good exercise to work out the "$\varphi$-parts" of this interpretation: how do we make sense of addition/multiplication of rationals given only addition/multiplication of integers? The point is that this part has to be appropriately well-defined - this is all $E$-invariance is about in this context.)
Re: your additional questions, most of them are addressed by the usual "product-associativity convention" - we tend in mathematics to identify e.g. $(U^2)\times (U^2)$ and $U^4$. So - refering to my example above re: $\mathbb{Q}$ and $\mathbb{Z}$ - since $X\subseteq\mathbb{Z}^2$ we can identify $E$ with a subset of $\mathbb{Z}^4$.
I don't really understand the issue you're having with $I$. Do you see how, in the example above, $\{(a,a): a\not=0\}$ is a definable $E$-invariant set corresponding to the rational number $1$?