# Can all relations be defined from symmetric relations?

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.

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" 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!

• Thanks, this is very helpful. I had come across the trick you mentioned initially before (the "silly" answer), but had forgotten it when I wrote the question! Very interested in the answer to you refined question. – Andrew Bacon Feb 26 at 1:51
• I've gone ahead and posted a separate question for it, as I think this one is technically answered affirmatively by your first answer. math.stackexchange.com/questions/3126900/… – Andrew Bacon Feb 26 at 2:12