¿Puede una relación ser transitiva cuando es simétrica pero no reflexiva?

Question

Más o menos lo que pide el título. Pero aquí hay algo de contexto:

Supongamos que $X$ es finito y $R$ es una relación sobre $X$ que no es reflexivo pero sí simétrico. Además, supongamos que podemos descartar $xRy$ y $yRz$ ambos ocurren $\forall x,y,z\in X$ s.t. $x\neq y$ y $y\neq z$ y $x\neq z$ . Así que podemos descartar que $xRy$ y $yRz$ cuando $x,y,z$ son distinto . En este punto, parece que $R$ puede ser vacuamente transitivo. Sin embargo, como $R$ es simétrica, $xRy$ y $yRx$ están bien. Pero como $R$ no es reflexivo, no podemos tener $xRx$ lo que parece ser una violación de la transitividad si $xRy$ y $yRx$ . ¿Es éste un contraejemplo "legítimo"?

Answer 1

Simétrico significa que podemos representar la relación como un grafo no dirigido. Transitivo significa que este gráfico está compuesto por componentes conectados que se parecen a un punto o $K_n$ con cada punto conectado a sí mismo. La reflexividad significa cada punto está conectado a sí mismo.

Por lo tanto, una condición necesaria y suficiente es que un componente sea un punto (es decir, un elemento no está relacionado con ningún otro). Precisamente en estos casos tu prueba falla porque requiere que cada $x$ estar relacionado con otro $y$ .

Answer 2

La respuesta es sí; la relación vacía (en cualquier conjunto no vacío $X$ ) es transitiva, simétrica y no reflexiva.

Answer 3

Si existe $(x,y)$ en una relación simétrica, también existe $(y,x)$ . Si esta relación es transitiva, entonces $(x,x)$ y $(y,y)$ debe existir en la relación. Sin embargo, esto no es suficiente para que la relación sea reflexiva.   Que sería más requieren que cada $x$ en el conjunto subyacente tiene algunos $y$ donde $(x,y)$ está en la relación simétrica y transitiva.

Una relación simétrica y transitoria, $R$ , sobre el conjunto $A$ es también reflexivo exactamente cuando $\forall x{\in}A~\exists y{\in} A :(x,y)\in R$ .

---

Una relación simétrica y no reflexiva, $R$ , sobre el conjunto $A$ , puede ser transitivo sólo si hay algo (en $A$ ) que no está relacionado con nada.   Un simétrico $R$ donde algo no está relacionado con nada es no necesariamente transitivo, sino que puede ser.  

$${\begin{Bmatrix}(0,0),&(0,1),&&(0,3)\\(1,0),&(1,1),&&(1,3)\\~\\(3,0),&(3,1),&&(3,3)\\&&&&(4,4)\end{Bmatrix}{\text{ is a symmetric, non-reflexive, transitive relation}\\\text{over the set }\{0,1,2,3,4\}}\\\begin{Bmatrix}&(0,1)\\(1,0),&(1,1),&&(1,3)\\~\\&(3,1)\\&&&&(4,4)\end{Bmatrix}{\text{ is a symmetric, non-reflexive, non-transitive relation}\\\text{where something (2) is not related to anything}}}$$

Answer 4

Relaciones simétricas transitivas en $X$ son lo mismo que una partición de $X$ más una elección de subconjunto $S \subset X$ de elementos que sí satisfacen la reflexividad. Los casos extremos $S=X$ y $S$ vacío son (respectivamente) relaciones de equivalencia y uniones disjuntas de grafos completos. Ejemplos de estas últimas son las relaciones irreflexivas como "hermano", "compañero de piso", "cónyuge", "correligionario" y "compañero de conspiración".

Sería interesante ver un ejemplo natural con $S$ un subconjunto adecuado.

Answer 5

Yo también me lo pregunté una vez y me quedé perplejo durante un tiempo. El truco detrás de esto es que uno necesita prestar mucha atención a la declaración exacta y precisa de las propiedades en cuestión . Esas pequeñas palabras de la esencia de la vida realmente cuentan . Aquí hay que prestar atención a la lógico estructura. A saber:

1. La declaración de simetría es: Para todo $x$ y $y$ en el dominio y el codominio, SI $x\ R\ y$ ENTONCES $y\ R\ x$ .
2. La declaración de transitividad es: Para todo $x$ y $y$ en el dominio y el codominio, SI $x\ R\ y$ y $y\ R\ z$ ENTONCES $x\ R\ z$ .

Las palabras clave son las que están en negrita: " SI ", " ENTONCES ". Estos son implicaciones . No afirman la verdad de los enunciados que unen y, además, sólo pueden utilizarse para inferir algo sobre la verdad de uno de los enunciados unidos si se afirma o niega convenientemente la del otro. En particular, en lo que respecta a la simetría, no hay nada más que nos permita suponer que la hipótesis de la implicación - $x\ R\ y$ - es cierto, y eso es lo que necesitamos para concluir que $x\ R\ x$ por el razonamiento dado en el post original. En particular, si queremos demostrar que $x\ R\ x$ por cada $x$ entonces necesitamos que $x\ R\ y$ para al menos una $y$ también para cada uno de esos $x$ -valores . Sin embargo, no tenemos nada que nos diga que es así. No hay enunciados con cuantificadores existenciales que nos digan que tiene que existir algo que valide la hipótesis de la implicación en la ley de simetría. Tiene un cuantificador universal pero ningún cuantificador existencial.

Por tanto, el argumento, aunque válido, no es sólido.

Se puede construir un contraejemplo a partir de cualquier relación de equivalencia simplemente borrando para cualquier $x$ todos los pares de la forma $(x, y)$ del gráfico. Esto falsificará la reflexividad, pero dejará a los otros dos sin cambios, ya que no se puede concluir nada de ellos cuando sus hipótesis son falsas.