Relaciones

Definición

Definimos $R$ como una relación en $A$ si $R\subseteq A\times A$, utilizando el producto cartesiano. Por ejemplo, sea $A=\{1,2,3\}$. Podremos definir una relación $R_1=\{(1,1),(1,2),(3,3)\}$.

Existen dos formas para denotar que un par de elemento pertenece a una relación.

$$(1,2)\in R_1$$ $$1R_{1}2$$

Para representar una relación, también podremos utilizar una matriz de adyacencia, con la cantidad de elementos de $A$ como tamaño.

$$A_{R_1}=\left(\begin{array}{ccc}1& 1& 0\\ 0& 0& 0\\ 0& 0& 1\end{array}\right)$$

Otra forma de representar la relación es graficando el conjunto y señalando con flechas las relaciones entre los objetos.

La flecha parte del primer elemento del par, y llega al segundo elemento del par.

stateDiagram
1 --> 1
1 --> 2
3 --> 3

Cuando una relación es reflexiva, antisimétrica y transitiva, se llama relación de orden.

El conjunto donde se ha introducido esa relación se llama conjunto ordenado.

1. Reflexiva: $\forall a\in A:aRa$
2. Antisimétrica: $\forall a,b\in A:(aRb,bRa)\to a=b$
3. Transitiva: $\forall a,b,c\in A:(aRb,bRc)\to aRc$

Se dice que $(a,R)$ es un conjunto parcialmente ordenado, o es poset. De ahora en más, se utilizará el símbolo $\le$ para representar una relación de orden. $aRb=a\le b$

Se dice orden parcial, ya que no todos los elementos están en relación entre sí. La relación solo está presente para un subconjunto de los elementos. $a\nleqq b$ no implica $a\ge b$.

Diagrama de Hasse

Sea $A=\{1,2,3\}$, en $P(a)$ (todos los subconjuntos de $A$) se define la relación de orden $\subseteq$.

El diagrama de Hasse ordena los elementos de un conjunto de forma ascendente, uniéndolos con una arista si son sucesores inmediatos.

graph LR
  0["{}"]--> 1["{1}"] & 2["{2}"] & 3["{3}"]
  1 & 2 --> 12["{1,2}"]
  1 & 3 --> 13["{1,3}"]
  2 & 3 --> 23["{2,3}"]
  12 & 13 & 23 --> 123["{1,2,3}"]

Relación Inversa

Definimos $R^{-1}$ como el conjunto de las relaciones de $R$ invertidas. Entonces:

$$R^{-1}=\{(x,y)\in A^2:yRx\}$$ $$xRy⟺y{R}^{-1}x$$

El opuesto de $R$, define aquellas relaciones que no pertenecen a $R$. Podemos definirla como:

$$R^{\prime }=A^2-R$$

Analizando las representaciones matriciales, tendremos

$$A_{R^{\prime }}=J-A_R$$ $$A_R^T=A_{R^{-1}}$$

Composición de Relación

Sean $S,T$ dos relaciones del conjunto $A$. Entonces definiremos la relación $R=S\circ T$ para la cual:

$$xRy⟺\exists z:xSz,zTy$$

graph LR
  subgraph A
		x
  end

	subgraph B
		z
  end
	subgraph C
		y
  end
	A -->|S| B -->|T| C
  A -->|R| C

Propiedades de Relación

En una relación, se pueden presentar las siguientes propiedades independientes, siendo $R$ una relación en el conjunto $A$.

• Reflexiva: $\forall x\in A:xRx$
• Irreflexiva: $\forall x\in A:x{R}^{\prime }x$
• Simétrica: $\forall x,y\in A:xRy⟺yRx$
• Antisimétrica: $\forall x,y\in A:(xRy,yRx)⟹x=y$
• Asimétrica: $\forall x,y\in A:xRy⟹y{R}^{\prime }x$
• Transitiva: $\forall x,y,z\in A:(xRy,yRz)⟹xRz$
• Anti transitiva: $\forall x,y,z\in A:(xRy,yRz)⟹x{R}^{\prime }z$

Transitividad

Sean $S,T$ relaciones en $A$, entonces si definamos $R=S\circ T$, hallamos que, con el producto matricial binario:

$$A_S{A}_B=A_R$$

Para demostrarlo, utilizaremos la definición del producto matricial binario.

$$\begin{array}{c}{A}_S{A}_T(i,j)=1\stackrel{\text{ def. del producto}}{\iff }\\ \sum _{k=1}^n{A}_S(i,k)A_T(k,j)=0\stackrel{\text{ por ser binario}}{\iff }\\ \exists k:A_S(i,k)=1\wedge A_T(k,j)=1\stackrel{\text{ definicioˊn de forma matricial}}{\iff }\\ \exists k:a_{i}S{a}_k\wedge a_{k}T{a}_j\stackrel{\text{ definicioˊn de composicioˊn}}{\iff }\\ a_{i}R{a}_j\stackrel{\text{ definicion de forma matricial}}{\iff }\\ A_R(i,j)=1\end{array}$$

Por definición, $R\circ R$ es transitiva, entonces $R$ es transitiva si y solo si $R\circ R\subset R$. Otra forma de expresarlo sería $A_R^2\le A_R$.

Operaciones en Matrices

Sean $A,B\in {\mathbb{R}}^{n\times m}$ entonces:

• Orden: $A\le B⟺A(i,j)\le B(i,j),\forall i,j$
• Producto Hadamard: $(A\odot B)(i,j)=A(i,j)B(i,j),\forall i,j$

Clausuras

Sea $P$ una propiedad de relación $R$, entonces sea $S$ una relación particular, la $P\text{-clausura}$ de $S$ es otra relación $H\supset S$ que tiene la propiedad $P$ y es minimal respecto a todas las que contienen a $S$.

Puede generarse la clausura añadiendo uno a uno las relaciones necesarias, recalculando en cada paso.

Relaciones de equivalencia

Una relación de equivalencia es una relación que cumple simultáneamente las propiedades: reflexiva, simétrica y transitiva.

graph TD
	subgraph A
    subgraph ca ["[a]"]
			a <--> b
			a --> a
      b --> b
    end
		subgraph cc ["[c]"]
	    c --> c
		end
		subgraph cd ["[e]"]
	    e <--> d & f
      d <--> f
      e --> e
      d --> d
      f --> f
		end
	end

Podemos ver que al introducir una relación de equivalencia en un conjunto, formaremos pequeños clústeres aislados en el conjunto, de modo que cualquier elemento de un clúster está en relación todos los elementos del mismo clúster, y con ningún elemento fuera del clúster

Definición

Sea $a\in A$, La clase de $a$ se denomina $[a]=\{x\in A:aRx\}$. Normalmente, se elige un representante de cada clase.

Las clases no son vacías, esto es inmediato debido a la reflexividad.

Dos clases distintas son disjuntas, si un elemento pertenece a más de una clase, entonces debido a la transitividad y la reflexividad estas clases se juntarían.

La relación de equivalencia introduce una partición de clases, coloquialmente conocida como partición. Todos los elementos están en por lo menos una clase y las clases son disjuntas.

Definición

Definimos $A/R$ como el conjunto de clases de $A$ bajo la relación de equivalencia de $R$. $A/R=\{[a]:a\in A\}$