Introducción
La sensación que quizás te quedó tras discutir las relaciones de equivalencia es que una relación de equivalencia establece cuándo elementos de un conjunto son «iguales» o «similares». Ahora introduciremos otros tipos de relaciones que nos harán pensar cuándo para dos elementos de un conjunto uno es «mayor» o «mejor» que otro bajo cierto criterio de comparación.
Antisimetría y orden parcial
Definición. Sea $R$ una relación sobre un conjunto $A$. Decimos que $R$ es una relación antisimétrica si y sólo si para cualesquiera $a,b\in A$ tales que $(a,b)\in R$ y $(b,a)\in R$ se tiene que $a=b$.
Veamos algunos ejemplos.
Ejemplo.
Sea $A$ un conjunto y sea $R$ la relación en $A$ definida como:
$aRb\ \text{si y sólo si} \ a\subseteq b$.
Veamos que $R$ es antisimétrica. En efecto, sean $a, b\in A$ tales que $(a,b)\in R$ y $(b,a)\in R$, entonces por definición de $R$ tenemos que $a\subseteq b$ y $b\subseteq a$. Por lo tanto, $a=b$.
$\square$
Ejemplo.
Sea $A$ un conjunto. Tenemos que $Id_A$ es una relación antisimétrica pues, si $(a,b)\in Id_A$ y $(b,a)\in Id_A$, entonces, $a=b$ por definición de $Id_A$.
$\square$
Para la siguiente definición es necesario recordar el concepto de relación reflexiva y transitiva que puedes encontrar en el la entrada de relaciones de equivalencia.
Definición. Sea $R$ una relación en $A$. Si $R$ es una relación reflexiva, antisimétrica y transitiva, entonces decimos que $R$ es un orden parcial en $A$. Para abreviar, diremos que $(A, R)$ es un orden parcial.
Ejemplo.
Si $A=\emptyset$, entonces la relación $\emptyset$ es un orden parcial en $A$. En efecto, se cumplen las tres propiedades que necesitamos:
- Como no hay $a\in A$, entonces $a\in A$ implica $(a,a)\in \emptyset$ por vacuidad. Por lo tanto, $\emptyset$ es una relación reflexiva.
- Como no hay elementos en $\emptyset$, entonces por vacuidad si $(a,b)\in \emptyset$ y $(b,a)\in \emptyset$, entonces $a=b$. Por lo tanto, $\emptyset$ es una relación antisimétrica.
- Como no hay elementos en $\emptyset$, entonces por vacuidad si $a,b,c\in A$ tales que $(a,b)\in \emptyset$ y $(b,c)\in \emptyset$, entonces $(a,c)\in \emptyset$. Por lo tanto, $\emptyset$ es una relación transitiva.
$\square$
Ejemplo.
Si $A$ es un conjunto y $R$ es la relación en $A$ definida como sigue:
$aRb\ \text{si y sólo si} \ a\subseteq b$,
entonces $R$ es un orden parcial. En efecto, se cumplen las tres propiedades que necesitamos:
- Sea $a\in A$, entonces $(a, a)\in R$ pues $a\subseteq a$ para cualquier conjunto $a$. Por lo tanto, $R$ es una relación reflexiva.
- Sean $a,b\in A$ tales que $(a,b)\in R$ y $(b,a)\in R$. Ya probamos que esto implica $a=b$. Por lo tanto, $R$ es una relación antisimétrica.
- Sean $a,b,c\in A$ tales que $(a,b)\in R$ y $(b,c)\in R$, entonces $a\subseteq b$ y $b\subseteq c$ respectivamente. Luego, $a\subseteq b$ y $b\subseteq c$ implican que $a\subseteq c$. Por lo tanto, $(a,c)\in R$ y así, $R$ es una relación transitiva.
Por lo tanto, $R$ es un orden parcial.
$\square$
Cuando una relación $R$ es un orden parcial, entonces la expresión $aRb$ se comporta como el símbolo $\leq$. Por ello, usualmente nos referiremos a los órdenes parciales usando este símbolo e intuitivamente pensaremos que una relación parcial nos permite decir cuando un elemento es menor o igual que otro.
Orden estricto
Si los órdenes parciales «se comportan como $\leq$», ¿qué tipo de relaciones «se comportan como $\lt$? Esto es lo que discutiremos a continuación. Primero necesitamos introducir dos nociones.
Definición. Sea $R$ una relación sobre un conjunto $A$. Decimos que $R$ es una relación asimétrica si y sólo si para cualesquiera $a,b\in A$ tales que $(a,b)\in R$ entonces no es cierto que $(b,a)\in R$.
Ejemplo.
Sean $A=\set{1,2,3}$ y $R=\set{(1,2), (1,3)}$. Se tiene que $R$ es una relación asimétrica. En efecto, $(1,2)\in R$ pero $(2,1)\notin R$ y $(1,3)\in R$ pero $(3,1)\notin R$.
$\square$
Definición. Sea $R$ una relación sobre un conjunto $A$. Decimos que $R$ es una relación irreflexiva si y sólo si para cualquier $a\in A$ se tiene que $(a,a)\notin R$.
Ejemplo.
Sean $A=\set{1,2,3}$ y $R=\set{(1,2), (1,3)}$. Se tiene que $R$ es una relación irreflexiva. En efecto, pues para cualquier elemento en $A$ en este caso $1, 2$ y $3$ se cumple que $(1,1)\notin R$, $(2,2)\notin R$ y $(3,3)\notin R$.
$\square$
Del ejemplo anterior podemos inferir que si $R$ es una relación asimétrica, entonces $R$ es irreflexiva. Vamos a demostrar esto último en la siguiente proposición.
Proposición. Sea $A$ un conjunto y $R$ una relación en $A$. Si $R$ es asimétrica, entonces $R$ es irreflexiva.
Demostración.
Vamos a probar que si $R$ no es irreflexiva, entonces no es asimétrica. Si $a\in A$ cumple que $(a,a)\in A$, entonces no es posible tener simultáneamente $(a,a)\in A$ y $(a,a)\notin A$, es decir, $R$ no es asimétrica.
$\square$
Definición. Sea $R$ una relación en $A$. Si $R$ es una relación asimétrica y transitiva decimos que $R$ es un orden estricto en $A$. Para abreviar, diremos $(A, R)$ es un orden estricto.
Ejemplo.
Sea $A$ un conjunto cualquiera (no necesariamente vacío). Veamos que la relación $\emptyset$ es un orden estricto.
Si $A=\emptyset$, se cumple por vacuidad que $\emptyset$ es una relación asimétrica y transitiva. Por lo tanto, $\emptyset$ es un orden estricto.
Supongamos ahora que $A\not=\emptyset$, verifiquemos las propiedades de asimetría y transitividad.
- Sean $a,b\in A$ tales que $(a,b)\in \emptyset$ entonces $(b,a)\notin \emptyset$ se satisface por vacuidad. Por lo tanto, $\emptyset$ es una relación asimétrica.
- Sean $a,b,c\in A$ tales que $(a,b)\in \emptyset$ y $(b,c)\in \emptyset$. Como esto nunca sucede, por vacuidad implica que $(a,c)\in \emptyset$. Por lo tanto, $\emptyset$ es una relación transitiva.
$\square$
Dado que estamos ordenando elementos de un conjunto, usualmente usaremos $<$ para denotar a una relación de orden estricto, ya que esta es irreflexiva.
Tarea moral
La siguiente lista de ejercicios te permitirá fortalecer tu entendimiento del tema de ordenes parciales y el de órdenes parciales estrictos.
- Si $A \not=\emptyset$, prueba que la pareja $(A,\emptyset)$ no es un orden parcial.
- Demuestra que si $A$ es un conjunto y $R$ es la relación $\subset$ en $A$, entonces $(A, R)$ es un orden parcial estricto.
- Argumenta por qué el concepto de no reflexividad es distinto al de irreflexividad. Además, encuentra un ejemplo de una relación que no sea ni reflexiva ni irreflexiva.
- Para cada una de las siguientes proposiciones, demuéstrala o da un contraejemplo.
- Si $R$ es una relación asimétrica, entonces es antisimétrica.
- Si $R$ es una relación antisimétrica, entonces es asimétrica.
- Sea $<$ un orden parcial estricto en un conjunto $A$. Muestra que $<\cup \{(a,a): a\in A\}$ es un orden parcial en $A$.
Más adelante…
En la siguiente entrada estudiaremos a los órdenes totales. Para hablar de tales órdenes retomaremos a los órdenes parciales y a los órdenes parciales estrictos. Además platicaremos del orden lexicográfico horizontal y vertical, los cuales se definen en el producto cartesiano de dos conjuntos ordenados.
Entradas relacionadas
- Entrada relacionada: Álgebra Superior I: Órdenes parciales y totales
- Ir a Teoría de los Conjuntos I
- Entrada anterior: Teoría de los Conjuntos I: Conjunto cociente
- Siguiente entrada: Teoría de los Conjuntos I: Orden total
Agradecimientos
Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»