Introducción
En esta sección hablaremos de relaciones, sin embargo a partir de este momento le otorgaremos un orden a sus elementos. En esta sección comenzaremos definiendo a los órdenes parciales y a los órdenes parciales estrictos.
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$ implica que $a=b$.
Ejemplo:
Sea $A$ un conjunto y sea $R$ una relación 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}$ un conjunto y sea $R$ una 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 y sabemos que $1=1$, $2=2$, $3=3$ y $4=4$.
$\square$
Para la siguiente definición es necesario recordar el concepto de relación reflexiva y transitiva que puedes encontrar en el siguiente enlace: Teoría de los Conjuntos I: Relaciones de equivalencias.
Definición: Sea $R$ una relación en $A$, si $R$ es una relación reflexiva, antisimétrica y transitiva decimos que $(A, R)$ es un conjunto parcialmente ordenado.
Ejemplo:
Si $A=\emptyset$, entonces la relación $\emptyset$ es un orden parcial.
- Sea $a\in A$, entonces $(a, a)\in \emptyset$ se cumple por vacuidad. Por lo tanto, $\emptyset$ es una relación reflexiva.
- Sean $a,b\in A$ tales que $(a,b)\in \emptyset$ y $(b,a)\in \emptyset$, entonces $a=b$. Por lo tanto, $\emptyset$ es una relación antisimétrica.
- Sean $a,b,c\in A$ tales que $(a,b)\in \emptyset$ y $(b,a)\in \emptyset$, entonces $a=b$. Por lo tanto, $\emptyset$ es una relación antisimétrica.
$\square$
Ejemplo:
Si $A$ un conjunto y sea $R$ una relación en $A$ definida como sigue:
$aRb\ \text{si y sólo si} \ a\subseteq b$,
entonces la relación $R$ es un orden parcial.
- 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 $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,a)\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$
Dado que estamos ordenando elementos de un conjunto, usualmente usaremos $\leq$ para denotar a la relación de orden parcial, pues esta relación nos permite decir cuando un elemento es menor o igual que otro.
Orden parcial estricto
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}$ un conjunto y sea $R=\set{(1,2), (1,3)}$ 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}$ un conjunto y sea $R=\set{(1,2), (1,3)}$ 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.
Ejemplo:
Sea $A$ un conjunto cualquiera, 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,a)\in \emptyset$, entonces $a=b$. Por lo tanto, $\emptyset$ es una relación antisimétrica.
$\square$
Dado que estamos ordenando elementos de un conjunto, usualmente usaremos $<$ para denotar a la relación de orden parcial estricto, pues esta relación nos permite decir cuando un elemento es menor estricto que otro.
Tarea moral
La siguiente lista de ejercicios fortalecera el 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.
Más adelante
En la siguiente sección estudiaremos a los órdenes totales, para hablar de tales órdenes retomaremos a los órdenes parciales y órdenes parciales estrictos. Además veremos el orden lexicográfico horizontal y vertical, tales ordenes se definen en el producto cartesiano de dos conjuntos ordenados.
Enlaces
En la siguiente entrada podrás encontrar más contenido acerca de órdenes parciales: