Relaciones
Las relaciones relacionan dos o más conjuntos
Dados dos conjuntos X e Y, su producto cartesiano se denota como X x Y=\{(x, y)|x\in X, y\in Y\} dónde (x, y) denota a un par ordenado formado por x e y (esta generalización de producto cartesiano se puede aplicar a más de dos conjuntos)
Un subconjunto XxY se denomina relación
Cuando tenemos \mathbb{R}\subset X x X una relación en X, dónde (a, b)\in \mathbb{R} se suele denotar aRb. Estas relaciones pueden cumplir las siguientes propiedades:
- Propiedad reflexiva cuando todos los a \in X cumplen aRa
- Propiedad simétrica si se cumple aRb también se ha de cumplir bRa (se puede denotar de forma abreviada cómo a R b\Rightarrow b R a)
- Propiedad transitiva si se cumple aRb y bRc entonces se ha de cumplir que aRc (se puede denotar de forma abreviada cómo a R b, a R c\Rightarrow a R c)
Una relación que cumpla estas tres propiedades se denomina relación de equivalencia. En lugar de utilizar R, para denotarlas se utiliza \sim
El ejemplo más sencillo de relación de equivalencia es la relación de igualdad (cada elemento está relacionado sólo consigo mismo). Y si en una relación de equivalencia identificamos los elementos relacionados, obtendremos una especie de igualdad
Suponemos que en X tenemos una relación de equivalencia \sim, agrupamos cada elemento a\in R con todos los que están relacionados con él. De esta forma obtenemos para cada a el siguiente conjunto: \hat{a}=\{x \in X| a \sim x\}. A este conjunto se le denomina clase de equivalencia de a
Si tenemos dos elementos a, b\in X, sus respectivas clases de equivalencia \hat{a} y \hat{b} son iguales (\hat{a} =\hat{b}) o disjuntas (\hat{a}\cap\hat{b} = \emptyset), las distintas clases de equivalencia forman lo que se denomina partición de X (por definición, una partición de un conjunto es una serie de subconjuntos que son disjuntos dos a dos y cuya unión da lugar al conjunto)
El conjunto de clases de equivalencia es un nuevo conjunto que se denomina conjunto cociente y se denota: \displaystyle X\backslash\sim=\{\hat{a}|a\in X\}
Si a, b \in X cumplen a \sim b, sus clases de equivalencia serán \hat{a} = \hat{b} y por tanto son el mismo elemento en X\backslash\sim
Si no se cumple la propiedad simétrica, puede cumplirse esta otra:
Una relación R reflexiva, antisimétrica y transitiva se denomina relación de orden, y es habitual denotarla mediante \leq; se dice que (X, \leq) es un conjunto ordenado. Con el mismo significado que a\leq b también se emplea b\geq a; si además de a\leq b queremos asegurar que a=b, se puede usar a < b \text{ o }b > a
En un conjunto ordenado, si siempre se cumple que a\leq b\text{ o }b\leq a, se denomina orden total; en otro caso nos encontramos ante un orden parcial
Cuando S es un subconjunto ordenado de X, decimos que x \in X es una cota superior de S si x \geq t para cualquier t \in S. Si existe a, la menor de las cotas superiores y se le llama supremo de S; si el supremo está en S, se dice que es el máximo de S
Cuando S es un subconjunto ordenado de X, decimos que x \in X es una cota inferior de S si x\geq t para cualquier \displaystyle t \in S. Si existe a, la mayor de las cotas inferiores y se le llama ínfimo de S; si el ínfimo está en S, se dice que es el mínimo de S
Un conjunto bien ordenado (o que cumple el principio de buena ordenación), es un conjunto ordenado tal que todo subconjunto no vacío tiene mínimo