2.8: Resumen

Template:MathJaxZach

Una relación$R$ sobre un conjunto$A$ es una forma de relacionar elementos de$A$. Escribimos$Rxy$ si la relación se mantiene entre$x$ y$y$. Formalmente, podemos considerar$R$ como los conjuntos de pares$\tuple{x,y} \in A^2$ tal que$Rxy$. Ser menor que, mayor que, igual a, dividiendo uniformemente, siendo la misma longitud que, un subconjunto de, y el mismo tamaño que todos son ejemplos importantes de relaciones (en conjuntos de números, cadenas, o de conjuntos). Las gráficas son una forma general de representar visualmente las relaciones. Pero una gráfica también puede verse como una relación binaria (la relación de borde) junto con el conjunto subyacente de vértices.

Algunas relaciones comparten ciertas características que las hacen especialmente interesantes o útiles. Una relación$R$ es reflexiva si todo está$R$ relacionado consigo mismo; simétrica, si con$Rxy$ también se$Ryx$ sostiene para cualquiera$x$ y$y$; y transitiva si $Rxy$y$Ryz$ garantías$Rxz$. Las relaciones que tienen estas tres propiedades son relaciones de equivalencia. Una relación es antisimétrica si$Rxy$ y$Ryx$ garantías$x=y$. Los órdenes parciales son aquellas relaciones reflexivas, antisimétricas y transitivas. Un orden lineal es cualquier orden parcial que satisfaga eso para cualquiera$x$ y$y$, ya sea$Rxy$ o$x=y$ o$Ryx$. (Generalmente, una relación con esta propiedad está conectada).

Dado que las relaciones son conjuntos (de pares), pueden operarse como conjuntos (por ejemplo, podemos formar la unión e intersección de relaciones). También podemos encadenarlos (producto relativo$R \mid S$). Si formamos el producto relativo de$R$ consigo mismo arbitrariamente muchas veces obtenemos el cierre transitivo$R^+$ de$R$.