3.5: Propiedades de las endorelaciones

Como mencioné, muchas de las relaciones que nos importan son endorelaciones (relaciones entre un conjunto y él mismo). Algunas endorelaciones tienen una o más de las siguientes propiedades simples que son útiles para hablar. A lo largo de esta sección, supongamos que esa\(R\) es la relación en cuestión, y se define de conjunto\(A\) a conjunto\(A\).

• Reflexividad. Una relación\(R\) es reflexiva si\(x R x\) por cada\(x \in A\). Otros pares ordenados también pueden estar en la relación, claro, pero si decimos que es reflexivo estamos garantizando que cada elemento está ahí consigo mismo. “HasSeen” es casi con certeza una relación reflexiva, presumiendo que los espejos están relativamente extendidos en el mundo. “ThinksisBeautiful” no es reflexivo, sin embargo: algunas personas se piensan bellas, y otras no.

• Simetría. Una relación es simétrica si\(x R y\) siempre\(y R x\) y viceversa. Esto no quiere decir que\((x,y)\) esté en la relación para todos\(x\) y\(y\) —sólo que si\((x,y)\) está en la relación, entonces\((y,x)\) se garantiza que también esté en la relación. Un ejemplo sería “HasshakenHandsWith”. Si te he estremecido la mano, entonces me has estremecido la mano, punto. De otra manera no tiene sentido.

• Anti simetría. Una relación es antisimétrica si\(x\) -\(R\) -\(y\) cuando\(y R x\) y viceversa (a menos que\(x\) y\(y\) sean lo mismo.) Dicho de otra manera, si\((x,y)\) está en la relación, bien, pero entonces no\((y,x)\) puede ser. Un ejemplo sería “iStallerthan”. Si soy más alto que tú, entonces no puedes ser más alto que yo. De hecho podríamos tener la misma altura, en cuyo caso ni el par (tú, yo) ni (yo, tú) estarían en la relación, pero en todo caso los dos no pueden coexistir.

• Tenga en cuenta cuidadosamente que antisimétrico es muy diferente de un simétrico. Una relación a simétrica es simplemente aquella que no es simétrica: en otras palabras, hay alguna\((x,y)\) ahí dentro sin coincidencia\((y,x)\). Una relación antisimétrica, por otro lado, es aquella en la que se garantiza que no\((y,x)\) hay coincidencias para ninguna\((x,y)\).

  Si tiene problemas para visualizar esto, aquí hay otra forma de pensarlo: darse cuenta de que la mayoría de las relaciones no son ni simétricas ni antisimétricas. Es una especie de coincidencia que una relación sea simétrica: eso significaría para cada single\((x,y)\) que contiene, también contiene un\((y,x)\). (¿Cuáles son las posibilidades?) Del mismo modo, es una especie de coincidencia que una relación sea antisimétrica: eso significaría para cada single\((x,y)\) que contiene, no contiene a\((y,x)\). (Nuevamente, ¿cuáles son las posibilidades?) Tu relación promedio de Joe va a contener algunos\((x,y)\) pares que tienen\((y,x)\) pares coincidentes, y algunos que no tienen coincidencias. Tales relaciones (la gran mayoría) son simplemente simétricas: es decir, ni simétricas ni antisimétricas.

  Sorprendentemente, ¡en realidad es posible que una relación sea simétrica y antisimétrica! (pero no asimétrico.) Por ejemplo, la relación vacía (sin pares ordenados) es simétrica y antisimétrica. Es simétrico porque por cada par ordenado\((x,y)\) en él (de los cuales hay cero), también está el correspondiente\((y,x)\). ¹ Y de manera similar, por cada par ordenado\((x,y)\), el correspondiente no\((y,x)\) está presente. Otro ejemplo es una relación con sólo “dobles” en ella —digamos, {(3,3), (7,7), (Fred, Fred)}. Esto también es simétrico y antisimétrico (¡resuelva!)

• Transitividad. Una relación es transitiva si cuando\(x R y\) y\(y R z\), entonces se garantiza eso\(x R z\). La relación “iStallerThan” que definimos es transitiva: si me dices que Bob es más alto que Jane, y Jane es más alta que Sue, entonces sé que Bob debe ser más alto que Sue, sin que ni siquiera tengas que decirme eso. Así es como funciona “más alto que”. Un ejemplo de una relación no transitiva sería “HasBeat” con equipos de la NFL. Sólo porque los Patriots vencieron a los Steelers este año, y los Steelers ganaron a los Gigantes, eso no implica que los Patriots necesariamente ganen a los Gigantes. Los Gigantes en realidad podrían haber vencido al equipo-quién-golpea-el-equipo-quién-los golpea-ellos (tales cosas suceden), o carajo, es posible que los dos equipos ni siquiera hayan jugado entre sí este año.

Todos los ejemplos anteriores se definieron de manera intensiva. Solo para la práctica, veamos también algunas relaciones extensamente definidas. Utilizando nuestro familiar set de Harry Potter como\(A\), considera la siguiente relación:

(Harry, Ron)
(Ron, Hermione)
(Ron, Ron) (Hermione, Ron)
(Ron, Harry)
(Hermione, Hermione)
(Hermione, Hermione)

Considerar: ¿esta relación es reflexiva? No. Tiene (Ron, Ron) y (Hermione, Hermione), pero falta (Harry, Harry), así que no es reflexivo. ¿Es simétrico? Sí. Mira cuidadosamente los pares ordenados. Tenemos un (Harry, Ron), pero también un coincidente (Ron, Harry). Tenemos una (Hermione, Ron), pero también una coincidencia (Ron, Hermione). Entonces cada vez que tenemos una también\((x,y)\) tenemos el emparejamiento\((y,x)\), que es la definición de simetría. ¿Es antisimétrico? No, porque (entre otras cosas) tanto (Harry, Ron) como (Ron, Harry) están presentes. Por último, ¿es transitivo? No. Tenemos (Harry, Ron) y (Ron, Hermione), lo que significa que si es transitivo tendríamos que tener también (Harry, Hermione) ahí dentro, lo cual no lo hacemos.Entonces no es transitivo. Recuerda: para cumplir con cualquiera de estas propiedades, tienen que aplicar completamente. “Casi” sólo cuenta en herraduras.

Vamos a probar otro ejemplo:

(Ron, Harry)
(Ron, Ron)
(Harry, Harry)
(Hermione, Hermione)
(Harry, Hermione)
(Hermione, Harry)

¿Este es reflexivo? Sí. Tenemos a los tres magos apareciendo consigo mismos. ¿Es simétrico? No, ya que (Ron, Harry) no tiene rival. ¿Es antisimétrico? No, ya que (Harry, Hermione) sí tiene un partido. ¿Es transitivo? No, ya que la presencia de (Ron, Harry) y (Harry, Hermione) implica la necesidad de (Ron, Hermione), que no aparece, así que no hay dados.

Órdenes parciales y posets

Un par de otros términos divertidos: una endorelación que es (1) reflexiva, (2) antisimétrica y (3) transitiva se llama orden parcial. Y un conjunto junto con una orden parcial se llama conjunto parcialmente ordenado, o “poset" para abreviar. El nombre “orden parcial” tiene sentido una vez que piensas a través de un ejemplo.

Es posible que hayas notado que cuando los perros se encuentran entre sí (especialmente los perros machos) a menudo se dan vueltas entre sí y hacen un balance entre sí y tratan de establecer el dominio como el llamado “perro alfa”. Esta es una especie de orden picoteante que establecen muchas especies diferentes. Ahora supongamos que tengo el conjunto\(D\) de todos los perros, y una relación “esAtlastastoughas” entre ellos. La relación comienza con cada pareja reflexiva que hay en ella: (Rex, Rex), (Fido, Fido), etc. Esto se debe a que obviamente cada perro es al menos tan duro como él mismo. Ahora cada vez que dos perros\(x\) y se\(y\) encuentran entre sí, establecen dominio a través del contacto visual o intimidación física, y luego se agrega a la relación uno de los siguientes pares ordenados: cualquiera\((x,y)\) o\((y,x)\), pero nunca ambos .

Sostengo que en este ejemplo de juguete, “IsAtleastastoughas” es un orden parcial, y\(D\) junto con IsAtleastastoughas juntos forman un poset. Razono de la siguiente manera. Es reflexivo, ya que empezamos sumando cada perro consigo mismo. Es antisimétrico, ya que nunca agregamos ambos\((x,y)\) y\((y,x)\) a la relación. Y es transitivo, porque si Rex es más duro que Fido, y Fido es más duro que Cuddles, esto significa que si Rex y Cuddles alguna vez se conocían, Rex establecería rápidamente el dominio. (No soy zoólogo, y no estoy seguro de si la última condición realmente se aplica con perros reales. Pero pretendamos que sí.)

Se le llama “orden parcial” porque establece una jerarquía parcial, pero incompleta, entre los perros. Si preguntamos, “¿el perro X es más duro que el perro Y?” la respuesta nunca es ambigua. Nunca vamos a decir: “bueno, el perro X era superior al perro A, que era superior al perro Y... pero de nuevo, el perro Y era superior al perro B, que era superior al perro X, así que no se sabe cuál de X e Y es realmente más duro”. No. Un orden parcial, por su transitividad y antisimetría, garantiza que nunca tengamos un conflicto tan irreconciliable.

No obstante, podríamos tener una falta de información. Supongamos que Rex nunca ha conocido a Killer, y nadie que Rex haya conocido jamás ha conocido a alguien que Killer No hay cadena entre ellos. Están en dos universos separados en lo que a nosotros respecta, y no tendríamos forma de saber cuál era el más duro. No tiene que ser tan extremo, aunque: Supongamos que Rex estableció dominio sobre Cuddles, y Killer también estableció dominio sobre Cuddles, pero esos son los únicos pares ordenados en la relación. Nuevamente, no hay forma de saber si Rex o Killer es el perro más duro. O necesitarían encontrarse con un oponente común al que solo uno de ellos pueda vencer, o bien reunirse para un throw-down.

Entonces un orden parcial nos da cierta apariencia de estructura —la relación establece una direccionalidad, y se nos garantiza que no nos envolvamos en contradicciones— pero no ordena completamente todos los elementos. Si lo hace, se llama orden total.

---

1. Espera, ¿cómo puedo decir eso? ¿Cómo puede haber” el par ordenado correspondiente” en una relación que no tiene pares ordenados?! La respuesta tiene que ver con la primera cláusula: por cada par ordenado (x, y) en ella. No hay ninguno de estos, por lo tanto, no se requieren (y, x)'s. La condición es trivialmente satisfecha. Esto es común en las matemáticas: decimos que A requiere B, pero esto significa que si A no es cierto, entonces B no es forzado.