6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andrew Bacon Feb 26 at 1:51
  • $\begingroup$ 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/… $\endgroup$ – Andrew Bacon Feb 26 at 2:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.