Archivo de la etiqueta: orden total

Teoría de los Conjuntos I: Construcción de los números naturales

Introducción

Hasta ahora hemos usado a los números naturales como los conocemos desde la educación básica, sin embargo dado que estamos en un curso de teoría de conjuntos hablaremos de los números naturales desde la perspectiva de los conjuntos. En esta sección comenzaremos con la construcción rigurosa de los números naturales, sin dejar de lado la noción intuitiva que ya tenemos.

Construcción

Al principio del curso hablamos acerca de los primeros axiomas de la teoría de los conjuntos, vimos que existía un conjunto y que tal conjunto (vacío) no tiene elementos, además probamos su unicidad. Con base a los demás axiomas y al conjunto vacío construimos más conjuntos como $\set{\emptyset}$, $\set{\set{\emptyset}}, \set{\emptyset, \set{\emptyset}}$, $\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$, etcétera.

Si nos fijamos en la cantidad de elementos que tienen estos conjuntos notaremos que varía o que algunos tienen la misma cantidad pero son conjuntos distintos, como $\set{\emptyset}$ y $\set{\set{\emptyset}}$.

Dado que queremos construir a los números naturales lo que intentaremos hacer es asociarle a cada número un conjunto según la cantidad de elementos que tenga. Por el argumento anterior podemos deducir que existe más de una forma de hacer esto, por ejemplo:

\begin{align*}
0 &-\emptyset\\
1&-\set{\set{\emptyset}}\\
2&-\set{\emptyset, \set{\set{\emptyset}}}\\
3&-\set{\emptyset, \set{\set{\emptyset}}, \set{\emptyset, \set{\set{\emptyset}}}}\\
\vdots
\end{align*}

Otra forma posible es la siguiente:

\begin{align*}
0 &-\emptyset\\
1&-\set{\emptyset}\\
2&-\set{\emptyset, \set{\emptyset}}\\
3&-\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}\\
\vdots
\end{align*}

Sin embargo, según la definición que daremos más adelante, vamos a requerir que nuestra construcción tenga ciertas características, por lo que aunque exista más de una forma de asociarle un número a un conjunto según la cantidad de elementos que este tenga nos quedaremos con la segunda forma.

Para definir formalmente a los números naturales comenzaremos definiendo una de las características que a simple vista cumplirá un número natural, tal característica es la de ser un conjunto transitivo.

Conjuntos transitivos

Definición: Sea $x$ un conjunto. Decimos que $x$ es un conjunto transitivo si para cualquier $y\in x$ se cumple que $y\subseteq x$.

Ejemplo:

Dado que nos quedamos con la segunda forma que dimos para identificar a los números naturales, al vacío le asociamos el número natural 0, por lo que este conjunto tendría que ser transitivo. En efecto, si $x=\emptyset$, se cumple por vacuidad que para cualquier $y\in \emptyset$, $y\subseteq \emptyset$. Por lo tanto, $\emptyset$ es un conjunto transitivo.

$\square$

Ejemplo:

Sea $x=\set{\emptyset}$. Dado que su único elemento es $y=\emptyset$, para ver que $x$ es transitivo basta ver que $\emptyset\subseteq \set{\emptyset}$ lo cuál sabemos que es cierto. Por lo tanto, $\set{\emptyset}$ es un conjunto transitivo.

$\square$

Ejemplo:

Sea $x=\set{\emptyset, \set{\set{\emptyset}}}$. Tenemos que $x$ no es transitivo. En efecto, pues $\set{\set{\emptyset}}\in x$ pero $\set{\set{\emptyset}}\not\subseteq x$ dado que $\set{\emptyset}\in \set{\set{\emptyset}}$ pero $\set{\emptyset}\notin x$. Por lo tanto, $\set{\emptyset, \set{\set{\emptyset}}}$ no es un conjunto transitivo.

$\square$

A continuación veremos algunas equivalencias para conjunto transitivo.

Proposición: Sea $x$ un conjunto. Entonces, $x$ es un conjunto transitivo si y sólo si $x\subseteq \mathcal{P}(x)$.

Demostración:

Si $x=\emptyset$, entonces se cumple que $\emptyset\subseteq \mathcal{P}(x)=\set{\emptyset}$.

Supongamos ahora que $x\not=\emptyset$. Sea $y\in x$, como $x$ es un conjunto transitivo se tiene que $y\subseteq x$ y por lo tanto, $y\in \mathcal{P}(x)$. Así, $x\subseteq \mathcal{P}(x)$.

Ahora, supongamos que $x\subseteq \mathcal{P}(x)$ y veamos que $x$ es un conjunto transitivo. Sea $y\in x$, tenemos que $y\in \mathcal{P}(x)$ y así, $y\subseteq x$.

Por lo tanto, $x$ es un conjunto transitivo.

$\square$

Proposición: Sea $x$ un conjunto. Si $x$ es un conjunto transitivo, entonces $\bigcup x\subseteq x$.

Demostración:

Si $x=\emptyset$, entonces $\bigcup x= \emptyset\subseteq \emptyset=x$.

Si $x\not=\emptyset$.
Sea $y\in \bigcup x$, entonces existe $z\in x$ tal que $y\in z$. Luego, como $z\in x$ y $x$ es un conjunto transitivo entonces $z\subseteq x$ y así, $y\in x$. Por lo tanto, $\bigcup x\subseteq x$.

$\square$

Otros resultados para conjuntos transitivos

A continuación y para concluir esta entrada veremos algunos resultados para conjuntos transitivos, esta vez con respecto a la intersección y la unión.

Proposición: Si $x$ y $y$ son conjuntos transitivos, entonces $x\cap y$ es un conjunto transitivo.

Demostración:

Sean $x$ y $y$ conjuntos transitivos. Veamos que $x\cap y$ es un conjunto transitivo, es decir, para cada $z\in x\cap y$ se cumple que $z\subseteq x\cap y$.

  1. Como $x$ es un conjunto transitivo, entonces para cualquier $z\in x$ se cumple que $z\subseteq x$.
  2. Dado que $y$ es un conjunto transitivo, entonces para cualquier $z\in y$ se cumple que $z\subseteq y$.

De $1$ y $2$ podemos concluir que para cualquier $z\in x\cap y$ se satisface que $z\subseteq x\cap y$.

Por lo tanto, $x\cap y$ es un conjunto transitivo.

$\square$

Proposición: Si $x$ y $y$ son conjuntos transitivos, $x\cup y$ es un conjunto transitivo.

Demostración:

Sean $x$ y $y$ conjuntos transitivos. Veamos que $x\cup y$ es un conjunto transitivo, es decir, para cada $z\in x\cup y$ se cumple que $z\subseteq x\cup y$.

  1. Como $x$ es un conjunto transitivo, entonces para cualquier $z\in x$ se cumple que $z\subseteq x$.
  2. Dado que $y$ es un conjunto transitivo, entonces para cualquier $z\in y$ se cumple que $z\subseteq y$.

De $1$ y $2$ podemos concluir que para cualquier $z\in x\cup y$ se satisface que $z\subseteq x\cup y$.

$\square$

Tarea moral

  • ¿Cuál de los siguientes conjuntos es transitivo?
    1. $\set{\emptyset, \set{\emptyset}}$,
    2. $\set{\set{\emptyset}}$,
    3. $\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$.
  • Demuestra que $(\set{\emptyset, \set{\emptyset}}, \in)$ es un conjunto totalmente ordenado.
  • Demuestra que $x=\set{\emptyset, \set{\emptyset}, \set{\emptyset, \set{\emptyset}}}$ tiene elemento máximo y elemento mínimo en el orden $\in_x$.
  • Sea $x$ un conjunto. Demuestra que si $\bigcup x\subseteq x$, entonces $x$ es un conjunto transitivo.

Más adelante

En la siguiente entrada daremos la definición formal y rigurosa de que es un número natural. Además demostraremos algunas de sus propiedades.

Enlaces

Para ver contenido acerca de números naturales puedes consultar el siguiente enlace: Álgebra Superior I: Introducción a números naturales.

Para recordar la definición de orden total puedes consultar el siguiente enlace: Teoría de los Conjuntos I: Orden total

Para recordar las definiciones de mínimo y máximo consulta el siguiente enlace: Teoría de los Conjuntos I: Mínimos, máximos, minimales y maximales

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

Álgebra Superior I: Órdenes parciales y totales

Introducción

En la entrada pasada, hemos introducido algunos tipos de relaciones de un conjunto en sí mismo. En esta entrada y en la siguiente, veremos algunos ejemplos de este tipo de relaciones, y lo haremos con un concepto que puede que te suene muy familiar desde algunas ideas básicas de los números: el órden.

Ordenes

En la vida cotidiana muchas veces nos surge la necesidad de comparar distintas cosas. Por ejemplo, podemos comparar qué tan lejos está un lugar a comparación de otros. Podemos decir que si una plaza comercial nos queda a dos kilómetros, está más cerca de un parque que queda a tres kilómetros de distancia. ¿Por qué pasa esto? Pues nosotros tenemos alguna noción de que dos kilómteros es menor distancia que tres. O al comparar el tamaño del disco duro de alguna computadora, podemos decir que $512$ Gb es mejor que $256$ Gb, puesto que el de $512$ tiene una mayor capacidad del de $256$. ¿Ves como es que usamos las palabras de mayor y menor? Cuando nosotros estamos usando la noción de ser mayor que o menor que, estamos hablando de un orden. Que es un tipo de relación entre un conjunto consigo mismo, por ahora veremos dos tipos de órdenes entre conjuntos: el orden parcial y el orden total.

Órdenes parciales

Piensa en la relación de $\mathbb{Z}^2$ dada por «ser menor o igual a», es decir la relación:

$$ \leq = \{(x,y) \in \mathbb{Z}^2: x \text{ es menor o igual a } y\}$$

Por ejemplo, $(1,2) \in \leq$ pues $1$ es menor o igual a $2$. Si dos elementos $x,y$ están relacionados mediante $\leq$, simplemente escribiremos $x\leq y$ en lugar de $(x,y) \in \leq$. Veamos algunas propiedades que tiene esta relación:

  1. $\leq$ es simétrica. Nota que para cualquier $x \in \mathbb{Z}$ sucede que $x=x$, en general $x \leq x$, pues la relación $\leq$ está dada por «ser menor o igual», y $x$ es igual a sí mismo.
  2. $\leq$ es antisimétrica. Para ver esto, nota que si sucede al mismo tiempo que $x \leq y$ y $y \leq x$, entonces estamos diciendo que $x$ es igual o menor a $y$ al mismo tiempo que $y$ es menor o igual a $x$. De tal forma que sucede que $$(x<y \lor x=y) \land (y<x \lor y=x) \Leftrightarrow (x<y \land y<x) \lor (x=y).$$ Nota que la primera condición no se cumple, entonces tiene que pasar que $x=y$
  3. $\leq$ es transitiva. Considera tres números $x,y,z \in \mathbb{Z}$ Y nota que si $x \leq y \land y \leq z$ entonces $x \leq z$.

Es por estas propiedades que decimos que la relación $\leq$ es un orden parcial.

Definición. Sea $X$ un conjunto y $R$ una relación de $X$ consigo misma. Diremos que $R$ es un orden parcial sobre $X$ si $R$ es relfexica, antisimétrica y transitiva a la vez.

Otro ejemplo de un orden parcial es la relación de inclusión $\subset$ dentro de los subconjuntos de algún conjunto $X$. Pues recordemos que esta relación está dada por «estar contenido en». Ahora, considera $A,B,C \in \mathcal{P}(X)$, entonces:

  • $\subset$ es reflexiva. Nota que como $A=A$, entonces $A \subset A$.
  • $\subset$ es antisimétrica. Si $A \subset B \land B \subset A$, entonces:$$\forall x ((x \in A \Rightarrow x \in B) \land (x \in B \Rightarrow x \in A)).$$ La cual es una equivalencia de $$\forall x (x \in A \Leftrightarrow x \in B) .$$ Es decir $A=B$.
  • $\subset$ es transitiva. Si $A \subset B \land B \subset C$ entonces:
    $$\begin{align*}
    \forall x((x \in A \Rightarrow x \in B) \land (x \in B \Rightarrow x \in C))
    \end{align*}$$ Y recordemos que podemos aplicar la regla de inferencia usada en demostraciones directas para demostrar que esto significa que
    $$\begin{align*}
    \forall x((x \in A \Rightarrow x \in B) \land (x \in B \Rightarrow x \in C)) &\Rightarrow \forall x(x \in A \Rightarrow x \in C)\\
    &\Leftrightarrow A \subset C.
    \end{align*}$$

Órdenes totales

Ahora, vamos a ver el siguiente concepto que es el de órdenes totales, que en pocas palabras son órdenes parciales con la propiedad de la tricotomía. Veamos de qué trata.

Cuando estemos hablando de un órden total, necesitamos que además de ser un orden parcial, tengamos siempre alguna forma de comparar los elementos de dicho conjunto. Por ejemplo, cuando tengamos dos números enteros $x,y$ siempre podemos decir que $x < y \lor x=y \lor x>y$, es decir, se cumple la propiedad de la tricotomía.

Definición. Sea $X$ un conjunto y $R$ una relación de $X$ en sí misma. Diremos que $R$ tiene la propiedad de la tricotomía, si para cada par de elementos $x,y \in X$ pasa que $x=y$ ó $(x,y) \in R$ ó $(y,x) \in R$.

Esta última definición hace que se nos permita poder «comparar» los elementos de $X$, siempre podemos decir cuál es el orden entre cada par de elementos. Piénsalo como un: si una relación tiene la tricotomía, entonces podemos siempre saber cómo se relacionan todos los elementos entre sí. Un orden total será un orden parcial que tiene esta propiedad.

Definición. Sea $X$ un conjunto y $R$ una relación de $X$ en sí misma. Diremos que $R$ es un orden total si es parcial y tiene la propiedad de la tricotomía.

Algunos ejemplos de órdenes totales son:

  • El orden de $\leq$ en $\mathbb{Z}^2$.
  • Las letras del abecedario con el orden usual. $A<B<C<\dots<Z$
  • Las palabras del diccionario forman un orden de acuerdo a cómo son las letras en las palabras, por ejemplo, si buscamos la palabra «oso», esta vendrá antes que la palabra «ratón», pues antes viene la letra «o» que la «r». A su vez, «casa» viene antes que la palabra «caspa», pues todas las letras «cas» son iguales, pero «a» viene antes que la «p». A este orden se le conoce como el orden lexicográfico. Si quieres saber más, revisa la tarea moral.

Otras definiciones sobre el orden

Dentro de un conjunto $X$ total o parcialmente ordenado mediante una relación $\leq$, podemos tener elementos especiales que tendrán nombres particulares. Como por ejemplo:

Definición. Sea $X$ un conjunto con un orden parcial $\leq$ y $x \in X$. Diremos que:

  • $x$ es un elemento maximal si para cualquier $y \in X$ distinta que $x$ no se cumple que $y \leq x$.
  • $x$ es un elemento minimal si para cualquier $y \in X$ distinta que $x$ no se cumple que $x \leq y$.
  • $x$ es un elemento máximo si para cualquier $y \in X$ se cumple que $y \leq x$.
  • $x$ es un elemento mínimo si para cualquier $y \in X$ se cumple que $x \leq y$.

Lo que nos quieren decir estas definiciones es que un elemento es maximal (o minimal) si no existe algún elemento por «arriba (o debajo)» de $x$. Es decir que no podemos encontrar un elemento que esté «después (o antes)» con respecto al orden $\leq$. Lo que nos dice un elemento máximo (o mínimo) es que todo elemento va a ser «menor o igual (mayor o igual)» a $x$. Si lo piensas, pueden sonar a definiciones muy parecidas, y de hecho siempre que un elemento sea máximo (o mínimo), será maximal (o minimal), pero el inverso puede no ser cierto.

La diferencia entre maximal y máximo está en que un máximo $x$ nos indica que siempre podemos comparar cualquiera otro de los elementos $y$ con el máximo y siempre resultará que $y \leq x$. Mientras que un maximal solo nos dice que no existirá un elemento $y$ tal que $x \leq y$, es decir no encontraremos una comparación en el que $x$ resulte ser menor. Lo mismo pasará con el minimal y mínimo.

Por ejemplo, piensa en el conjunto $X=\{1,2,3\}$ y el orden parcial $\leq = \{(1,1),(2,2),(3,3),(1,3),(2,3)\}$. Nota que aquí $3$ es un máximo, pues pasa que $1 \leq 3, 2 \leq 3, 3 \leq 3 $, pero $1$ es minimal, pues $1 \leq 3$ y como $2$ no se compara con $1$, entonces se cumple que no existe algún elemento por «debajo» de él. De la misma manera, $2$ es minimal.

Ahora, considera otro orden parcial sobre el mismo conjunto, dado por $\leq* = \{(1,1),(2,2),(3,3),(1,3),(1,2)\}$. Y nota que ahora sucede que bajo este orden, $1$ es mínimo y $2,3$ son elementos maximales.

Tarea moral

  1. Define la relación de orden lexicográfico $\leq_{lex}$ en $\mathbb{Z}^2 \times \mathbb{Z}^2$ en donde $(x,y) \leq_{lex} (w,z)$ si $x \leq y \lor (x=y \land (b \leq d))$. Muestra que $\leq_{lex}$ es un orden total.
  2. Demuestra que si un conjunto con un orden parcial tiene máximo (o mínimo), este es único.
  3. Considera al conjunto $X=\{1,2,3,6,18\}$ y a la relación $|$ «dividir a » dada por:
    $$\begin{align*}
    |=\{&(1,1),(1,2),(1,3),(1,6),(1,18),\\
    &(2,2),(2,6),(2,18),(3,3),(3,6),\\
    &(3,18),(6,6),(6,18),(18,18)\}.
    \end{align*}$$ Y resuelve lo siguiente:
    • Demuestra que $X$ es un orden parcial pero no total.
    • Encuentra el elemento mínimo.
    • Encuentra el elemento máximo.

Más adelante…

En esta entrada nos hemos enfocado en dos tipos de orden, que son los parciales y totales, y estos no solo serán útiles en este curso, pues será un concepto recurrente en temas de cálculo, geometría y demás materias. Por ahora, introdujimos este concepto y pasaremos a otro que igual se usarán mucho, que son las relaciones de equivalencia, que nos permite «partir conjuntos» de acuerdo a elementos que se relacionen entre sí.

Entradas relacionadas

Álgebra Superior II: El orden en los enteros

Introducción

En las entradas anteriores introdujimos al conjunto de los números enteros, así como sus operaciones de suma y producto. Lo que haremos ahora es ver cómo ordenar a los elementos en $\mathbb{Z}$. Lo haremos de una forma similar a la que hicimos lo de las operaciones: usando las nociones que ya teníamos definidas en $\mathbb{N}$.

Como recordatorio, en $\mathbb{N}$ dijimos que $a<b$ cuando $a\subseteq b$. De esta noción de «menor que» dimos la noción de «menor o igual que», diciendo que $a\leq b$ cuando ya sea que $a<b$ o bien $a=b$. Vimos que esta relación $\leq$ define un orden parcial en $\mathbb{N}$ que además es tricotómico. Quizás los resultados más importantes para trabajar con esta noción de desigualdad fue ponerla en términos de suma de elementos en $\mathbb{N}$:

  • En $\mathbb{N}$ se cumple que $a<b$ si y sólo si existe un natural $k>0$ tal que $a+k=b$.
  • En $\mathbb{N}$ se cumple que $a\leq b$ si y sólo si existe un natural $k$ tal que $a+k=b$.

Con esto en mente, veamos ahora cómo construir un orden en $\mathbb{Z}$. Antes de hacer eso, conviene primero pensar en números positivos, negativos y el cero.

Los positivos, los negativos y el cero en $\mathbb{Z}$

Ya sabemos que la identidad aditiva en $\mathbb{Z}$ es la clase $\overline{(0,0)}$, que también se puede pensar como la clase $\overline{(a,a)}$ para cualquier $a$ en $\mathbb{N}$. Si tenemos cualquier otra clase $\overline{(a,b)}$, por tricotomía del orden en $\mathbb{N}$ nos quedan sólo otras dos opciones: o bien $a<b$, o bien $b<a$. Esto nos ayudará a definir la noción de positividad y negatividad.

Definición. Sea $\overline{(a,b)}$ un entero. Diremos que ${(a,b)}$ es:

  • Cero si $a=b$,
  • Positivo si $a>b$ y
  • Negativo si $a<b$.

Una vez más, por la tricotomía del orden en $\mathbb{N}$, siempre sucede exactamente una de las posibilidades anteriores. Es importante ver que esta definición está bien hecha, es decir, que no depende de la clase de equivalencia que se eligió. Por ejemplo, si $\overline{(a,b)}$ es positivo, sucede que $a>b$. Si tomamos $(c,d)$ tal que $(a,b)\sim (c,d)$, nos gustaría ver que también sucede $c>d$. Esto se debe a que $a+d=b+c$. Si tuviéramos $c\leq d$, entonces nos pasaría que $a+d>b+c$ y tendríamos una contradicción. Así, por tricotomía debe pasar $c>d$. El caso de la negatividad se verifica de manera análoga.

Recuerda que el inverso aditivo de un entero $\overline{(a,b)}$ es el entero $-\overline{(a,b)}=\overline{(b,a)}$. Así, si $\overline{(a,b)}$ es positivo, entonces su inverso aditivo es negativo y viceversa.

Definición. Usaremos la letra $P$ para referirnos al conjunto de todos los enteros positivos. Usaremos $-P$ para referirnos al conjunto de todos los enteros negativos.

¿Cómo se comportan estas definiciones con las operaciones que ya tenemos en $\mathbb{Z}$? Ahora tenemos todo lo necesario para poder formalizar oraciones como «negativo por negativo es positivo», o «positivo más positivo es positivo.

Proposición. En $\mathbb{Z}$ se cumple todo lo siguiente:

  • Si $\overline{(a,b)}$ y $\overline{(c,d)}$ están en $P$, entonces su suma está en $P$ y su producto también.
  • Si $\overline{(a,b)}$ y $\overline{(c,d)}$ están en $-P$, entonces su suma está en $-P$ y su producto está en $P$.

Demostración. Todas estas afirmaciones se traducen a proposiciones que debemos demostrar en $\mathbb{N}$. En el caso de la primera, debemos ver que si $a>b$ y $c>d$, entonces $a+c>b+d$ y que $ac+bd>ad+bc$. Lo primero es sencillo, pues sale de la compatibilidad de $>$ con la suma de $\mathbb{N}$. Demostremos entonces que $ac+bd>ad+bc$.

Como $a>b$, existe un natural $k>0$ tal que $a=b+k$. Como $c>d$, existe un natural $l>0$ tal que $c=d+l$. Haciendo estas substituciones de $a$ y $c$ en $ac+bd>ad+bc$, obtenemos la siguiente cadena de desigualdades que son equivalentes a lo que debemos demostrar:

\begin{align*}
ac+bd&>ad+bc\\
(b+k)(d+l)+bd&>(b+k)d+b(d+l)\\
bd+bl+kd+kl+bd&>bd+kd+bd+bl.
\end{align*}

La última de estas desigualdades se cumple pues a la izquierda tenemos todos los sumandos que del lado derecho, y además el sumando $kl$ que como $k>0$ y $l>0$, entonces cumple $kl>0$.

Las demostraciones para cuando los elementos son negativos quedan como tarea moral.

$\square$

Al conjunto de enteros positivos también se le conoce en ocasiones como $\mathbb{Z}^+$, y al de enteros positivos también se le conoce como $\mathbb{Z}^-$.

El orden en $\mathbb{Z}$

Estamos listos para definir el orden en $\mathbb{Z}$. Aprovecharemos que ya podemos restar para poner la definición de orden en términos de esta operación.

Definición. Para $\overline{(a,b)}$ y $\overline{(c,d)}$ elementos en $\mathbb{Z}$ diremos que $\overline{(c,d)}<\overline{(a,b)}$ si $\overline{(a,b)}-\overline{(c,d)}$ es un entero positivo.

En realidad la expresión $\overline{(a,b)}-\overline{(c,d)}$ es simplemente $\overline{(a+c,b+d)}$, así que otra forma de escribir la condición de la definición es simplemente pedir que $a+c>b+d$. Como siempre sucede que o bien $a+c>b+d$, o que $a+c<b+d$, o que $a+c=b+d$ (y sólo una de ellas), entonces de manera inmediata obtenemos la tricotomía en $\mathbb{Z}$.

Proposición. Para $\overline{(a,b)}$ y $\overline{(c,d)}$ elementos en $\mathbb{Z}$ siempre sucede exactamente alguna de las siguientes:

  • $\overline{(a,b)}<\overline{(c,d)}$
  • $\overline{(c,d)}<\overline{(a,b)}$
  • $\overline{(a,b)}=\overline{(c,d)}$

Como en el caso de los naturales, a partir de la definición de «menor estricto» es sencillo obtener la noción de «menor o igual».

Definición. Para $\overline{(a,b)}$ y $\overline{(c,d)}$ elementos en $\mathbb{Z}$ diremos que $\overline{(c,d)}\leq \overline{(a,b)}$ si o bien $\overline{(a,b)}-\overline{(c,d)}$ es un entero positivo, o bien $\overline{(a,b)}=\overline{(c,d)}$.

Lo anterior es equivalente a pedir que $a+c\geq b+d$.

Proposición. La relación $\leq$ es un orden parcial en $\mathbb{Z}$.

Demostración. Es inmediato que esta relación $\leq$ es reflexiva, pues $\overline{(a,b)}\leq \overline{(a,b)}$ se obtiene de manera inmediata de la segunda parte de la definición.

Para ver que es antisimétrica, si tuviéramos $\overline{(c,d)}\leq \overline{(a,b)}$ y $\overline{(a,b)}\leq \overline{(c,d)}$, entonces tendríamos las desigualdades $a+c\geq b+d$ y $b+d\geq a+c$, que por la antisimetría en $\mathbb{N}$ implican que $a+c=b+d$, que justo es $\overline{(a,b)}=\overline{(c,d)}$.

Finalmente, para ver que $\leq$ es una relación transitiva, comenzamos con enteros $\overline{(a,b)}, \overline{(c,d)}, \overline{(e,f)}$ tales que $\overline{(e,f)}\leq \overline{(c,d)}$ y $\overline{(c,d)}\leq \overline{(a,b)}$.

De la primer desigualdad obtenemos $c+f\geq e+d$ y de la segunda obtenemos que $a+d\geq b+c$. Sumando ambas desigualdades, obtenemos que $c+f+a+d\geq b+c+e+d$. De aquí podemos deducir que $a+f\geq b+e$. Esto precisamente nos dice que $\overline{(e,f)}\leq \overline{(a,b)}$, como queríamos.

$\square$

Las dos proposiciones anteriores se pueden resumir en el siguiente enunciado.

Teorema. La relación $\leq$ es un orden total en $\mathbb{Z}$.

Compatibilidad del orden con las operaciones en $\mathbb{Z}$

Lo último que nos queda por mencionar es cómo se comporta la relación $\leq$ en $\mathbb{Z}$ con sus operaciones de suma y producto. A continuación mencionamos algunas de las propiedades que se cumplen, aunque hay varias cosas más que se pueden demostrar.

Proposición. En $\mathbb{Z}$ se cumple lo siguiente:

  • Si $\overline{(a,b)}\leq \overline{(c,d)}$ y $\overline{(e,f)}\leq \overline{(g,h)}$, entonces $$\overline{(a,b)}+\overline{(e,f)}\leq \overline{(c,d)}+\overline{(g,h)}.$$
  • Si $\overline{(a,b)}\leq \overline{(c,d)}$ y $\overline{(e,f)}$ es positivo, entonces $$\overline{(a,b)}\overline{(e,f)}\leq \overline{(c,d)}\overline{(e,f)}.$$
  • Si $\overline{(a,b)}\leq \overline{(c,d)}$ y $\overline{(e,f)}$ es negativo, entonces $$\overline{(c,d)}\overline{(e,f)}\leq \overline{(a,b)}\overline{(e,f)}$$

Demostración.

  • Las hipótesis se pueden escribir como $a+d\leq b+c$ y $e+h\leq f+g$. Sumando ambas y asociando de un modo que nos convenga, obtenemos que $(a+e)+(d+h)\leq (b+f)+(c+g)$. Esto lo que nos dice es que $\overline{(a+e,b+f)}\leq $\overline{(c+g,d+h)}$, que es precisamente lo que queríamos demostrar.
  • Por la hipótesis, tenemos que $\overline{(c,d)}-\overline{(a,b)}$ es positivo y que $\overline{(e,f)}$ también. Por lo que ya vimos antes, el producto de estos dos enteros debe ser entonces positivo. Por distributividad, este producto es $\overline{(c,d)}\overline{(e,f)}-\overline{(a,b)}\overline{(e,f)}$. Así, $\overline{(a,b)}\overline{(e,f)}\leq \overline{(c,d)}\overline{(e,f)},$ como queríamos.
  • Por la hipótesis, tenemos que $\overline{(c,d)}-\overline{(a,b)}$ es positivo y que $\overline{(e,f)}$ es negativo. Entonces $\overline{(f,e)}=-\overline{(e,f)}$ es positivo. Por lo que ya vimos antes, el producto de estos dos enteros debe ser entonces positivo. Por distributividad, este producto es $\overline{(c,d)}\overline{(f,e)}-\overline{(a,b)}\overline{(f,e)}$. Esta expresión se puede escribir de manera alternativa como $\overline{(a,b)}\overline{(e,f)}-\overline{(c,d)}\overline{(e,f)}$. Como es positiva, obtenemos justo lo que queríamos.

$\square$

En los ejercicios de la tarea moral explorarás más propiedades de la relación $\leq$ y cómo interactúa con las operaciones en $\mathbb{Z}$.

Tarea moral

  1. Completa las demostraciones de las nociones de positivo, negativo y orden en $\mathbb{Z}$ están bien definidas.
  2. Demuestra que la suma de dos enteros negativos es un entero negativo y que su producto es un entero positivo. Haz una demostración que funcione en general, pero luego verifícalo «a mano» para los enteros $\overline{(3,7)}$ y $\overline{(9,11)}$.
  3. En la entrada dimos la definición formal de $<$ y de $\leq$ en $\mathbb{Z}$, pero aún no hemos definido ni usado los símbolos $>$ y $\geq$ en $\mathbb{Z}$. Formaliza una definición para ellos. Demuestra que $\geq$ también es un orden total en $\mathbb{Z}$.
  4. Demuestra que en $\mathbb{Z}$, si $\overline{(a,b)}\leq \overline{(c,d)}$ y $\overline{(e,f)}$ es negativo, entonces $$\overline{(a,b)}\overline{(e,f)}\geq \overline{(c,d)}\overline{(e,f)}.$$
  5. Determina si la siguiente propiedad del producto y el orden en $\mathbb{Z}$ siempre es verdadera, o bien si hay ocasiones en las que falla: «Si $\overline{(a,b)}\leq \overline{(c,d)}$ y $\overline{(e,f)}\leq \overline{(g,h)}$, entonces $$\overline{(a,b)}\overline{(e,f)}\leq \overline{(c,d)}\overline{(g,h)}.»

Más adelante

Ya tenemos todo lo que necesitamos en los enteros: su definición, sus operaciones y su noción de orden. Sin embargo, aún tenemos una gran dificultad: es muy difícil escribirlos. Cada que queremos referirnos a un entero, debemos usar la clase de equivalencia de una pareja de naturales. Nos gustaría que los enteros fueran algo mucho más intuitivo: los naturales y sus negativos. Lo que haremos en la siguiente entrada es ver cómo formalizar esta idea para que podamos, finalmente, abandonar la notación de parejas de naturales y relaciones de equivalencia. Esto será bastante útil para después entrar en muchas otras propiedades que nos interesan de los enteros como la noción de divisibilidad y otras propiedades aritméticas.

Entradas relacionadas