Matemáticas/Teoría de conjuntos/Intuitiva/Relaciones

1.8.1. Sean los conjuntos $x$ e $y$. Cualquier subconjunto $\mathrm {R} \subseteq x\times y$ se dice relación de $x$ sobre $y$. Por tanto, una relación es un conjunto de pares ordenados, de modo que toda función $f:x\longrightarrow y$ es una relación, si bien lo recíproco no es necesariamente cierto, pues puede una relación no cumplir (f-1) o (f-2) (o ambas) de 1.7.1 . De ésto, resulta conveniente adoptar una notación diferente a la que se usó con las funciones para expresar el hecho de que $(a,b)\in \mathrm {R}$. Así pues, escribiremos

$a\mathrm {R} b\quad \mathrm {siempre\ que} \quad (a,b)\in \mathrm {R}$,

y $a\not \mathrm {R} b$ cuando $(a,b)\notin \mathrm {R}$. Para el caso particular en que $f$ es una relación que es a su vez es función, tenemos

$f(a)=b\quad \mathrm {equivale\ a} \quad a\mathrm {f} b$.

Sin embargo, emplearemos la notación $f(a)=b$ para representar $(a,b)\in f$ cuando sepamos que $f$ es una función.

1.8.2. Las relaciones pueden definirse entre más de dos conjuntos. Así, una relación entre los conjuntos $x$, $y$ y $z$, puede ser cualquier subconjunto del producto cartesiano $x\times y\times z$, y consistiría por tanto de ternas ordenadas. Una relación $\mathrm {R}$ así se dice relación ternaria, para distinguirse de las relaciones que se aplican solo entre dos conjuntos (que naturalmente se llaman relaciones binarias). En términos más generales, una función $n$-aria entre cuales quiera $n$ conjuntos $x_{1},\ldots ,x_{n}$, es un conjunto cualquiera $\mathrm {R} \subseteq x_{1}\times \cdots \times x_{n}$.

1.8.3. En este libro solo trataremos las relaciones binarias, por lo que cuando se hable de relación se entenderá que se trata de una de éstas.

1.8.4. En particular, una relación sobre un conjunto $x$ es un subconjunto $\mathrm {R} \subseteq x\times x$. Al igual que las funciones, las relaciones sobre un conjunto $x$ pueden tener, de forma particular, ciertas propiedades que permiten clasificarlas. Más exactamente: Sea $\mathrm {R}$ una relación sobre un conjunto $x$.

La relación $\mathrm {R}$ es reflexiva siempre que

( R-1 ) $a\mathrm {R} a$ para toda $a\in x$.

La relación $\mathrm {R}$ es irreflexiva si

( R-2 ) $a\mathrm {R} a$ para ningún $a\in x$.

La relación $\mathrm {R}$ es simétrica siempre que

(R-3) $a\mathrm {R} b$ y $b\mathrm {R}$ a para cualesquiera $a,b\in x$.

La relación $\mathrm {R}$ es antisimétrica siempre que

(R-4) $a\mathrm {R} b$ y $b\mathrm {R} a$ implica $a=b$ para cualesquiera $a,b\in x$.

La relación $\mathrm {R}$ es asimétrica siempre que

(R-5) $a\mathrm {R} b$ implica que $b\mathrm {R}$ a es falso para cualesquiera $a,b\in x$.

La relación $\mathrm {R}$ es transitiva siempre que

(R-6) $a\mathrm {R} b$ y $b\mathrm {R} c$ implica $a\mathrm {R} c$ para cualesquiera $a,b,c\in x$.

La relación $\mathrm {R}$ es conexa siempre que

(R-7) $a\mathrm {R} b$ o $b\mathrm {R} a$ para cualesquiera $a,b\in x$.

1.8.5. Una relación $\mathrm {R}$ que es reflexiva, simétrica y transitiva se dice relación de equivalencia. Si $\mathrm {R}$ es una relación de equivalencia sobre un conjunto $x$ y si $a\in x$, entonces el conjunto $\left[a\right]_{\mathrm {R} }$ dado por

$\left[a\right]_{\mathrm {R} }=\{b\mid b\in x\quad {\mbox{y}}\quad b\mathrm {R} a\}$

se dice clase de equivalencia de $a$ por $\mathrm {R}$. Si se sabe cual es la relación $\mathrm {R}$ y si no se presta a confusión, es común escribir simplemente $\left[a\right]$ en lugar de $\left[a\right]_{\mathrm {R} }$. Así pues

$b\in \left[a\right]_{\mathrm {R} }\quad {\mbox{si y solo si}}\quad b\mathrm {R} a$.

1.8.6. La aplicación identidad en un conjunto $x$,

$\mathrm {id} _{x}=\{(a,a)\mid a\in x\}$,

es claramente una relación de equivalencia sobre $x$, y dentro del contexto de la teoría de relaciones suele hacerse referencia a ella mediante el término relación trivial.

1.8.7. Otra relación de equivalencia sobre un conjunto $x$ es el mismo producto cartesiano $x\times x$, que en este caso se llama comúnmente relación grosera.

1.8.8. Puesto que una relación de equivalencia $\mathrm {R}$ sobre un conjunto $x$ es reflexiva, tenemos

$a\in \left[a\right]_{\mathrm {R} }$

para todo $a\in x$. Además, $\mathrm {R}$ es simétrica, de donde

$b\in \left[a\right]_{\mathrm {R} }\quad \mathrm {si\ y\ solo\ si} \quad a\in \left[b\right]_{\mathrm {R} }$.

Se tiene también que

$b,c\in \left[a\right]_{\mathrm {R} }\quad \mathrm {implica} \quad b\mathrm {R} c$.

Efectivamente, pues si $b,c\in \left[a\right]_{\mathrm {R} }$, entonces $a\mathrm {R} b$ y $c\mathrm {R} a$, y por simetría, $a\mathrm {R} c$, luego por transitividad $b\mathrm {R} c$. Otra cosa más es que

$\left[a\right]_{\mathrm {R} }\cap \left[b\right]_{\mathrm {R} }\neq \varnothing \quad {\mbox{implica}}\quad \left[a\right]_{\mathrm {R} }=\left[b\right]_{\mathrm {R} }$.

La razón es que si $\left[a\right]_{\mathrm {R} }\cap \left[b\right]_{\mathrm {R} }\neq \varnothing$, entonces existe un $c\in x$ tal que $c\in \left[a\right]_{\mathrm {R} }$ y $c\in \left[b\right]_{\mathrm {R} },$ o sea que $c\mathrm {R} a$ y $c\mathrm {R} b$, y con esto $a\mathrm {R} b$, que como ya vimos significa que $\left[a\right]_{\mathrm {R} }=\left[b\right]_{\mathrm {R} }$.

1.8.9. Otra forma de expresear este resultado es que

$\left[a\right]_{\mathrm {R} }\neq \left[b\right]_{\mathrm {R} }\quad \mathrm {implica} \quad \left[a\right]_{\mathrm {R} }\cap \left[b\right]_{\mathrm {R} }=\varnothing$

.

1.8.10. Sea $\mathrm {R}$ una relación de equivalencia sobre un conjunto $x$. El conjunto cociente de $x$ por la relación $\mathrm {R}$, que se representa por $x/\mathrm {R}$, se define por

$x/\mathrm {R} =\{\left[a\right]_{\mathrm {R} }\mid a\in x\}$.

Es decir, $x/\mathrm {R}$ contiene todas las clases de equivalencia por la relación $\mathrm {R}$.

1.8.11. Puesto que cada uno de los elementos de $x$ está en alguna clase de equivalencia (pues por ejemplo si $a\in x$ se tiene $a\in \left[a\right]_{\mathrm {R} }$), resulta que

$\bigcup _{\left[a\right]_{\mathrm {R} el}\in x/{\mathrm {R} }}\left[a\right]_{\mathrm {R} }=x$,

o, para mayor claridad,

$\bigcup _{a\in x}\left[a\right]_{\mathrm {R} }=x$,

y como cualesquiera dos clases de equivalencia distintas de $x/\mathrm {R}$ son disjuntas (véase 1.8.9), $x/\mathrm {R}$ es una partición de $x$ (véase 1.5.6).

1.8.12. Sea $C$ una partición de un conjunto $X$. Luego defínase la relación $\mathrm {R}$ mediante

$\mathrm {para\ cualesquiera} \ a,b\in X,\quad a\mathrm {R} b\ \mathrm {si\ y\ solo\ si} \ a,b\in x$

para algún $x\in C$. Puesto que

$\bigcup _{x\in C}x=X$,

cada uno de los elementos de $X$ está contenido en algún conjunto $x$ de $C$, por lo que $a\mathrm {R} a$ para todo $a\in X$, y así $\mathrm {R}$ es reflexiva. Claramente $a\mathrm {R} b$ implica $b\mathrm {R} a$ para todo $a,b\in X$, por lo que $\mathrm {R}$ es simétrica. Además, si $a\mathrm {R} b$ y $b\mathrm {R} c$, existen $x_{1},x_{2}\in C$ tales que $a,b\in x_{1}$ y $b,c\in x_{2}$, y estos han de cumplir $x_{1}=x_{2}$ (pues si $x_{1}\neq x_{2}$, ha de ser $x_{1}\cap x_{2}=\varnothing$, lo que es contradictorio en vista de que $b\in x_{1}$ y $b\in x_{2}$), y entonces concluimos que $a\mathrm {R} c$. Esto hace que $\mathrm {R}$ sea también transitiva, y entonces termina siendo esta una relación de equivalencia sobre $X$ inducida por la partición $C$.

1.8.13. El resultado de 1.8.11 y el resultado de 1.8.12 se resumen en el enunciado siguiente:

Si $\mathrm {R}$ es una relación de equivalencia sobre un conjunto $x$, entonces el conjunto cociente $x/\mathrm {R}$ es una partición de $x$ y, recíprocamente, si $P$ es una partición del conjunto $x$, entonces existe una relación $\mathrm {R}$ tal que $x/\mathrm {R} =P$.

1.8.14. Una relación $\mathrm {R}$ sobre un conjunto $x$ reflexiva, antisimétrica y transitiva se dice relación de orden parcial (o simplemente un orden) sobre el conjunto $x$, y el par $(x,\mathrm {R} )$ se dice entonces un conjunto parcialmente ordenado, o simplemente que es un conjunto ordenado.

1.8.15. Aquí usaremos el símbolo

$\leq$

para representar un orden parcial cualquiera (diferente según el contexto) y no solo para el familiar orden sobre el conjunto de números reales.

En particular, la relación de inclusión $\subseteq$ sobre el conjunto potencia ${\mathcal {P}}(x)$ de un conjunto $x$ es una relación de orden parcial.

1.8.16. Se dice que $\mathrm {R}$ es una relación de orden (parcial) estricto, o simplemente que es un orden estricto, sobre un conjunto $x$, si $\mathrm {R}$ es irreflexiva, antisimétrica y transitiva. Para representar ordenes estrictos, cualesquiera que sean estos, usaremos el símbolo

$<$

.

Un orden que no sea estricto será llamado simplemente orden no estricto.

1.8.17. Si $\leq$ es una relación de orden no estricto sobre un conjunto $x$, entonces la relación

$<=\{(a,b)\mid (a,b)\in \,\leq \quad {\mbox{y}}\quad a\neq b\}$

es claramente un orden estricto sobre $x$. Por otro lado, si $<$ es una relación de orden estricto sobre $x$, entonces

$\leq =<\cup \{(a,a)\mid a\in x\}$

es una relación de orden no estricto sobre $x$.

1.8.18. Sea $(x,\leq )$ un conjunto ordenado. Un elemento $a\in x$ tal que $a\leq b$ para todo $b\in x$ se dice elemento mínimo (o primer elemento) de $x$. El elemento mínimo de un conjunto, si existe, es único. En efecto, pues si $a$ y $a'$ fueran dos elementos mínimos de $x$, por definición

$a\leq a'\quad {\mbox{y}}\quad a'\leq a$,

y por antisimetría, $a=a'$.

1.8.19. Sea $(x,\leq )$ un conjunto ordenado. Un elemento $a\in x$ tal que $b\leq a$ para todo $b\in x$ se dice elemento máximo (o último elemento) de $x$. También el elemento máximo de un conjunto, si existe, es único.

1.8.20. En un conjunto ordenado $(x,\leq )$ es posible que existan elementos que, pudiendo no ser un máximo o un mínimo de $x$, tienen cierta distinción sobre otros elementos de $x$ por medio de el orden $\leq$. Nos referimos a los minimales y los maximales. Un elemento $a\in x$ es un minimal en $x$ si no existe ningún elemento en $x$ estrictamente menor que $a$. (por medio del orden estricto $<$ dado por $a<b$ si y solo si $a\leq b$ y $a\neq b$, por supuesto) ; un elemento $a\in x$ se dice máximal de $x$ si no existe ningún elemento en $x$ estrictamente mayor que $a$. Es posible que los minimales de un conjunto, si existen, sean más de uno. Lo mismo aplica para los maximales de un conjunto.

Notemos pues que un conjunto puede no contener ni mínimos (máximos) ni minimales (maximales), o bien, contener uno o más minimales (maximales) y ningún mínimo (máximo). Si un conjunto tiene mínimo (máximo), éste es a su vez el único minimal (maximal) del conjunto.

1.8.21. Sea $(x,\leq )$ un conjunto ordenado, y sea $x_{1}\subseteq x$. Un elemento $a\in x$ tal que $a\leq b$ para todo $b\in x_{1}$ se dice cota inferior (o minorante) de $x_{1}$. Por otro lado, un elemento $a\in x$ tal que $b\leq a$ para todo $b\in x_{1}$ se dice cota superior (o mayorante) de $x_{1}$. Una cota inferior o superior de $x_{1}$ puede o no estar en $x_{1}$. Además, si $C_{i}$ es el conjunto de cotas inferiores de $x_{1}$, entonces $C_{i}\cap x_{1}$ solo puede ser vacío o ser un conjunto con un solo elemento. Si $C_{i}\cap x_{1}\neq \varnothing$, entonces el único elemento de $C_{i}\cap x_{1}$ es claramente un mínimo de $x_{1}$. Si $C_{i}$ contiene un elemento máximo, entonces este se dice ínfimo de $x_{1}$, y lo representaremos por $\mathrm {inf} (x_{1})$. Análogamente, si $C_{s}$ es el conjunto de todas las cotas superiores de $x_{1}$, $C_{s}\cap x_{1}=\varnothing$ o $C_{s}\cap x_{1}$ contiene a lo más un elemento, el cual sería entonces un máximo de $x_{1}$. Si $C_{s}$ tiene un mínimo, entonces este se dice supremo de $x_{1}$, y lo representaremos por $\mathrm {sup} (x_{1})$.

1.8.22. Un conjunto que tiene cotas inferiores se dice inferiormente acotado, mientras que un conjunto que tiene cotas superiores se dice superiormente acotado. Si un conjunto esta acotado inferior y superiormente, se dice simplemente que es acotado.

1.8.23. Sea $(x,\leq )$ un conjunto parcialmente ordenado. Si todo subconjunto de $x$ admite un minimal respecto de $\leq$, se dice que $\leq$ es una relación de orden bien fundada sobre $x$, o que es un orden bien fundado sobre $x$. Dado ese caso, se dice que el par $(x,\leq )$ es bien fundado.

1.8.24. Un hecho apreciable a cerca de órdenes bien fundados es el siguiente:

Si $(x,\leq )$ es un conjunto parcialmente ordenado, entonces $(x,\leq )$ es bien fundado si y solo si no existe una secuencia infinita $\{a\}_{n}^{\infty }$ tal que $a_{n+1}<a_{n}$.

En efecto, pues si $(x,\leq )$ no fuera un conjunto bien fundado, entonces, si $a_{n}\in x$, $a_{n}$ no es un minimal, y por lo tanto existe otro elemento $a_{n+1}\in x$ tal que $a_{n+1}<a_{n}$. Este argumento es claramente válido para cualquiera que sea el número natural $n$, por lo que se concluye que si $(x,\leq )$ es no bien fundado, existe una secuencia infinita descendiente $\ldots <a_{n+1}<a_{n}<\ldots <a_{0}$. Recíprocamente, si $(a,\leq )$ es un conjunto ordenado tal que existe una secuencia descendiente infinita $\ldots <a_{n+1}<a_{n}<\ldots <a_{0}$, entonces, para cualquiera que sea el elemento $a_{n}\in x$, existe otro $a_{n+1}$ tal que $\ldots <a_{n+1}<a_{n}$, de modo que $a_{n}$ no es minimal de $x$, y con ello $(x,\leq )$ es no bien fundado.

1.8.25. Una relación de orden $\leq$ que es conexa en $x$, se dice relación de orden total, u orden total, sobre $x$, y se dice que el par $(x,\leq )$ es un conjunto totalmente ordenado.

1.8.25. Un conjunto totalmente ordenado y bien fundado se dice conjunto bien ordenado, y su relación de orden se dice por tanto un buen orden. Supóngase que $(x,\leq )$ es un conjunto bien ordenado. Entonces $(x,\leq )$ es, en particular, bien fundado, por lo que todo subconjunto $x_{1}\subseteq x$ tiene por lo menos un minimal. Supóngase que $a$ y $a'$ son dos minimales de $x_{1}$. Puesto que $(x,\leq )$ es totalmente ordenado,

$a\leq a'\quad \mathrm {o} \quad a'\leq a$.

Cualquiera que sea el caso, debe de ser $a=a'$, pues si no, $a<a'$ o $a'<a$, lo que no puede ser por que un minimal no tiene un elemento estrictamente menor que él (ni siquiera siendo este otro minimal). Vemos entonces que el elemento minimal $a$ es un mínimo de $x_{1}$. Por conclusión, un conjunto ordenado $(x,\leq )$ es bien ordenado si todo subconjunto $x_{1}$ de $x$ tiene mínimo.

---

Capítulo anterior: Funciones Capítulo siguiente: Ejercicios