What does Feferman-Vaught say $\textbf{exactly}$ about definable subsets of a direct product of two structures

logicmodel-theory

Below I reproduce a consequence of the Feferman-Vaught theorem, taken from Wilfrid Hodges' book Model Theory:

Corollary 9.6.4: Let $L$ be a first-order language, let $A$ and $B$ be $L$-structures and let $\phi(\overline{x})$ be a formula of $L$. Then there is a finite set $\bigl\{\bigl(\theta_i(\overline{x}),\chi_i(\overline{x})\bigr): i<n\bigr\}$ of pairs of formulas of $L$, such that for all tuples $\overline{a}=(a_0,a_1,\ldots),\overline{b}=(b_0,b_1,\ldots)$ from $A,B$ respectively,

$$A\times B\models\phi\bigl((a_0,b_0),(a_1,b_1),\ldots\bigr)\iff\ \style{font-family:inherit;}{\text{for some}}\ i<n, A\models\theta_i(\overline{a})\ \style{font-family:inherit;}{\text{and}}\ B\models\chi_i(\overline{b}).$$

I have two questions about this result:

  1. Does this result say that a definable subset in a product of two structures is the finite union of "definable rectangles" (that is, Cartesian produts of definable subsets in the respective components)?

  2. It is true, conversely, that every definable rectangle is a definable subset of the product structure?

Note that Question 2 is not trivial, because the statement of the corollary assumes that a definable subset of the product is given.

Bonus question: Does the results above hold for definable subsets with parameters in a uniform way? that is, if $\phi$ has parameters, can formulas $\theta_i$ and $\chi_i$ be chosen depending on the components of such parameters? I ask this because the proof of the result is left to the reader ("Proof: Unpick what the theorem says."), which amounts to reexamine the previous material.

Best Answer

Re: $(1)$, yes, that's exactly what the result is saying.

And this holds uniformly since we can always look at expansions of our starting structures:

Suppose $d_1=(a_1,b_1),..., d_k=(a_k,b_k)\in A\times B$ and $X\subseteq (A\times B)^n$ is definable over $d_1,..., d_k$ in the structure $A\times B$. Let $u_1,...,u_k$ be new constant symbols and let $A'$ and $B'$ be the expansions of $A$ and $B$ gotten by interpreting $u_i$ as $a_i$ and $b_i$, respectively. Then $X$ is parameter-freely definable in the structure $A'\times B'$.

Re: $(2)$, perhaps surprisingly, the answer is no - in general, products of definable sets are not definable. This is because we "lose the coordinatization." For example, suppose both $A$ and $B$ are the group $(\mathbb{Z};+)$, and consider the set $$X=\{(a,b)\in\mathbb{Z}^2: a=0\}.$$ Since both $\mathbb{Z}$ and $\{0\}$ are definable in $(\mathbb{Z};+)$, the set $X$ is a product of definable sets, but it is clearly not definable since it is not fixed by all automorphisms (consider the map $(u,v)\mapsto (v,u)$, for example).

Related Question