Archivo de la etiqueta: órdenes

Teoría de los Conjuntos: Órdenes parciales y órdenes estrictos

Por Gabriela Hernández Aguilar

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:

  1. 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.
  2. 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.
  3. 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:

  1. 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.
  2. 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.
  3. 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.

  1. 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.
  2. 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.

  1. Si $A \not=\emptyset$, prueba que la pareja $(A,\emptyset)$ no es un orden parcial.
  2. Demuestra que si $A$ es un conjunto y $R$ es la relación $\subset$ en $A$, entonces $(A, R)$ es un orden parcial estricto.
  3. 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.
  4. 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.
  5. 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

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»