Closure Properties of Definable Sets

Question

I'm reading through Marker's Model Theory: An Introduction and I'm having a bit of trouble with the proof of Proposition 1.3.4, which gives a characterization of definable sets. In particular, I need help with his proof that the graph of any term is in the family of sets $\mathcal{D}$, defined as follows:

Marker first shows that the graphs of constant terms and variable terms are in $\mathcal{D}$, which is clear to me. He then shows that the graph of an m-ary function term applied to $m$ n-ary terms $t=f(t_1, ..., t_m)$ is contained in $\mathcal{D}$, assuming by induction that the graph of each $t_{i}^\mathcal{M}$ is contained in $\mathcal{D}$, and then writing an expression for the graph of $t$ in terms of the graphs of the $t_i^\mathcal{M}$s and the graph of $f^\mathcal{M}$:

The expression for the graph of $t^\mathcal{M}$ clear to me. What's non-obvious to me is why it's contained in $\mathcal{D}$, which Marker does not explain except for a brief statement that this follows from the listed closure properties. I've been trying to figure out a way to construct the graph of $t^\mathcal{M}$ just from the graphs of the $t_i^\mathcal{M}$s and $f^\mathcal{M}$ and the properties i-viii, but I'm struggling to. One idea I had was to notice that the graph of $t$ is the result of applying the projection map in property vii $m$ times to the intersection $\{(\bar{x}, y, \bar{z}) : (\bar{z}, y)\in G\}\cap\bigcap_{i=1}^m \{(\bar{x}, y, \bar{z}) : (\bar{x}, z_i)\in G_i\}$. If each of the sets in this intersection is contained in $\mathcal{D}$, then the result follows from property vi. However, I can't seem to show that these sets are contained in $\mathcal{D}$. That they are almost seems to follow from property v, but the components of the ordered pairs are in the wrong order. Is there a way to finish this argument? Or a different way to show this? I feel like I might be missing something obvious.

Answer 1

You're on the right track - the key issue here (which I agree that Marker doesn't explain clearly) is "the components of the ordered pairs are in the wrong order".

There are many variants on the list of closure properties characterizing the definable sets. One common such property, which Marker omits from his list, is closure under permutation of coordinates:

• If $X\in D_n$ and $\pi$ is a permutation of $\{1,\dots,n\}$, then $\pi(X) = \{(x_1,\dots,x_n)\mid (x_{\pi^{-1}(1)},\dots,x_{\pi^{-1}(n)})\in X\}\in D_n$.

This closure property clearly holds of the class of definable sets (apply the permutation to the tuple of variables), and you could use it to finish your agument, since you could freely rearrange coordinates of tuples.

Now as it happens, this closure property follows from Marker's list of closure properties. Note that Marker allows cylindrification (taking the product with $M$) on the left, projection on the right, and equality between arbitrary coordinates.

Suppose $X\in D_n$ and $\pi$ is a permutation of $\{1,\dots,n\}$. Apply rule (v) $n$ times, to obtain $M^n\times X\in D_{2n}$. Then intersect with the $n$ sets $\{(y_1,\dots,y_n,x_1,\dots,x_n)\mid y_{\pi(i)} = x_i\}\in D_{2n}$ for $1\leq i \leq n$. Then project $n$ times, to obtain $\pi(X)\in D_n$.