Definability in the signature of first-order logic with identity

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.)

• 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? – Nika Dec 16 '19 at 23:49
• 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$. – Andrew Bacon Dec 16 '19 at 23:55
• @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$. – Andrew Ostergaard Dec 16 '19 at 23:56
• "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$. – Andrew Bacon Dec 16 '19 at 23:56
• 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$? – Nika Dec 17 '19 at 0:02

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$$.

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

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.

• Thanks, this characterization is very helpful. Do you have a reference for the fact about quantifier elimination? – Andrew Bacon Dec 17 '19 at 0:07
• 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? – Andrew Bacon Dec 17 '19 at 0:07
• @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. – Eric Wofsey Dec 17 '19 at 0:28
• 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. – Eric Wofsey Dec 17 '19 at 0:34
• Right, I can see how the definable subsets are Boolean combinations of those sets, given quantifier elimination. – Andrew Bacon Dec 17 '19 at 0:38