4
$\begingroup$

Let $L$ be the language of first-order logic with equality and $D$ a set, considered as a model of $L$. Is there a nice characterization of the subsets of $D^n$ that are definable in $L$ with parameters from $D$? For instance, presumably the definable subsets of $D^1$ are just the finite and cofinite subsets. (Any references appreciated too.)

$\endgroup$
  • $\begingroup$ I feel like you're asking for more than the definition of pointwise definability in a structure. There are sets which contain finite subsets that are not definable. Could you say a little bit more about what you mean? $\endgroup$ – Nika Dec 16 '19 at 23:49
  • $\begingroup$ I wanted simple necessary and sufficient conditions for a subset of $D^n$ to be characterized by a formula in $n$ variables and parameters in $D$. I was hoping they existed, since there is a simple characterization when $n=1$, namely the finite and cofinite subsets of $D$. $\endgroup$ – Andrew Bacon Dec 16 '19 at 23:55
  • $\begingroup$ @Nika, you mentioned that there are sets with finite subsets that are not definable. Keep in mind that this question is about which subsets of $D^n$ will be definable with parameters from $D$. $\endgroup$ – Andrew Ostergaard Dec 16 '19 at 23:56
  • 1
    $\begingroup$ "There are sets which contain finite subsets that are not definable". Every finite subset of $D$, $\{a_1...a_n\}$ is defined by the formula $x_1=a_1\vee ... \vee x_n=a_n$ with the parameters $a_1...a_n$. $\endgroup$ – Andrew Bacon Dec 16 '19 at 23:56
  • $\begingroup$ Whoops I must be misunderstanding something. I was thinking of an example in Enderton's A Mathematical Introduction to Logic which has $D = \{a,b,c\}$ and a relation on $D$, $E = \{\langle a,b \rangle, \langle a,c \rangle \}$, for which neither $\{ b \}$ nor $\{ c \}$ are definable. Did I get definable confused with definable with parameters in $D$? $\endgroup$ – Nika Dec 17 '19 at 0:02
3
$\begingroup$

Here is a proof that the theory of any set $D$ (over the empty signature) has quantifier elimination. By induction on formulas, it suffices to eliminate one existential quantifier at a time. That is, it suffices to prove that if $\varphi(x_1,\dots,x_n,y)$ is a quantifier-free formula then there exists a quantifier-free formula $\psi(x_1,\dots,x_n)$ such that $$D\models\forall x_1\dots\forall x_n(\exists y\varphi(x_1,\dots,x_n,y)\leftrightarrow \psi(x_1,\dots,x_n)).$$ To prove this, define the shape of $(a_1,\dots,a_n)\in D^n$ to be the equivalence relation $\{(i,j):a_i=a_j\}$ on the set $\{1,\dots,n\}$. Observe that if $(a_1,\dots,a_n)$ and $(b_1,\dots,b_n)$ have the same shape, there is an automorphism (i.e., bijection) $f:D\to D$ which satisfies $f(a_i)=b_i$ for all $i$. Thus, $D\models \exists y\varphi(a_1,\dots,a_n,y)\leftrightarrow \exists y\varphi(b_1,\dots,b_n,y)$. In other words, the truth of $\exists y\varphi(a_1,\dots,a_n,y)$ depends only on the shape of $(a_1,\dots,a_n)$.

Now for any equivalence relation $\sim$ on $\{1,\dots,n\}$, let $\psi_\sim(x_1,\dots,x_n)$ be a quantifier-free formula that expresses that $(x_1,\dots,x_n)$ is $\sim$-shaped (so $\psi$ is a big conjuction of formulas of the form $x_i=x_j$ or $\neg x_i=x_j$ depending on whether $i\sim j$). Let $\psi$ be the disjunction of $\psi_{\sim}$ over all $\sim$ such that $D\models\exists y\varphi(a_1,\dots,a_n,y)$ if $(a_1,\dots,a_n)$ is $\sim$-shaped. We then see that for each possible shape of $(a_1,\dots,a_n)\in D^n$, $D\models \exists y\varphi(a_1,\dots,a_n,y)\leftrightarrow \psi(a_1,\dots,a_n)$, and so $\psi$ has the desired property.


From quantifier elimination, it follows that every definable subset of $D^n$ is defined by a quantifier-free formula, which is just a Boolean combination of atomic formulas. There are just three types of atomic formulas (with parameters):

  • $x_i=x_j$
  • $x_i=d$ (or $d=x_i$) for some parameter $d\in D$
  • $d=e$ for some parameters $d,e\in D$.

In the first case the corresponding definable subset is $$\{(x_1,\dots,x_n)\in D^n:x_i=x_j\},$$ and in the second case the corresponding definable subset is $$\{(x_1,\dots,x_n)\in D^n:x_i=d\}.$$ In the third case it is either $D^n$ or $\emptyset$ depending on whether $d=e$ is true, so we can ignore that case. Thus the definable subsets of $D^n$ are Boolean combinations of the two types of sets above: "diagonal" subsets where two coordinates are equal, or "hyperplane" subsets where one coordinate has a fixed value.

When $n=1$ both of these types are finite or cofinite sets and so the definable sets are just the finite or cofinite sets. For $n>1$, there is not any description that is much simpler than "Boolean combinations of these sets". If you like, you could say that for any subset $A\subseteq D^n$ definable from parameters $d_1,\dots,d_m\in D$, there is a set $S$ of equivalence relations on $\{1,\dots,n+m\}$ such that $A$ is the set of all $(x_1,\dots,x_n)$ such that the shape of $(x_1,\dots,x_n,d_1,\dots,d_m)$ is in $S$.

$\endgroup$
  • $\begingroup$ Seeing the proof of quantifier elimination was really helpful for me. Thanks! $\endgroup$ – Andrew Bacon Dec 17 '19 at 1:09
4
$\begingroup$

If $D$ is finite, then we can define any subset of $D^n$ using parameters from $D$.

If $D$ is infinite, then it is what we call a strongly minimal structure: its definable subsets are indeed either finite or cofinite. The theory of $D$ is that of infinite sets, and this theory has quantifier elimination, which tells you something about the definable subsets of general $D^n$. The only atomic formula in this language is "$x = y$". This corresponds to a definable subset of the form $\{(x_1, \ldots, x_n) \in D^n : x_i = d\}$ for some $1 \leq i \leq n$ and $d \in D$. The definable subsets of $D^n$ are then Boolean combinations of such sets.

Edit: as Eric Wofsey pointed out in the comments, we can also use $\{(x_1, \ldots, x_n) \in D^n : x_i = x_j\}$ in our Boolean combination (getting for example the diagonal of $D^2$). The case of $\{(x_1, \ldots, x_n) \in D^n : d = e\}$, for $d, e \in D$ is really not interesting, because it is either the entire set or the empty set.

$\endgroup$
  • $\begingroup$ Thanks, this characterization is very helpful. Do you have a reference for the fact about quantifier elimination? $\endgroup$ – Andrew Bacon Dec 17 '19 at 0:07
  • $\begingroup$ And could you say a little more about why it implies that the definable sets have that form? Is there a general fact about theories with quantifier elimination you are appealing to? $\endgroup$ – Andrew Bacon Dec 17 '19 at 0:07
  • $\begingroup$ @AndrewBacon: This is immediate from the definition of quantifier elimination. Quantifier elimination says every formula is equivalent to a quantifier-free formula, and a quantifier-free formula is by definition a Boolean combination of atomic formulas. $\endgroup$ – Eric Wofsey Dec 17 '19 at 0:28
  • 1
    $\begingroup$ Oh, the description of the definable subsets corresponding to atomic formulas here is incorrect, though: they can also have the form $\{(x_1,\dots,x_n)\in D^n:x_i=x_j\}$. (Or $\{(x_1,\dots,x_n)\in D^n:d=e\}$ for some $d,e\in D$, but such a set is either $\emptyset$ or $D^n$ so we don't need to include that case.) This is because an atomic formula is $x=y$ where each of $x$ and $y$ can be either a variable or a parameter, so there are different cases depending on how many of them are parameters. $\endgroup$ – Eric Wofsey Dec 17 '19 at 0:34
  • $\begingroup$ Right, I can see how the definable subsets are Boolean combinations of those sets, given quantifier elimination. $\endgroup$ – Andrew Bacon Dec 17 '19 at 0:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.