RELACION REFLEXIVA

Relación de equivalencia Artículo principal: Relación de equivalencia. Una relación binaria es una relación de equivalencia si es reflexiva, simétrica y transitiva:4 Dado un conjunto A, y una relación binaria R entre sus elementos R = \{ (a,b)\in \; A^2 : \quad R(a,b) \} Se dice que esta relación binaria es relación de equivalencia, si cumple: 1.- Relación reflexiva: la relación R es reflexiva si todo elemento a de A esta relacionado consigo mismo. \forall a \in A : \; (a,a) \in R 2.- Relación simétrica: la relación R es simétrica si un elemento a esta relacionado con otro b, entonces el b también esta relacionado con el a. \forall a, b \in A : \; (a,b) \in R \longrightarrow \quad (b,a) \in R 3.- Relación transitiva: la relación R es transitiva si un elemento a esta relacionado con otro b, y este b con otro c, entonces el elemento a esta también relacionado con el c. \forall a, b, c \in A : \; \Big ( (a,b) \in R \quad \land \quad (b,c) \in R \Big ) \longrightarrow \quad (a,c) \in R Una relación de equivalencia define dentro del conjunto A lo que se denominan, Clases de equivalencia, una clase de equivalencia o familia de elementos es cada uno de los subconjuntos en que la relación de equivalencia divide al conjunto A, entre ellos son disjuntos, y la unión de todos ellos es el conjunto A, veamos un ejemplo. En Aritmética modular se define la operación modulo como el resto de la división, así: 5 \mathit{\; M \acute{o} d \;} 2 = 1 6 \mathit{\; M \acute{o} d \;} 3 = 0 7 \mathit{\; M \acute{o} d \;} 3 = 1 el resto de dividir 5 entre 2 es 1 el resto de dividir 6 entre 3 es 0 el resto de dividir 7 entre 3 es 1 se dice que dos números son congruentes modulo n, si al dividir cada uno de esos números por n dan el mismo resto: 8 \equiv 17 \quad ( \mathit{ M \acute{o} d \;} 3) el 8 y el 17 son congruentes modulo 3 dado que al dividirlos por 3 en los dos casos dan por resto 2. La congruencia modular de grado n, de los números naturales, es una Relación de equivalencia, dado que es reflexiva: \forall a \in \N : \; a \equiv a \quad ( \mathit{ M \acute{o} d \;} n) es simétrica: \forall a, b \in \N : \; a \equiv b \quad ( \mathit{ M \acute{o} d \;} n) \longrightarrow \quad b \equiv a \quad ( \mathit{ M \acute{o} d \;} n) y es transitiva \forall a, b, c \in \N : \; \Big ( a \equiv b \quad ( \mathit{ M \acute{o} d \;} n) \quad \land \quad b \equiv c \quad ( \mathit{ M \acute{o} d \;} n) \Big ) \longrightarrow \longrightarrow \quad a \equiv c \quad ( \mathit{ M \acute{o} d \;} n) Conjunto parcialmente ordenado Artículo principal: Conjunto parcialmente ordenado. Un conjunto A se dice que esta parcialmente ordenado respecto a una relación binaria R si la relación R es reflexiva, transitiva y antisimétrica: Dado un conjunto A, y una relación binaria R entre sus elementos R = \{ (a,b)\in \; A^2 : \quad R(a,b) \} Se dice que esta relación binaria define un conjunto parcialmente ordenado, si cumple: 1.- Relación reflexiva: la relación R es reflexiva si todo elemento a de A esta relacionado consigo mismo. \forall a \in A : \; (a,a) \in R 2.- Relación transitiva: la relación R es transitiva si un elemento a esta relacionado con otro b, y este b con otro c, entonces el elemento a esta también relacionado con el c. \forall a, b, c \in A : \; \Big ( (a,b) \in R \quad \land \quad (b,c) \in R \Big ) \longrightarrow \quad (a,c) \in R 3.- Relación antisimétrica: la relación R es antisimétrica si los pares ordenado (a,b) y (b,a) pertenecen a la relación R , entonces a y b son iguales. \forall a,b \in A : \; \Big ( (a,b) \in R \quad \land \quad (b,a) \in R \Big ) \longrightarrow \quad a = b Tomando un conjunto A, formado, por ejemplo, por los elementos: A = \{ a, b, c \} \; Definimos el Conjunto potencia de A como el formado por todos los subconjuntos de A: P (A) = \Big\{ \{\}, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c \} \Big\} A cada uno de estos subconjuntos los llamamos: A_1 = \{ \} \; A_2 = \{a\} \; A_3 = \{b\} \; A_4 = \{c\} \; A_5 = \{a, b\} \; A_6 = \{a, c\} \; A_7 = \{b, c\} \; A_8 = \{a, b, c\} \; Y tomando dos de estos subconjuntos decimos que están relacionados por pertenencia si el primero es Subconjunto del segundo: R = \Big\{ (A_i , A_j )\in \; P (A) : \quad A_i \subset A_j \Big\} La relación pertenencia entre los conjuntos potencia de A, es un conjunto parcialmente ordenado, al ser reflexiva: \forall A_i \in P (A) : \; A_i \subset A_i Transitiva: \forall A_i, A_j, A_k \in P (A) : \; \Big ( A_i \subset A_j \quad \land \quad A_j \subset A_k \Big ) \longrightarrow \quad A_i \subset A_k Antisimetrica: \forall A_i, A_j \in P (A) : \; \Big ( A_i \subset A_j \quad \land \quad A_j \subset A_i \Big ) \longrightarrow \quad A_i = A_j Por lo que el conjunto de las partes de A, respecto a la relación binaria pertenencia es un conjunto parcialmente ordenado. Esta relación no es total dado que: \neg\forall (A_i, A_j) \in P (A) : \; A_i \subset A_j \quad \lor \quad A_j \subset A_i Que se denominan no comparables, los pares de conjuntos no comparables son: OrdenParcial.svg \Big( \{a\}, \{b\} \Big) \notin R ,\quad \{a\} \not\subset \{b\} \Big( \{a\}, \{c\} \Big) \notin R ,\quad \{a\} \not\subset \{c\} \Big( \{b\}, \{c\} \Big) \notin R ,\quad \{b\} \not\subset \{c\} \Big( \{a\}, \{b, c\} \Big) \notin R ,\quad \{a\} \not\subset \{b, c\} \Big( \{b\}, \{a, c\} \Big) \notin R ,\quad \{b\} \not\subset \{a, c\} \Big( \{c\}, \{a, b\} \Big) \notin R ,\quad \{c\} \not\subset \{a, b\} \Big( \{a, b\}, \{a, c\} \Big) \notin R ,\quad \{a, b\} \not\subset \{a, c\} \Big( \{a, b\}, \{b, c\} \Big) \notin R ,\quad \{a, b\} \not\subset \{b, c\} \Big( \{a, c\}, \{b, c\} \Big) \notin R ,\quad \{a, c\} \not\subset \{b, c\} A la vista del diagrama, los conjuntos que se pueden alcanzar siguiendo el sentido de las flechas se denominan comparables y determinan la estructura del orden parcial. Orden total Artículo principal: Orden total. Un conjunto A se dice que esta totalmente ordenado respecto a una relación binaria R si la relación R es reflexiva, transitiva, antisimétrica y total: Dado un conjunto A, y una relación binaria R entre sus elementos R = \{ (a,b)\in \; A^2 : \quad R(a,b) \} Se dice que esta relación binaria define un orden total, si cumple: 1.- Relación reflexiva: la relación R es reflexiva si todo elemento a de A esta relacionado consigo mismo. \forall a \in A : \; (a,a) \in R 2.- Relación transitiva: la relación R es transitiva si un elemento a esta relacionado con otro b, y este b con otro c, entonces el elemento a esta también relacionado con el c. \forall a, b, c \in A : \; \Big ( (a,b) \in R \quad \land \quad (b,c) \in R \Big ) \longrightarrow \quad (a,c) \in R 3.- Relación antisimétrica: la relación R es antisimétrica si los pares ordenado (a,b) y (b,a) pertenecen a la relación R , entonces a y b son iguales. \forall a,b \in A : \; \Big ( (a,b) \in R \quad \land \quad (b,a) \in R \Big ) \longrightarrow \quad a = b 4.- Relación total: la relación R es total si para cualquiera dos elemento del conjunto: a, b; o a esta relacionado con b ó bien b esta relacionado con a. \forall a, b \in A : \; (a,b) \in R \quad \lor \quad (b,a) \in R Si tomamos el conjunto de los números enteros Z, por ejemplo, respecto a la relación binaria entre sus elementos menor o igual, podemos ver que es reflexiva: \forall a \in \Z : \; a \le a es transitiva: \forall a, b, c \in \Z : \; \Big ( a \le b \quad \land \quad b \le c \Big ) \longrightarrow \quad a \le c es antisimetrica: \forall a,b \in \Z : \; \Big ( a \le b \quad \land \quad b \le a \Big ) \longrightarrow \quad a = b y es total: \forall a, b \in \Z : \; a \le b \quad \lor \quad b \le a Conjunto bien ordenado Artículo principal: Conjunto bien ordenado. Dado un conjunto A y una relación R, entre los elementos de ese conjunto, se dice que es un conjunto bien ordenado si cumple: Dado un conjunto A, y una relación binaria R entre sus elementos R = \{ (a,b)\in \; A^2 : \quad R(a,b) \} Se dice que esta relación binaria define un conjunto bien ordenado, si cumple: 1.- Relación reflexiva: la relación R es reflexiva si todo elemento a de A esta relacionado consigo mismo. \forall a \in A : \; (a,a) \in R 2.- Relación transitiva: la relación R es transitiva si un elemento a esta relacionado con otro b, y este b con otro c, entonces el elemento a esta también relacionado con el c. \forall a, b, c \in A : \; \Big ( (a,b) \in R \quad \land \quad (b,c) \in R \Big ) \longrightarrow \quad (a,c) \in R 3.- Relación antisimétrica: la relación R es antisimétrica si los pares ordenado (a,b) y (b,a) pertenecen a la relación R , entonces a y b son iguales. \forall a,b \in A : \; \Big ( (a,b) \in R \quad \land \quad (b,a) \in R \Big ) \longrightarrow \quad a = b 4.- Relación total: la relación R es total si para cualquiera dos elemento del conjunto: a, b; o a esta relacionado con b ó bien b esta relacionado con a. \forall a, b \in A : \; (a,b) \in R \quad \lor \quad (b,a) \in R 5.- Relación bien fundada: dado un conjunto A y una relación R, entre los elementos de ese conjunto, esta relación se dice bien fundada, si pata todo subconjunto B de A se cumple que existe un m en B tal que para todo b de B, distinto de m, el par ordenado (b,m) no pertenece a R. \forall B \subset A \; , \quad \exists m \in B \; : \quad \forall b \in B \; \land \; b \ne m \; : \quad (b,m) \notin R