Relaciones
Las relaciones relacionan dos o más conjuntos
Dados dos conjuntos X e Y, su producto cartesiano se denota como XxY={(x,y)∣x∈X,y∈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 R⊂XxX una relación en X, dónde (a,b)∈R se suele denotar aRb. Estas relaciones pueden cumplir las siguientes propiedades:
- Propiedad reflexiva cuando todos los a∈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 aRb⇒bRa)
- Propiedad transitiva si se cumple aRb y bRc entonces se ha de cumplir que aRc (se puede denotar de forma abreviada cómo aRb,aRc⇒aRc)
Una relación que cumpla estas tres propiedades se denomina relación de equivalencia. En lugar de utilizar R, para denotarlas se utiliza ∼
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 ∼, agrupamos cada elemento a∈R con todos los que están relacionados con él. De esta forma obtenemos para cada a el siguiente conjunto: a^={x∈X∣a∼x}. A este conjunto se le denomina clase de equivalencia de a
Si tenemos dos elementos a,b∈X, sus respectivas clases de equivalencia a^ y b^ son iguales (a^=b^) o disjuntas (a^∩b^=∅), 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: X\∼={a^∣a∈X}
Si a,b∈X cumplen a∼b, sus clases de equivalencia serán a^=b^ y por tanto son el mismo elemento en X\∼
Si no se cumple la propiedad simétrica, puede cumplirse esta otra:
Propiedad antisimétrica si se cumple aRb y bRa, debe cumplirse que a=b (se puede denotar de forma abreviada cómo aRb,bRa⇒a=b)
Una relación R reflexiva, antisimétrica y transitiva se denomina relación de orden, y es habitual denotarla mediante ≤; se dice que (X,≤) es un conjunto ordenado. Con el mismo significado que a≤b también se emplea b≥a; si además de a≤b queremos asegurar que a=b, se puede usar a<b o b>a
En un conjunto ordenado, si siempre se cumple que a≤b o b≤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∈X es una cota superior de S si x≥t para cualquier t∈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∈X es una cota inferior de S si x≥t para cualquier t∈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