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=\set{1,2,3,4}$ y sea $R$ la relación definida como:
$R=\set{(1,1), (2,2), (3,3), (4,4)}$.
Tenemos que $R$ es una relación antisimétrica pues en este ejemplo cada elemento de $A$ se relaciona consigo mismo solamente.
$\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 $(A, R)$ es un conjunto parcialmente ordenado. A $R$ le llamamos un orden parcial en $A$.
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 antisimétrica.
$\square$
Ejemplo.
Sea $A$ es 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 parcial 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.
Sea $A=\set{1,2,3}$ y sea $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.
Sea $A=\set{1,2,3}$ y sea $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.
Supongamos que $R$ es una relación asimétrica, es decir, para cualesquiera $a,b\in A$ tales que $(a,b)\in R$ entonces $(b,a)\notin R$. Luego, sea $a\in A$ arbitrario. Veamos que $(a,a)\notin R$. Supongamos por el contrario que $(a,a)\in R$ en busca de una contradicción. De aquí se tiene que existe $a\in A$ tal que $(a,a)\in R$ y $(a,a)\in R$ lo que contradice la asimetría de $R$. Por lo tanto, $(a,a)\notin R$ y así $R$ es irreflexiva.
$\square$
Definición. Sea $R$ una relación en $A$. Si $R$ es una relación asimétrica y transitiva decimos que $(A, R)$ es un conjunto estrictamente ordenado. Además, decimos que $R$ es un orden parcial en $A$.
Ejemplo.
Sea $A$ un conjunto cualquiera (no necesariamente vacío). Veamos que la relación $\emptyset$ es un orden parcial 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 parcial 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 parcial estricto, pues esta relación nos permite pensar de manera intuitiva cuando un elemento es menor estricto que otro.
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 porqué 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
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»