Archivo del Autor: Gabriela Hernández Aguilar

Teoría de los Conjuntos I: Orden total

Introducción

En esta sección hablaremos acerca de ordenes totales, retomaremos el concepto de orden parcial y orden parcial estricto y añadiremos el concepto de ser comparable. Además hablaremos acerca del orden lexicográfico vertical y horizontal.

Concepto

Definición: Sea $\leq$($<$) una relación de orden en $A$ y sean $a, b\in A$. Decimos que $a$ y $b$ son $\leq$-comparables($<$-comparables) en el orden $\leq$ ($<$) si:

$a\leq b$ o $b\leq a$
($a<b$, o $a=b$, o $b<a$).

Ejemplo:

Sea $A=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $\subseteq_A$ la relación dada por el conjunto

$\subseteq_A=\set{(\emptyset, \emptyset), (\emptyset, \set{\emptyset}), (\emptyset, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset},\set{\emptyset}), (\set{\emptyset}, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset, \set{\emptyset}}, \set{\emptyset, \set{\emptyset}})}$

una relación de orden parcial.

Luego, dados $a,b\in A$ podemos decidir si $a\subseteq b$ o $b\subseteq a$. En efecto,

  • Si $a=\emptyset$ y $b=\emptyset$, entonces $a\subseteq_A b$ y $b\subseteq_A a$.
  • Si $a=\set{\emptyset}$ y $b=\set{\emptyset}$, entonces $a\subseteq_A b$ y $b\subseteq_A a$.
  • Si $a= \set{\emptyset, \set{\emptyset}}$ y $b=\set{\emptyset,\set{\emptyset}}$, entonces $a\subseteq_R b$ y $b\subseteq_R a$.
  • Si $a=\emptyset$ y $b=\set{\emptyset}$, entonces $a\subseteq_R b$.
  • Si $a=\emptyset$ y $b=\set{\emptyset, \set{\emptyset}}$, entonces $a\subseteq_A b$.
  • Si $a=\set{\emptyset}$ y $b=\set{\emptyset, \set{\emptyset}}$, entonces $a\subseteq_A b$.

$\square$

Ejemplo:

Sea $A=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $R$ la relación dada por el conjunto $R=\set{(\emptyset, \set{\emptyset}), (\emptyset, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset}, \set{\emptyset, \set{\emptyset}})}$ una relación de orden parcial estricto.

Notemos que $aRb$ si y sólo si $a\in b$ para $a,b\in A$. Luego, dados $a,b\in A$ podemos decidir si $a\in b$, $a=b$ o $b\in a$. En efecto,

  • Si $a=\emptyset$ y $b=\emptyset$, entonces $a=b$,
  • Si $a=\set{\emptyset}$ y $b=\set{\emptyset}$, entonces $a=b$,
  • Si $a= \set{\emptyset, \set{\emptyset}}$ y $b=\set{\emptyset,\set{\emptyset}}$, entonces $a=b$,
  • Si $a=\emptyset$ y $b=\set{\emptyset}$, entonces $a\in b$ y así, $aRb$,
  • Si $a=\emptyset$ y $b=\set{\emptyset, \set{\emptyset}}$, entonces $a\in b$ y así, $aRb$,
  • Si $a=\set{\emptyset}$ y $b=\set{\emptyset, \set{\emptyset}}$, entonces $a\in b$ y así, $aRb$,

$\square$

Definición: Sea $A$ un conjunto y sea $\leq$ ($<$) orden parcial (estricto) en $A$. Si para cualesquiera $a, b\in A$ son $\leq(<)$-comparables, entonces $\leq(<)$ es un orden total.

Ejemplo:

Sea $A=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $R$ la relación dada por el conjunto

$R=\set{(\emptyset, \emptyset), (\emptyset, \set{\emptyset}), (\emptyset, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset},\set{\emptyset}), (\set{\emptyset}, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset, \set{\emptyset}}, \set{\emptyset, \set{\emptyset}})}.$

Ya vimos en la parte de arriba que todos los elementos de $A$ son $\leq$-comparables y por lo tanto, $R$ es un orden total.

$\square$

Ejemplo:

Sea $A=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ y sea $R$ la relación dada por el conjunto

$R=\set{(\emptyset, \set{\emptyset}), (\emptyset, \set{\emptyset, \set{\emptyset}}), (\set{\emptyset}, \set{\emptyset, \set{\emptyset}})}$.

Ya vimos que todos los elementos de $A$ son $<$-comparables y por lo tanto, $R$ es un orden total.

$\square$

Orden lexicográfico vertical

Ahora, vamos a dar un orden al producto cartesiano de dos conjuntos ordenados. Para ello conviene hacer mención de lo siguiente: si $(A,\leq_A)$ es un conjunto parcialmente ordenado y tenemos dos elementos $a,b\in A$ tales que $a\leq_Ab$ pero $a\not=b$, entonces escribiremos simplemente $a<_Ab$. De esta manera, en un conjunto parcialmente ordenado $(A,\leq_A)$, si $a,b\in A$, el símbolo $a<_Ab$ significará $a\leq_Ab$ y $a\not=b$.

Definición: Sean $(A, \leq_A)$ y $(B, \leq_B)$ conjuntos totalmente ordenados. Definimos al orden lexicográfico vertical en $A\times B$ como sigue:

$(a,b)\ll_v (a’, b’)$ si y sólo si ($a<_A a’$) o ($a=a’$ y $b\leq_B b’$).

Proposición: El orden lexicográfico vertical es un orden total.

Demostración:

  • Reflexividad:
    Sea $(a,b)\in A\times B$. Dado que $b\in B$ y $\leq_B$ es un orden parcial en $B$, entonces $\leq_B$ es una relación reflexiva y así $b\leq_B b$. En consecuencia, la conjunción $a=a$ y $b\leq_B b$ es verdadera, y por tanto $(a,b)\ll_v (a,b)$. De esta manera, $\ll_v$ es reflexivo.
  • Antisimetría:
    Sean $(a,b), (c,d)\in A\times B$ tales que $(a,b)\ll_v (c,d)$ y $(c,d)\ll_v (a,b)$. Veamos que $(a,b)=(c,d)$, es decir, $a=c$ y $b=d$.
    Como $(a,b)\ll_v (c,d)$ entonces, ($a<_A c$) o ($a=c$ y $b\leq_B d$).
    Como $(c,d)\ll_v (a,b)$ entonces, ($c<_A a$) o ($c=a$ y $d\leq_B b$).
    Luego, tiene que ocurrir que $a=c$ y $b\leq_Bd$. Para probarlo supongamos que esto no ocurre buscando generar una contradicción. Dado que la conjunción $a=c$ y $b\leq_Bd$ no es verdadera, pues estamos suponiendo que no ocurre, entonces, necesariamente debe ser cierto que $a<_Ac$. Ahora, no puede ocurrir que $c<_Aa$, pues de ser así tendríamos que $c<_Aa$ y $a<_Ac$ son verdaderas al mismo tiempo, y por ende se tendría que $c\leq_A a$ pero $c\not=a$ y que $a\leq_Ac$ pero $a\not=c$. Así, en particular obtenemos que $c\leq_Aa$ y $a\leq_Ac$, pero esto implica que $a=c$ pues $\leq_A$ es una relación antisimétrica. Este último hecho contradice que $a\not=c$. Por tanto, no puede ocurrir que $c<_Aa$. Como consecuencia debe ser cierto que $c=a$ y $d\leq_Bb$, pero esto nuevamente contradice el hecho de que $a<_Ac$, es decir, que $a\leq_Ac$ y $a\not=c$. Como la contradicción viene de suponer que $a<_Ac$, entonces, debe ser cierto que $a=c$ y $b\leq_Bd$. Ya tenemos entonces que $a=c$ por lo que resta ver que $b=d$. Como $a=c$ entonces no puede ocurrir que $c<_Aa$ y, por tanto, debe ocurrir que $c=a$ y $d\leq_Bb$ es verdadero. De esta manera tenemos que $b\leq_Bd$ y $d\leq_Bb$, de donde $d=b$ pues $\leq_B$ es una relación antisimétrica.
    Por lo tanto, $(a,b)=(c,d)$ lo que demuestra que $\ll_v$ es una relación antisimétrica.
  • Transitividad:
    Sean $(a,b), (c,d), (e,f)\in A\times B$ tales que $(a,b)\ll_v (c,d)$ y $(c,d)\ll_v (e,f)$. Veamos que $(a,b)\ll_v(e,f)$.
    Como $(a,b)\ll_v (c,d)$ entonces, ($a<_A c$) o ($a=c$ y $b\leq_B d$).
    Como $(c,d)\ll_v (e,f)$ entonces, ($c<_A e$) o ($c=e$ y $d\leq_B f$).
    Caso 1: Si $a<_Ac$ y $c<_A e$. Por transitividad de $<_A$ se tiene que $a<_A e$. Por lo tanto, ($a<_A e$) o ($a=e$ y $b\leq_B f$) es verdadero y así, $(a,b)\ll_v (e,f)$.
    Caso 2: Si $a<_Ac$ y $c=e$ y $d\leq_B f$, entonces $a<_A e=c$. Por lo tanto, ($a<_A e$) o ($a=e$ y $b\leq_B f$) es verdadero y así, $(a,b)\ll_v (e,f)$.
    Caso 3: Si $a=c$ y $b\leq_B d$ y $c<_A e$, entonces $a=c<_A e$. Por lo tanto, ($a<_A e$) o ($a=e$ y $b\leq_B f$) es verdadero y así, $(a,b)\ll_v (e,f)$.
    Caso 4: Si $a=c$ y $b\leq_B d$ y $c= e$ y $d\leq_B f$, entonces $a=e$ y $b\leq_B f$ por transitividad de $\leq_B$. Por lo tanto, ($a<_A e$) o ($a=e$ y $a\leq_B e$) es verdadero y así, $(a,b)\ll_v (e,f)$.
    Por lo tanto, $\ll_v$ es transitivo.
    Por lo tanto, $\ll_v$ es un orden parcial en $A\times B$.

Para ver que $\ll_v$ es un orden total en $A\times B$ debemos ver que todos sus elementos son $\ll_v$ comparables.

Sean $(a,b), (c,d)\in A\times B$, veamos que $(a,b)\ll_v (c,d)$ o $(c,d)\ll_v(a,b)$.

Dado que $(a,b), (c,d)\in A\times B$, entonces $a,c\in A$ y $b,d\in B$. Luego, como $\leq_A$ y $\leq_B$ son órdenes totales en $A$ y $B$ respectivamente, tenemos que sus elementos son comparables, es decir, ($a\leq_A c$ o $c\leq_A a$) y ($b\leq_B d$ o $d\leq_B b$).

Caso 1: Si $a\leq_A c$ y $b\leq_B d$, hay dos posibles casos. Si $a<_A c$ y $b\leq_B d$ se tiene que $(a,b)\ll_v (c,d)$. Ahora, si $a=c$ y $b\leq_B d$ entonces $(a,b)\ll_v (c,d)$.

Caso 2: Si $a\leq_A c$ y $d\leq_B b$, hay dos posibles casos. Si $a<_A c$, entonces $(a,b)\ll_v (c,d)$. Ahora, si $a=c$ y $d\leq_B b$ entonces $(c,d)\ll_v (a,b)$.

Caso 3: Si $c\leq_A a$ y $b\leq_B d$, hay dos posibles casos. Si $c<_A a$, entonces $(c,d)\ll_v (a,b)$. Ahora, si $a=c$ y $b\leq_B b$ entonces $(a,b)\ll_v (c,d)$.

Caso 4: Si $c\leq_A a$ y $d\leq_B b$, hay dos posibles casos. Si $c<_A a$, entonces $(c,d)\ll_v(a,b)$. Ahora, si $c=a$ y $d\leq_B b$, entonces $(c,d)\ll_v (a,b)$.

$\square$

Orden lexicográfico horizontal

A continuación definiremos al orden lexicográfico horizontal, este orden también será un orden total. (Probar que $(A\times B, \ll_h)$ es un orden total será parte de tu tarea moral).

Definición: Sean $(A, \leq_A)$ y $(B, \leq_B)$ conjuntos totalmente ordenados. Definimos al orden lexicográfico horizontal en $A\times B$ como sigue:

$(a,b)\ll_h (a’, b’)$ si y sólo si ($b<_B b’$) o ($b=b’$ y $a\leq_A a’$).

Tarea moral

  • Demuestra que el orden lexicográfico horizontal es un orden total.
  • Consideremos $(\mathcal{P}(\set{\set{\emptyset}, \set{\emptyset, \set{\emptyset}}, \set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}}, \subseteq)$. Da dos elementos que no sean comparables.
  • Si consideramos $(A, \leq_A)$ y $(B, \leq_B)$ conjuntos parcialmente ordenados y definimos la relación producto en $A\times B$ como:
    $(a,b)\ll_{A\times B} (c,d)$ si y sólo si $a\leq_A c$ y $b\leq_B d$.
    Demuestra que $\ll_{A\times B}$ no es un orden total.

Más adelante

En la siguiente sección hablaremos acerca de elementos mínimos y máximos en un conjunto ordenado. Además hablaremos acerca de cotas superiores e inferiores. Así como de otros conceptos que nos permitan acotar a un conjunto.

Enlaces

Aquí puedes consultar más contenido acerca de órdenes totales:

Álgebra Superior I: Órdenes parciales y totales

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

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.

  1. Sea $a\in A$, entonces $(a, a)\in \emptyset$ se cumple por vacuidad. Por lo tanto, $\emptyset$ es una relación reflexiva.
  2. 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.
  3. 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.

  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 $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,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.

  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,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:

Álgebra Superior I: Órdenes parciales y totales

Teoría de los Conjuntos I: Conjunto cociente

Introducción

En esta entrada definiremos al conjunto cociente, dicho conjunto tendrá como elementos a las clases de equivalencia de una relación. Además probaremos que toda relación de equivalencia induce una partición y viceversa.

Concepto

Definición: Sea $R$ una relación de equivalencia en $A$, definimos al conjunto cociente por la relación $R$ como el conjunto:

$R\diagup A=\set{[a]_R: a\in A}$.

Ejemplo:

Sea $A=\set{1,2,3,4}$ y $R$ la relación identidad en $A$. Sabemos que $R$ es de equivalencia en $A$. Luego, siguiendo la definición de conjunto cociente tenemos que $R\diagup A=\set{[1]_R, [2]_R, [3]_R, [4]_R}$, donde $[1]_R=\set{1}$, $[2]_R=\set{2}$, $[3]_R=\set{3}$, $[4]_R=\set{4}$.

$\square$

Ejemplo:

Sea $A=\set{1,2,3,4}$ y $R=\set{(1,1), (2,2), (3,3), (4,4), (1,4), (4,1)}$ una relación de equivalencia en $A$. Luego, tenemos que

$R\diagup A=\set{[1]_R, [2]_R, [3]_R, [4]_R}$,

donde

  • $[1]_R=\set{1,4}$,
  • $[2]_R=\set{2}$,
  • $[3]_R=\set{3}$,
  • $[4]_R=\set{4,1}$.

Por lo tanto, $R\diagup A=\set{[1]_R, [2]_R, [3]_R}$

$\square$

Cada relación de equivalencia induce una partición

Teorema: Sea $R$ una relación de equivalencia en $A$, entonces el conjunto cociente $A\diagup R$ es una partición de $A$.

Demostración:

Supongamos que $R$ es una relación de equivalencia en $A$. Veamos que $A\diagup R$ es una partición de $A$.

  1. Sea $a\in A$, vimos en la entrada de particiones que $[a]_R\not=\emptyset$.
  2. Sean $[a]_R,[b]_R\in A\diagup R$ tales que $[a]_R\not=[b]_R$ y veamos que $[a]_R\cap [b]_R=\emptyset$. Supongamos que no ocurre que $[a]_R\cap [b]_R=\emptyset$, es decir, $[a]_R\cap [b]_R\not=\emptyset$ lo que es equivalente a que $[a]_R=[b]_R$
  3. Por último, $\bigcup_{a\in A} [a]_R= A$ pues para cada $a\in A$, $a\in [a]_R$.

$\square$

Este último teorema demuestra que toda relación de equivalencia induce una partición.

Las particiones inducen una relación de equivalencia

El teorema anterior nos permitió probar que cada relación de equivalencia induce una partición y de hecho, esta partición será el conjunto cociente, por lo que es válido preguntarnos si el resultado se cumple de regreso, es decir, dada una partición podemos inducir una relación de equivalencia. Veamos el siguiente ejemplo.

Ejemplo:

Sea $A=\set{0,1,2, 3, \cdots}$ y sean $A_1=\set{0,2,4,\cdots}$ y $A_2=\set{1,3, 5,\cdots}$. Resulta que $\mathcal{P}$ es una partición de $A$ pues tanto $A_1$ y $A_2$ son conjuntos no vacíos, además $A_1\cap A_2=\emptyset$ y $A_1\cup A_2=A$.

Queremos ver si existe la manera de relacionar a los elementos de $A$ tal que la relación que resulte sea de equivalencia. Consideremos la siguiente relación definida como sigue:

$R_\mathcal{P}=\set{(a,b)\in A^2: \exists A_i\in \mathcal{P}\ \text{tales que}\ a,b\in A_i}$.

Notemos que la relación $R_\mathcal{P}$ es una relación en $A$ y además relaciona a los elementos si pertenece a un mismo conjunto de la partición.

Veamos que $R_\mathcal{P}$ es una relación de equivalencia, para ello verifiquemos si es una relación reflexiva, simétrica y transitiva.

  1. Sea $a\in A$, si $a$ es un número par (existe $k$ tal que $a= 2k$), entonces $a\in A_1$ y por lo tanto, existe $A_1\in \mathcal{F}$ tal que $a\in A_1$ y así $(a,a)\in R_\mathcal{P}$.
    Si $a$ es un número impar (existe $k$ tal que $a= 2k+1$), entonces $a\in A_2$ y por lo tanto, existe $A_2\in \mathcal{P}$ tal que $a\in A_2$ y así $(a,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación reflexiva.
  2. Supongamos que $(a,b)\in R_\mathcal{P}$ y veamos que $(b,a)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ con $i\in \set{1,2}$ tal que $a, b\in A_i$. Lo que es equivalente a decir que existe $A_i\in \mathcal{P}$ con $i\in\set{1,2}$ tal que $b,a\in A_i$, es decir, $(b,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación simétrica.
  3. Supongamos que $(a,b)\in R_\mathcal{P}$ y $(b,c)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ con $i\in \set{1,2}$ tal que $a, b\in A_i$. Luego, como $(b,c)\in R_\mathcal{P}$ entonces existe $A_j\in \mathcal{P}$ con $j\in \set{1, 2}$ tal que $b,c\in A_j$. Luego $A_i=A_j$ pues de lo contrario $A_i\not= A_j$ y $b\in A_1$ al mismo tiempo que $b\in A_2$ y así, $b$ es par e impar, lo cuál no puede ocurrir. Por lo tanto, existe $A_i\in \mathcal{P}$ con $i\in \set{1,2}$ tal que $a,c\in A_i$ y así, $(a,c)\in R_\mathcal{P}$. Por lo tanto, $R_\mathcal{P}$ es una relación transitiva.

Por lo tanto, $R_\mathcal{P}$ es una relación de equivalencia.

$\square$

Podemos demostrar que esto ocurre para cualquier conjunto y cualquier partición. Veamos el siguiente teorema.

Teorema: Toda partición induce una relación de equivalencia.

Demostración:

Sea $A$ un conjunto y $\mathcal{P}=\set{A_i:i\in I}$ una partición de $A$. Defimos a $R_\mathcal{E}$ como el siguiente conjunto:

$R_\mathcal{P}=\set{(a,b)\in A\times A: \exists A_i\in \mathcal{P}\ \text{tal que}\ a,b\in A_i}$.

Notemos que $R_\mathcal{P}$ es una relación en $A$ pues es un subconjunto de $A\times A$. Veamos que $R$ es de equivalencia, es decir, $R$ es reflexiva, simétrica y transitiva.

  1. Sea $a\in A$, dado que $\mathcal{P}$ es una partición de $A$, entonces $A=\bigcup_{i\in I}A_i$. Entonces existe $j\in I$ tal que $a\in A_j$, de donde $(a,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación reflexiva.
  2. Supongamos que $(a,b)\in R_\mathcal{P}$ y veamos que $(b,a)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ tal que $a, b\in A_i$. Lo que es equivalente a decir que existe $A_i\in \mathcal{P}$ tal que $b,a\in A_i$, es decir, $(b,a)\in R_\mathcal{P}$.
    Por lo tanto, $R_\mathcal{P}$ es una relación simétrica.
  3. Supongamos que $(a,b)\in R_\mathcal{P}$ y $(b,c)\in R_\mathcal{P}$.
    Como $(a,b)\in R_\mathcal{P}$ entonces existe $A_i\in \mathcal{P}$ tal que $a, b\in A_i$. Luego, como $(b,c)\in R_\mathcal{P}$ entonces existe $A_j\in \mathcal{P}$ tal que $b,c\in A_j$. Además $A_i=A_j$ pues de lo contrario, $A_i\not= A_j$ y $b\in A_i$ al mismo tiempo que $b\in A_j$ y así, $b\in A_i\cap A_j=\emptyset$ lo cual es una contradicción. Por lo tanto, existe $A_i\in \mathcal{P}$ tal que $a,c\in A_i$ y así, $(a,c)\in R_\mathcal{P}$. Por lo tanto, $R_\mathcal{P}$ es una relación transitiva.

Por lo tanto, $R_\mathcal{P}$ es una relación de equivalencia en $A$.

$\square$

Con este último teorema hemos probado que en efecto, así como cada relación de equivalencia induce una partición, se cumple que cada partición induce una relación de equivalencia.

Tarea moral

La siguiente lista de ejercicios te ayudará a reforzar el contenido de esta entrada:

  • Demuestra que si $A$ es un conjunto y $R$ es una relación de equivalencia en $A$, entonces $A\diagup R$ es un conjunto.
  • Sea $A=\set{1,2,3,4,5,6}$ y $R=\set{(1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (5,6), (6,5), (4,6), (6,4), (4,5), (5,4)}$ relación de equivalencia en $A$. Determina al conjunto cociente de $A$ respecto de $R$.

Más adelante

En la siguiente sección continuaremos con algunos teoremas del conjunto cociente, dichos teoremas involucraran funciones.

Enlaces

Más sobre relaciones de equivalencia y clases de equivalencia:

Álgebra Superior I: Relaciones de equivalencia y clases de equivalencia

Teoría de los Conjuntos I: Funciones inversas

Introducción

En esta sección retomaremos los conceptos de función inyectiva y sobreyectiva, así como el de función biyectiva, hablaremos acerca de las funciones inversas, para ello introduciremos conceptos como el de inversa derecha y el de inversa izquierda.

Inversa izquierda

Definición: Sea $f:X\to Y$ una función. Si $g:Y\to X$ es una función tal que $g\circ f=Id_X$, entonces decimos que $g$ es inversa izquierda de $f$.

Ejemplo:

Sea $X=\set{1,2}$ y $Y=\set{1,2,3}$ conjuntos. Sea $f:X\to Y$ una función dada por el conjunto $f=\set{(1,1), (2,2)}$.

Luego, $g:Y\to X$ definida como $g=\set{(1,1), (2,2), (3,2)}$ es inversa izquierda de $f$. En efecto, tenemos que $g\circ f=Id_X$ pues:

$g\circ f(1)= g(f(1))= g(1)=1= Id_X(1)$
$g\circ f(2)= g(f(2))= g(2)=2= Id_X(2)$

Por lo tanto, $g\circ f=Id_X$ y así $g$ es inversa izquierda de $f$.

$\square$

Teorema: Sea $f:X\to Y$ una función, decimos que $f$ es inyectiva si y sólo tiene $f$ tiene inversa izquierda.

Demostración:

Supongamos que $f$ es inyectiva, es decir, para cualesquiera $x,y\in X$ tales que $f(x)= f(y)$, implica que $x=y$. Vamos a demostrar que existe $g:Y\to X$ función tal que $g\circ f= Id_X$.

Dado que $f$ es una relación, entonces existe la relación inversa de $f$ a la que llamaremos $g$. Veamos que $g$ es función.

Sean $(a,b)\in g$ y $(a,c)\in g$, veamos que $b=c$ para demostrar que $g$ es función.

Luego, $(b,a)\in f$ y $(c,a)\in f$ así como $f$ es inyectiva y $f(b)=f(c)$, entonces $b=c$ y por lo tanto, $g$ es función. Además $g$ es inversa izquierda pues se verifica que $g\circ f=Id_X$. En efecto, sea $x\in X$, entonces $(x,f(x))\in f$ y así $(f(x), x)\in g$, por lo que:

$g\circ f(x)=g(f(x))= x=Id_X(x)$.

Por lo tanto, $g$ es inversa izquierda de $f$.

Ahora, supongamos que $f$ es una función invertible, es decir, existe $f^{-1}$ tal que $f\circ f^{-1}=Id= f^{-1}\circ f$.

Luego, sean $x_1, x_2$ tales que $f(x_1)=f(x_2)$. Veamos que $x_1=x_2$. Tenemos que $(f(x_1), x_1)\in f^{-1}$ y $(f(x_2), x_2)\in f^{-1}$, dado que $f(x_1)= f(x_2)$ y que $f^{-1}$ es función entonces $x_1=x_2$.

Por lo tanto, $f$ es inyectiva.

$\square$

Inversa derecha

Definición: Sea $f:X\to Y$ una función. Si $g:Y\to X$ es una función tal que $f\circ g=Id_Y$, entonces decimos que $g$ es inversa derecha de $f$.

Ejemplo:

Sea $X=\set{1,2,3}$ y $Y=\set{1,2}$ conjuntos. Sea $f:X\to Y$ una función dada por el conjunto $f=\set{(1,1), (2,2), (3,1)}$.

Luego, $f:Y\to X$ definida como $g=\set{(1,1), (2,2)}$ es inversa derecha de $f$. En efecto, tenemos que $f\circ g=Id_Y$ pues:

$f\circ g(1)= f(g(1))= f(1)=1= Id_X(1)$
$f\circ g(2)= f(g(2))= f(2)=2= Id_X(2)$

Por lo tanto, $f\circ g=Id_Y$ y así $g$ es inversa derecha de $f$.

$\square$

Del ejemplo anterior podrás notar que $f$ es sobreyectiva pero no inyectiva, va a resultar que si $f$ es invertible por la derecha entonces $f$ es sobreyectiva. Lo demostraremos en la siguiente proposición.

Proposición: Sea $f:X\to Y$ una función, $f$ es sobreyectiva si y sólo si $f$ tiene inversa derecha.

Demostración:

Supongamos que $f$ es sobreyectiva, es decir, para cualquier $y\in Y$, existe $x\in X$ tal que $f(x)=Y$. Veamos que $f$ tiene inversa derecha, es decir que existe $g:Y\to X$ tal que $f\circ g=Id_Y$.

Consideremos $g:Y\to X$ dada por $g(y)=x$ para toda $y\in Y$. Tenemos que $f\circ g(y)= f(g(y))= f(x)= y=Id_Y(y)$, por lo tanto $g$ es inversa derecha de $f$.

Ahora, supongamos que $f$ tiene inversa derecha, digamos $g$. Sea $y\in Y$, veamos que existe $x\in X$ tal que $f(x)=y$.
Dado que $g$ es inversa derecha de $f$, entonces $f\circ g=Id_Y$, por lo que para cualquier $y\in Y$, $f\circ g(y)= Id_Y(y)=y$, por lo que existe $x= g(y)\in X$ tal que $f(x)=f(g(y))=y$. Por lo tanto, $f$ es sobreyectiva.

$\square$

Inversa izquierda pero no derecha y viceversa

Podemos preguntarnos porqué hasta este momento tenemos dos conceptos diferentes de inversa y la respuesta es porque en ocasiones la inversa por la izquierda no será inversa por la derecha y viceversa. Además habrá veces en las que una función solo tenga inversa izquierda y no derecha, así como funciones que solo tengan inversa derecha pero no izquierda. Retomemos los ejemplos anteriores para ver esto último.

Ejemplo:

Sea $X=\set{1,2}$ y $Y=\set{1,2,3}$ conjuntos. Sea $f:X\to Y$ una función dada por el conjunto $f=\set{(1,1), (2,2)}$. Antes vimos que $g=\set{(1,1), (2,2), (3,2)}$ es inversa izquierda de $f$, sin embargo, $g$ no es inversa derecha pues $f\circ g= \set{(1,1), (2,2), (3, 2)}$ y $f\circ g\not= Id_Y$ pues $f\circ g(3)= 2\not= 3=Id_Y(3)$. Además $f$ no tiene inversa derecha pues $g$ debe enviar a $3$ a un elemento de $X$, en este caso las únicas posibilidades son $1$ o $2$. En cualquiera de los casos al componer a la función $g$ con $f$, la composición resulta ser distinta de la función identidad.

Ahora, sea $X=\set{1,2,3}$ y $Y=\set{1,2}$ conjuntos. Sea $f:X\to Y$ una función dada por el conjunto $f=\set{(1,1), (2,2), (3,1)}$. Vimos que $g=\set{(1,1), (2,2)}$ es inversa derecha de $f$. Sin embargo, $g$ no es inversa izquierda de $f$ pues $g\circ f=\set{(1,1), (2,2), (3,1)}$ y $g\circ f\not=Id_X$.

$\square$

Inversa de una función

Definición: Sea $f:X\to Y$ una función. Si $g:Y\to X$ es tal que $f\circ g= Id=g\circ g$ entonces decimos que $g$ es la inversa de $f$, y la denotamos como $f^{-1}$.

Notemos que la inversa de una función será tanto inversa izquierda y derecha, pero además dichas inversas serán iguales y es a la que llamaremos inversa de una función. Además para que exista la función inversa debe ocurrir que $f$ es una función biyectiva.

Ejemplo:

Sean $X=\set{\dots, -3, -2,-1, 0,1,2,3, \dots}$ y $f:X\to X$ una función dada por $f(x)=x+1$.

Busquemos la función inversa de $f$, para ello hagamos $f(x)=y$ y despejemos $x$ de $y=x+1$. Tenemos que $x=y-1$, por lo que $f^{-1}(x)=x-1$

Verifiquemos que en efecto $f^{-1}\circ f= Id= f\circ f^{-1}$. Tenemos que:

$f^{-1}\circ f(x)= f^{-1}(f(x))= f^{-1}(x+1)= (x+1)-1=x$,

$f\circ f^{-1}(x)= f(f^{-1}(x))= f(x-1)= (x-1)+1=x$.

Por lo tanto, $f^{-1}(x)= x-1$ es la función inversa de $f$.

$\square$

Teorema: Sea $f:X\to Y$, $f$, $f$ es biyectiva si y sólo si $f$ tiene inversa derecha e inversa izquierda.

Demostración:

Supongamos que $f$ es biyectiva, entonces $f$ es inyectiva y $f$ es sobreyectiva.

Como $f$ es inyectiva entonces $f$ tiene inversa izquierda y como $f$ es sobreyectiva entonces $f$ tiene inversa derecha.

Ahora, supongamos que $f$ tiene inversa derecha e inversa izquierda. Entonces $f$ es sobreyectiva e inyectiva respectivamente, por los teoremas que probamos anteriormente.

$\square$

Tarea moral

La siguiente lista de ejercicios te permitira identificar cuando una función tiene inversa ya sea izquierda o derecha

  • Da una función que tenga inversa derecha pero no izquierda.
  • Da una función que tenga inversa izquierda pero no derecha.
  • Da una función que tenga dos inversas derechas.
  • Da una función que tenga dos inversas izquierdas.
  • Sean $f:X\to Y$ y $g:Y\to Z$ funciones biyectivas. Demuestra que $g\circ f$ es invertible, más aún que $(g\circ f)^{-1}= f^{-1}\circ g^{-1}$.

Más adelante

En la siguiente sección comenzaremos con el tema de relaciones de equivalencia.

Teoría de los Conjuntos I: Funciones sobreyectivas y biyectivas

Introducción

En esta entrada hablaremos acerca de funciones sobreyectivas, este tipo de funciones serán aquellas cuya imagen sea todo el codominio. Tras definir este concepto podremos definir el concepto de función biyectiva, este último será de gran utilidad pues haremos uso de él cuando queramos estudiar conjunto a traves de otros conjuntos que tengan la misma cantidad de elementos.

Función sobreyectiva

Definición: Sea $f:X\to Y$ una función. Si $f[X]=Y$, entonces decimos que $f$ es sobreyectiva.

$\square$

Teorema: Sea $f:X\to Y$ una función. Entonces los siguientes enunciados son equivalentes:

  1. $f$ es sobreyectiva.
  2. Para cualquier $y\in Y$, existe $x\in X$ tal que $f(x)=y$.
  3. Para cualesquiera $h,k:Y\to Z$ tales que si $h\circ f= k\circ f$, entonces $h=k$.

Demostración:

$1)\rightarrow 2)$

Supongamos que $f$ es sobreyectiva, es decir que $f[X]=Y$. Sea $y\in Y$, entonces $y\in f[X]$ por lo que existe $x\in X$ tal que $f(x)=y$. Por lo tanto, para cualquier $y\in Y$ existe $x\in X$ tal que $f(x)=y$.

$2)\rightarrow 3)$

Sean $h,k:Y\to Z$ tales que $h\circ f=k\circ f$. Veamos que $h=k$. Sea $y\in Y$, veamos que $h(y)=k(y)$. Dado que $y\in Y$, por hipótesis tenemos que existe $x\in X$ tal que $f(x)=y$, por lo que $h(y)= h(f(x))$ y $k(y)= k(f(x))$. Luego, como $h\circ f(x)= h(f(x))= k(f(x))= k\circ f(x)$, tenemos que $h(y)= k(y)$.

$3)\rightarrow 1)$

Supongamos que $f$ no es sobreyectiva en busca de una contradicción. Sean $h: Y\to \set{\emptyset}$ y $k: Y\to \set{\emptyset, \set{\emptyset}}$ funciones dadas por $h(y)=\emptyset$ para todo $y\in Y$ y

\begin{align*}
k(y) = \left\{ \begin{array}{lcc}
\emptyset &  \text{si} & y\in f(X)\\
\set{\emptyset} &  \text{si}  & y \notin f(X) \\
\end{array}
\right.
\end{align*}

respectivamente. Notemos que $k\not=h$ pues dado que $f$ no es sobreyectiva, entonces existe $y_0\in Y$ tal que $y_0\notin f[X]$. Así, $h(y_0)= \emptyset$ y $k(y_0)=\set{\emptyset}$, por lo tanto, $h\not=k$.

Luego, $h\circ f= k\circ f$. Sea $x\in X$, entonces $f(x)\in Y$ y así, $h\circ f(x)= h(f(x))= \emptyset$ y $k\circ f(x)= k(f(x))= \emptyset$. Por lo tanto, debe ocurrir que $h=k$, lo cuál es una contradicción.

Así, $f$ es sobreyectiva.

$\square$

Algunas funciones sobreyectivas

Ejemplo:

La función identidad es sobreyectiva. En efecto, sea $Id_X:X\to X$ la función identidad y sea $y\in X$, entonces existe $y\in X$ tal que $Id_X(y)= y$.

Por lo tanto, $Id_X$ es sobreyectiva.

$\square$

Ejemplo:

Sea $f:X\to \set{c}$ una función dada por $f(x)=c$ para todo $x\in X$. Tenemos que $f$ es sobreyectiva.

En efecto, sea $y\in \set{c}$. Dado que $y\in \set{c}$, entonces $y=c$. veamos que existe $x\in X$ tal que que $f(x)=c$. Esto último se cumple por como esta definida la función $f$.

$\square$

Ejemplo:

Sea $X$ un conjunto y $A\subseteq X$, la función característica de $A$ es una función sobreyectiva.

Dado que el codominio de la función característica es el conjunto $\set{\emptyset, \set{\emptyset}}$, deseamos ver que para cualquier $y\in \set{\emptyset, \set{\emptyset}}$ existe $x\in X$ tal que $\chi_A(x)=y$.

Caso 1: Si $y=\emptyset$, entonces existe $x\in X$ tal que $x\notin A$, de modo que $\chi_A(x)=\emptyset$.

Caso 2: Si $y=\set{\emptyset}$, entonces existe $x\in X$ tal que $x\in A$, de modo que $\chi_A(x)=\set{\emptyset}$.

Por lo tanto, $\chi_A$ es sobreyectiva.

$\square$

Composición de funciones

Así como lo hicimos en la sección anterior con respecto a la inyectividad, podemos averiguar que pasa con la composición de funciones con respecto a la sobreyectividad. Veamos el siguiente teorema:

Teorema: Sean $f:X\to Y$ y $g:Y\to Z$ funciones sobreyectivas, $g\circ f$ es sobreyectiva.

Demostración:

Sea $z\in Z$, veamos que existe $x\in X$ tal que $g\circ f(x)=z$.
Dado que $g$ es sobreyectiva y $z\in Z$, entonces existe $y\in Y$ tal que $g(y)=z$. Luego, como $f$ es sobreyectiva y $y\in Y$, entonces existe $x\in X$ tal que $f(x)=y$, así $g(y)=g(f(x))= z$. Por lo tanto, $g\circ f$ es sobreyectiva.

$\square$

Funciones biyectivas

Definición: Decimos que $f:X\to Y$ es una función biyectiva si y sólo si $f$ es inyectiva y sobreyectiva.

Ejemplo:

La función identidad es biyectiva.

Verificamos en la sección de funciones inyectivas que la función identidad es una función inyectiva, además de que en esta sección verificamos que es sobreyectiva.

$\square$

Ejemplo:

Sean $X=\set{1,2,3}$ y $Y=\set{2,4,6}$ y sea $f:X\to Y$ una función dada por $f(x)=2x$. Tenemos que $f$ es inyectiva pues es una función uno a uno, es decir, elementos distintos van a dar a elementos distintos. Más explícitamente $1$ va a dar a $2$, $2$ a $4$ y $3$ a $6$.

Además $f$ es sobreyectiva, pues para cualquier $y\in Y$, existe $x\in X$ tal que $f(x)=y$. En efecto, ya que para $2\in Y$ existe $1\in X$ tal que $f(1)=2$; para $4\in Y$ existe $2\in X$ tal que $f(2)=4$ y por último para $6\in Y$ existe $3\in X$ tal que $f(3)=6$.

$\square$

Tarea moral

Realiza la siguiente lista de ejercicios que te ayudara a fortalecer los conceptos de función inyectiva, sobreyectiva y biyectiva:

  1. Sean $f:X\to Y$ y $g:Y\to Z$ funciones. Demuestra que si $g\circ f$ es sobreyectiva, entonces $g$ es sobreyectiva.
  2. Demuestra o da un contraejemplo del siguiente enunciado: Si $f:X\to Y$ y $g:Y\to Z$ son funciones tales que $g\circ f$ es sobreyectiva, entonces $f$ es sobreyectiva.
  3. Sean $X=\set{1,2,3, \cdots}$ y $Y=\set{3,4,5,\cdots}$ y sea $f:X\to Y$ dada por $f(x)=2x+3$. ¿$f$ es sobreyectiva? Argumenta tu repuesta.

Más adelante

Ahora que aprendimos el concepto de función inyectiva y sobreyectiva tenemos las bases suficientes para hablar de funciones invertibles. Veremos funciones invertibles por la derecha e invertibles por la izquierda, cuyos conceptos resultarán equivalentes al de función sobreyectiva y función inyectiva respectivamente.

Enlaces

En el siguiente enlace podrás encontrar más contenido acerca de funciones inyectivas y sobreyectivas:

Funciones inyectivas y sobreyectivas