Can every relation be defined from "set-ary" relations? 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?
 A: 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
