This is an extension of this question, suggested by Noah Schweber.
Suppose I have some set of relations $(R_i)_{i\in I}$ over a set $D$: $R_i\subseteq D^{n_i}$, $n_i\in \mathbb{N}$.
Noah defines a relation $R$ to be set-ary iff, whenever $\{x_1,...,x_n\} = \{y_1,...,y_n\}$ then $(x_1,...,x_n)\in R$ if and only if $(y_1,...,y_n)\in R$.
I would like to know if there is always a set of set-ary relations from which $(R_i)_{i\in I}$ are first-order definable. For example, can $<$ on $\mathbb{Z}$ be defined by set-ary relations?
Any unary or symmetric binary relation is set-ary. Thus, to provide an affirmative answer to the question, for domains $D$ with at least 3 elements, it suffices to show that any relation on such a domain is definable from unary and symmetric binary relations.
Case 1. $D$ is finite but has at least $3$ elements.
In this case, any relation on $D$ is p.p.-definable from unary relations and equivalence relations. To see this, let $\Omega$ be the set of all unary relations and equivalence relations on $D$. It is not hard to see that the only polymorphisms $f:\langle D; \Omega\rangle^k\to \langle D; \Omega\rangle$ are the projection maps. This implies that any finitary relation on $D$ is p.p.-definable from $\Omega$, according to the results of
Bodnarcuk, V. G.; Kaluznin, L. A.; Kotov, V. N.; Romov, B. A.
Galois theory for Post algebras. I, II.
Kibernetika (Kiev) 1969, no. 3, 1–10; ibid. 1969, no. 5, 1-9.
Case 2. $D$ is infinite.
Let $R$ be a $k$-ary relation on $D$. Partition $D$ into $k+1$ subsets of equal size, $D_0, D_1, \ldots, D_k$. For each $k$-tuple, $t=(i_0,\ldots,i_{k-1})\in \{0,\ldots,k\}^k$ I will explain how to define $$R_t = R\cap (D_{i_0}\times \cdots \times D_{i_{k-1}}).$$ Then $R$ can be defined as the union of the $R_t$'s.
Let $E = D_j$ for some $D_j$ different from any of $D_{i_0}, \ldots, D_{i_{k-1}}$. This is possible, since there are more than $k$ of the $D_j$'s. Now choose an injection $f:R_t\to E$. It is easy to check that $|R_t|\leq |D|=|E|$, so this is possible.
For any $r=(r_0,\ldots,r_{k-1})\in R_t$, and any $i<k$, put the pairs $(r_i, f(r)), (f(r), r_i)$ into a relation $S_i$. Put no other pairs in $S_i$.
The relation $R_t$ is definable from the unary relation $E$ and symmetric binary relations $S_i$. Namely, $(r_0,\ldots,r_{k-1})\in R_t$ iff $r_i\notin E$ for any $i$, and, $\exists e\in E$ such that $(r_i,e)\in S_i$ for each $i$. \\\
The unary relations and the symmetric binary relations are not enough to p.p.-define all relations on a $2$-element domain. For example, you can't p.p.-define $$\{(0,0,1), (0,1,0), (1,0,0)\}.$$ But you can p.p.-define all relations on the $2$-element domain from set-ary unary and ternary relations by an argument like the one for Case 1