Can all relations be defined from symmetric relations?

Question

I have a question about first-order structures over some set $D$. Suppose I have some set of relations $(R_i)_{i\in I}$ where $R_i\subseteq D^{n_i}$, $n_i\in \mathbb{N}$.

I would like to know if there is always a set of symmetric relations from which $(R_i)_{i\in I}$ are first-order definable, where a relation is symmetric when $(x_1...x_n)\in R$ iff $(x_{\pi 1}...x_{\pi n})\in R$ for every permutation $\pi$ of $\{1...n\}$.

Example that prompted this question: Suppose $D=\mathbb{Z}$ and consider the relation $<$. If we allow symmetric function symbols, then then $<$ may be defined from the symmetric $+$ and a unary (and thus symmetric) predicate $P$ expressing positivity. (Namely: $x< y$ is given by the formula $\exists z(P(x+z)\wedge \neg P(y+z))$.) But if we do not allow function symbols, I can't tell whether $<$ is definable from symmetric relations.

Answer 1

Excellent question! Let me first give a silly answer, and then try to say something more satisfying.

---

We can quite easily introduce asymmetry via counting: e.g. looking at $D=\mathbb{N}$ for the moment, consider the ternary relation $R\subseteq \mathbb{N}^3$ given by setting $R(a,b,c)$ iff:

• $a,b,c$ are all distinct,

• $a,b,c$ are all equal, or

• the more common input is greater than the less common input (e.g. $R(2,3,3)$ holds but $R(2,2,3)$ doesn't).

Then $R$ is quite clearly symmetric, and the relation "$x<y$" is equivalent to "$x\not=y\wedge R(x,y,y)$." More generally, we can use this trick to copy over any relation into a symmetric one.

---

But that's silly. Let's throw away counting by restricting attention to set-ary relations:

A relation $R\subseteq D^n$ is set-ary if whenever $\overline{x},\overline{y}$ are $n$-tuples whose ranges are equal, we have $R(\overline{x})\iff R(\overline{y})$. E.g. a $4$-ary set-ary relation $R$ satisfies $$R(x,x,y,y)\iff R(x,y,y,y)\iff R(y,x,y,x)\iff ...$$ for all $x,y\in D$.

Any set-ary relation is clearly symmetric, but we've also "removed the ability to count."

Well, here we certainly can get some amount of asymmetry. For example, taking $D=\mathbb{R}$, from the unary (hence set-ary) relation "is negative" we can define the binary asymmetric relation $P(x,y)\iff D(x)$ - we have e.g. $P(-1,1)$ but not $P(1,-1)$.

So we can get some asymmetry even from full symmetry. But we did not get an arbitrary relation from only set-ary relations! In particular, the $P$ above has "large regions" of symmetry.

• One particularly strong way to phrase this: we can partition our domain into two pieces (negatives and nonnegatives) such that $P$ is symmetric when restricted to each piece separately, and $P$ either holds always or fails always (in this case, holds always) of a pair where the first element is taken from the first piece and the second element from the second piece. So in some piece we have a finite amount of asymmetry - the ordering on the pieces - and then everything else is symmetric.

So let's try to go further. The simplest high ambition would be:

Is there a linear ordering of $D$ definable purely from set-ary relations?

I don't immediately see the answer to this stronger question; I suspect the answer is "no," however. So this answer isn't really complete - but I hope it's helped!