Definability in the signature of first-order logic with identity
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.
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$.