Relaciones de orden y de equivalencia

Relaciones de orden y de equivalencia
ESTRUCTURA DISCRETA 1
UNIVERSIDAD FERMIN TORO
SAIA A

1. Rafael Brizuela
24307352
Estrucutra disctera I
Slideshare
relaciones de orden y de equivalencia
Introducción
A continuacion se presenta un resumen breve sobre relaciones de equivalencia y
relaciones de orden parcial, esto implica definir una relación y exponer sus
propiedades. El material elaborado por la Cátedra de Matemática de Universidad
ORT, se utiliza como referencia par a extraer conceptos e imágenes.

Definición de relación
”El concepto de relacion implica la idea de correspondencia entre los elementos de
dos conjuntos que forman parejas ordenadas” (Enciclopedia, 2011). Teniendo en
cuenta el concepto anteriormente expresado, veremos las relaciones binarias de un
conjunto en si mismo. nos centraremos en explicar sus propiedades y cómo
reconocerlas a través de las distintas formas de representación de una relación.
Tomemos un conjunto X no vacío, de allí surge que una relación es un subconjunto
del mismo. Estas serán relaciones binarias en el conjunto X. Existen cuatro formas de
representar una relación binaria: Extensión, Comprensión, Diagrama y Matricial. En
el primer caso, se muestra cada pareja de la relación, a través de pares ordenados.
Si lo expresamos por comprensión, se muestran todos los elementos del conjunto y
además, se determinan las condiciones que tendrán las parejas para pertenecer a la
relación. En el diagrama, se muestra la relación a través de vértices y aristas. Por
último, se representa a través de una matriz cuadrada dónde solo se ingresan unos
(cuando hay relación) y ceros (cuando no hay relación).
Por comprensión :
Sea C = {1,2,3}, tal que: (x,y) ∈R↔x≤y(x,y)∈R↔x≤y

Por extensión:
R = {(1,1), (1,2), (1,3) (2,2), (2,3), (3,3)}

Matricial:

2. Diagrama (grafo dirigido):



Para crear el diagrama, es necesario tener en cuenta:
• •
• Cuando un elemento está relacionado con sí mismo, se realiza un bucle
(también llamado lazo).
• •
• Se realiza una flecha cuando hay vínculo entre dos elementos. Por ejemplo si
tenemos (1,2) se representará: 1→21→2.
• •
• Si dos elementos no están relacionados, no se dibuja ninguna flecha.
En el dibujo que se muestra anteriormente, hay tres lazos indicados en cada vértice,
esto denota que existe la relación (1,1), (2,2) y (3,3). Además, quedan dibujadas las
aristas que salen de cada nodo, hacia el otro extremo de la relación. De esta forma,
el uno se relaciona con el dos y el tres, y el dos con el tres.
Propiedades
Una relación puede aplicar la propiedad: Reflexiva, Simétrica, Antisimétrica o
Transitiva.
• •
• Si es reflexiva, cada elemento se relaciona con sí mismo. Es posible
identificarla de tres maneras:
o –
o Si miramos la relación por extensión, veremos que se encuentran
expresados como: {(1,1), (2,2), (3,3)}.
o –
o En la matriz, se verifica mirando la diagonal principal: debe encontrarse
presente el número uno a lo largo de toda la diagonal.
o –

3. o Por último, mirando el diagrama, debe haber un bucle en cada vértice.
•

• •
• Si es simétrica, la relación de dos elementos, debe darse en ambos sentidos.
Es posible identificarla de tres maneras:
o –
o Si miramos la relación por extensión, debemos encontrar {(2,3), (3,2)}
o –
o En la matriz, podemos decir que Mr=MTMr=MT (matriz transpuesta).
o –
o Por último, mirando el diagrama, debemos encontrar que las aristas que
van de un punto a otro, se dirijan en ambos sentidos. Esto es:
dos⇌tres.dos⇌tres.
• •
• Si es antisimétrica, la relación de dos elementos, debe darse en un sólo
sentido. La única relación bilateral que se admite es si a=ba=b. Es posible
identificarla de tres maneras:
o –
o Si miramos la relación por extensión, encontramos por ejemplo: {(1,1),
(1,2), (2,2), (2,3), (3,3)}
o –
o En la matriz, podemos ver que Mr≠MTMr≠MT (matriz transpuesta).
o –
o Por último, mirando el diagrama, debemos encontrar que las aristas que
van de un punto a otro, se dirijan en un sólo sentido. Esto es:
dos→tres.dos→tres.
• •
• Si es transitiva, existe una relación entre a y b, y otra relación entre b y c, por
ende, a y c quedan relacionados. Es posible identificarla de tres maneras:
o –
o Si miramos la relación por extensión, encontramos por ejemplo: {(1,2),
(1,3), (2,3)}
o –

4. o La matriz, si la multiplicamos por sí misma, el resultado será menor o
igual a la matriz original
o –
o Por último, mirando el diagrama, vemos que las aristas hacen un
triángulo de esta forma:
(uno→dos),(dos→tres),(uno→tres).(uno→dos),(dos→tres),(uno→tres).


Relaciones de equivalencia y de orden parcial
Una vez que conocemos las propiedades, y además, sabemos reconocerlas,
podemos identificar cuándo una relación es de equivalencia, y cuándo es de orden
parcial. Decimos que se trata de una relación de equivalencia cuando cumple con las
siguientes propiedades:
• •
• Reflexiva
• •
• Simétrica
• •
• Transitiva

Por otro lado, una relación de orden parcial cumple con las siguientes propiedades:
• •
• Reflexiva
• •
• Antisimétrica
• •
• Transitiva

5. Grafos

Un grafo está compuesto por vértices y aristas. Estos son los elementos del conjunto,
y el par ordenado (a,b) respectivamente. El mismo se enmarca en una relación RR
de un conjunto no vacío. A su vez, decimos que es un grafo dirigido y está asociado
a la relación.
Un grafo dirigido (también llamado dígrafo), lo encontramos cuando a y b (donde
a≠ba≠b) pertenecen a una misma relación. Por lo tanto, a y b serán vértices, y estarán
unidos por una arista. Si la relación es sobre el mismo elemento, de la forma (a,a),
tenemos un bucle o lazo. Cuando encontramos un vértice que no tiene asociado
ninguna arista, lo llamaremos: vértice aislado.
Diagrama de Hasse
El Diagrama de Hasse, tiene como objetivo simplificar el dibujo de un grafo cuando la
relación es de orden. Por lo tanto, si tenemos un conjunto finito y una relación, el
diagrama de Hasse de esa relación es un grafo asociado con las siguientes
características:
• Se omiten los bucles
• Se omiten los atajos entre aristas consecutivas (no se muestra la transitividad)
• Se construye el diagrama ”desde abajo hacia arriba”

6. Elemento maximal y elemento minimal
Consideremos un conjunto no vacío y una relación de orden parcial:
o •
o El elemento maximal es aquel que no tiene ningún elemento del
conjunto que lo preceda. En el diagrama de Hasse, lo identificamos en
la parte superior.
o •
o El elemento minimal es aquel que no precede a ningún elemento del
conjunto. Si miramos en el diagrama, lo encontramos en la base.
Nota: Puede existir más de un elemento minimal/maximal, no son únicos.
Por ejemplo, en la figura anterior, el elemento minimal sería el 1 y los
maximales serían el 3 y 4.

7. Máximo y Mínimo
Consideremos un conjunto no vacío y una relación de orden parcial:
o •
o El máximo es aquel número mayor a los demás, pero debe estar
relacionado con todos los elementos del conjunto.
o •
o El mínimo es aquel número menor a los demás, pero debe estar
relacionado con todos los elementos del conjunto.
Nota: Mínimo y Máximo son números únicos; si todos los elementos estan
conectados, el maximo y minimo coincidira con el elemento maximal y minimal
Si miramos el ejemplo expresado anteriormente, podemos ver que el mínimo
es 1, pero sin embargo no hay máximo, dado que entre el 3 y el 4 no es posible
identificarlo.
Cota inferior, cota Superior, supremo e ínfimo
Consideremos un conjunto no vacío y una relación de orden parcial:
o •
o Cota Inferior: un elemento x del conjunto A es cota inferior del conjunto
B si existe un elemento b (donde (x,b) exista en la relación para todo b
perteneciente a B) que sea menor que él.
o •
o Cota Superior: un elemento x del conjunto A es cota superior del
conjunto B si existe un elemento b (donde (b,x) exista en la relación para
todo b perteneciente a B) que sea mayor que él.
o •
o Supremo:aquel elemento que es cota superior y a su vez, es la menor
de ellas.
o •
o Ínfimo: aquel elemento que es cota inferior y a su vez, es la mayor de
ellas.