¿Se pueden definir todas las relaciones a partir de relaciones simétricas?

Question

Tengo una pregunta sobre las primeras estructuras de orden sobre un conjunto $D$. Supongamos que tengo un conjunto de relaciones de $(R_i)_{i\in I}$ donde $R_i\subseteq D^{n_i}$, $n_i\in \mathbb{N}$.

Me gustaría saber si hay siempre un conjunto de relaciones simétricas a partir de la cual $(R_i)_{i\in I}$ son de primer orden definibles, cuando una relación es simétrica $(x_1...x_n)\in R$ fib $(x_{\pi 1}...x_{\pi n})\in R$ por cada permutación $\pi$ de $\{1...n\}$.

Ejemplo que inspiró a esta pregunta: Supongamos $D=\mathbb{Z}$ y considerar la relación $<$. Si permitimos que la simétrica de la función de símbolos, a continuación, $<$ puede ser definido a partir de la simétrica $+$ y un unario (y por lo tanto simétrica) predicado $P$ expresan positividad. (Es decir: $x< y$ está dado por la fórmula $\exists z(P(x+z)\wedge \neg P(y+z))$.) Pero si no permitimos que la función de los símbolos, no puedo decirle si $<$ es definible a partir de relaciones simétricas.

Answer 1

Excelente pregunta! Permítanme en primer lugar darle una tonta respuesta y, a continuación, intenta decir algo más satisfactorio.

---

Podemos muy fácilmente introducen a través de la asimetría de conteo: por ejemplo, mirando a $D=\mathbb{N}$ por el momento, la posibilidad de la relación ternaria $R\subseteq \mathbb{N}^3$ dado por la configuración de $R(a,b,c)$ fib:

• $a,b,c$ son distintos,

• $a,b,c$ son todos iguales, o

• el más común de entrada es mayor que el menos común de entrada (por ejemplo, $R(2,3,3)$ sostiene sino $R(2,2,3)$ no).

A continuación, $R$ es claramente simétrica, y la relación "$x<y$" es equivalente a "$x\not=y\wedge R(x,y,y)$." Más en general, podemos utilizar este truco para copiar cualquier relación en un simétrica.

---

Pero que tontería. Vamos a tirar de conteo mediante la restricción de la atención a los set-ary relaciones:

Una relación $R\subseteq D^n$ es set-ary si siempre $\overline{x},\overline{y}$ se $n$-tuplas cuyos rangos son iguales, tenemos $R(\overline{x})\iff R(\overline{y})$. E. g. un $4$-ary set-ary relación $R$ satisface $$R(x,x,y,y)\iff R(x,y,y,y)\iff R(y,x,y,x)\iff ...$$ for all $x,y\in D$.

Cualquier conjunto-ary relación es claramente simétrica, pero también hemos "quitado la habilidad de contar."

Bueno, he aquí, que sin duda puede obtener una cierta cantidad de asimetría. Por ejemplo, $D=\mathbb{R}$, a partir de la unario (de ahí set-ary) la relación "es negativo" se puede definir el binario relación asimétrica $P(x,y)\iff D(x)$ - , tenemos por ejemplo, $P(-1,1)$ pero no $P(1,-1)$.

De modo que podemos obtener algún grado de asimetría incluso de la completa simetría. Pero lo hicimos de no obtener una arbitraria relación de sólo set-ary relaciones! En particular, el $P$ arriba tiene "grandes regiones" de la simetría.

• Una manera particularmente fuerte para la frase: se puede partición de nuestro dominio en dos piezas (negativos y nonnegatives) tal que $P$ es simétrica restringido a cada pieza por separado, y $P$ tampoco tiene siempre o no siempre (en este caso, tiene siempre) de una pareja donde el primer elemento es tomado de la primera pieza, y el segundo elemento de la segunda pieza. Por lo que en algunos pieza tenemos una cantidad finita de asimetría - el orden de las piezas y, a continuación, todo lo demás es simétrica.

Así que vamos a intentar ir más allá. El más simple de alta ambición sería:

Hay un lineal de pedidos de $D$ definibles puramente de set-ary relaciones?

Yo no ver de inmediato la respuesta a esta pregunta más fuerte; sospecho que la respuesta es "no", sin embargo. Así que esta respuesta no es muy completo pero espero que ayudaron!