# 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?

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, 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

• The proof in case 1 seems overkill - just pin down each element $e$ by a unary relation $U_e$ holding on exactly that element, and define an arbitrary finite-arity relation $R$ as $$R(x_1,...,x_n)\iff\bigvee_{R(y_1,...,y_n)}(U_{y_1}(x_1)\wedge ...\wedge U_{y_n}(x_n)).$$ Or am I missing something? (I also don't understand why this wouldn't get you all relations on a $2$-element domain - are you using a more restrictive notion of "definability?") – Noah Schweber Feb 26 at 4:08
• I should have said: I was going for p.p.-definability on finite domains (because I could), but first-order definability on infinite domains. (I just edited my answer to say this.) – Keith Kearnes Feb 26 at 4:13
• Ah, sorry, I read too quickly. "PP-definable" means "definable by an existential quantification over a conjunction of positive relation instances," right? – Noah Schweber Feb 26 at 4:25