Matemáticas Discretas TC1003 Relaciones entre Conjuntos: Propiedades Departamento de Matemáticas / Centro de Sistema Inteligentes

ITESM

Relaciones entre Conjuntos: Propiedades

Matemáticas Discretas - p. 1/23

Representación Alternativa para Relaciones Sea A un conjunto y R una relación de A en A. En este caso diremos que R es una relación sobre A o una relación en A.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 2/23

Representación Alternativa para Relaciones Sea A un conjunto y R una relación de A en A. En este caso diremos que R es una relación sobre A o una relación en A. Alternativamente al diagrama de flechas del conjunto hacia si mismo:

a

a

a

b

b

b

c

c

c

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 2/23

Ejemplo

Si A = {1, 2, 3, 4} y R = {(1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (4, 1)} dibuje el diagrama de flechas de las relación.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 3/23

Ejemplo

Si A = {1, 2, 3, 4} y R = {(1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (4, 1)} dibuje el diagrama de flechas de las relación. ´ Solucion

1

2

4

3

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 3/23

Relación Reflexiva ´ Definicion

Sean A un conjunto y R una relación. Se dice que

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 4/23

Relación Reflexiva ´ Definicion

Sean A un conjunto y R una relación. Se dice que ■ R es reflexiva si : ∀x, (x ∈ A → (x, x) ∈ R).

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 4/23

Relación Reflexiva ´ Definicion

Sean A un conjunto y R una relación. Se dice que ■ R es reflexiva si : ∀x, (x ∈ A → (x, x) ∈ R). Es decir, toda relación que sea reflexiva debe tener al menos n flechas (suponiendo que n es el número de elementos de A):

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 4/23

Relación Reflexiva ´ Definicion

Sean A un conjunto y R una relación. Se dice que ■ R es reflexiva si : ∀x, (x ∈ A → (x, x) ∈ R). Es decir, toda relación que sea reflexiva debe tener al menos n flechas (suponiendo que n es el número de elementos de A): deben estar todas las parejas (a, a) donde a barre todos los elementos de A.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 4/23

Ejemplos

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 5/23

Ejemplos

1

2

4

3

Relación no Reflexiva

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 5/23

Ejemplos

1

2

1

2

4

3

4

3

Relación no Reflexiva

Relaciones entre Conjuntos: Propiedades

Relación Reflexiva

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 5/23

Ejemplos

1

2

1

2

4

3

4

3

Relación no Reflexiva

Relación Reflexiva

Cada nodo debe tener un cíclo.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 5/23

Ejemplos

De acuerdo a la mtriz de adyacencia de una relación:     1 ··· 1 ···  .. . .   ..   .   . 1  .         ... 0     ... 1 Relación No reflexiva Relación Reflexiva

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 6/23

Ejemplos

De acuerdo a la mtriz de adyacencia de una relación:     1 ··· 1 ···  .. . .   ..   .   . 1  .         ... 0     ... 1 Relación No reflexiva Relación Reflexiva En la diagonal principal debe haber sólo unos para relaciones reflexivas.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 6/23

Ejemplos

De acuerdo a la mtriz de adyacencia de una relación:     1 ··· 1 ···  .. . .   ..   .   . 1  .         ... 0     ... 1 Relación No reflexiva Relación Reflexiva En la diagonal principal debe haber sólo unos para relaciones reflexivas. En las no reflexivas hay al menos un cero.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 6/23

Relación Simétrica ´ Definicion

Sean A un conjunto y R una relación.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 7/23

Relación Simétrica ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es simétrica si

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 7/23

Relación Simétrica ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es simétrica si ∀x, y, ((x, y) ∈ R → (y, x) ∈ R).

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 7/23

Relación Simétrica ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es simétrica si ∀x, y, ((x, y) ∈ R → (y, x) ∈ R). Que no nos engañe la implicación: no dice que tengamos flechas de x a y para todo x y y:

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 7/23

Relación Simétrica ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es simétrica si ∀x, y, ((x, y) ∈ R → (y, x) ∈ R). Que no nos engañe la implicación: no dice que tengamos flechas de x a y para todo x y y: Dice que en caso de haber una flecha de x a y debemos de tener una de y a x en las relaciones simétricas.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 7/23

Ejemplos

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 8/23

Ejemplos

1

2

4

3

Relación no simétrica

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 8/23

Ejemplos

1

2

1

2

4

3

4

3

Relación no simétrica

Relaciones entre Conjuntos: Propiedades

Relación Simétrica

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 8/23

Relación Antisimétrica ´ Definicion

Sean A un conjunto y R una relación.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 9/23

Relación Antisimétrica ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es antisimétrica si

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 9/23

Relación Antisimétrica ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es antisimétrica si ∀x, y, ((x, y) ∈ R ∧ (y, x) ∈ R → x = y).

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 9/23

Relación Antisimétrica ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es antisimétrica si ∀x, y, ((x, y) ∈ R ∧ (y, x) ∈ R → x = y). Cuando están las parejas (x, y) y (y, x) en la relación, es porque las parejas son (x, x).

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 9/23

Ejemplos

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 10/23

Ejemplos

1

2

4

3

Relación no Antisimétrica

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 10/23

Ejemplos

1

2

1

2

4

3

4

3

Relación no Antisimétrica

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Relación Antisimétrica

Matemáticas Discretas - p. 10/23

Relación Transitiva ´ Definicion

Sean A un conjunto y R una relación.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 11/23

Relación Transitiva ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es transitiva si

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 11/23

Relación Transitiva ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es transitiva si ∀x, y, z, ((x, y) ∈ R ∧ (y, z) ∈ R → (x, z) ∈ R).

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 11/23

Ejemplos

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 12/23

Ejemplos

1

2

4

3

Relación no Transitiva

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 12/23

Ejemplos

1

2

1

2

4

3

4

3

Relación no Transitiva

Relaciones entre Conjuntos: Propiedades

Relación Transitiva

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 12/23

Relación de Equivalencia ´ Definicion

Sean A un conjunto y R una relación.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 13/23

Relación de Equivalencia ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es una relación de equivalencia si

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 13/23

Relación de Equivalencia ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es una relación de equivalencia si R es reflexiva, simétrica y transitiva.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 13/23

Ejemplos

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 14/23

Ejemplos

1

2

4

3

Relación no de Equivalencia

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 14/23

Ejemplos

1

2

1

2

4

3

4

3

Relación no de Equivalencia

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Relación de Equivalencia

Matemáticas Discretas - p. 14/23

Relación de Orden Parcial ´ Definicion

Sean A un conjunto y R una relación.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 15/23

Relación de Orden Parcial ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es una relación de orden parcial si

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 15/23

Relación de Orden Parcial ´ Definicion

Sean A un conjunto y R una relación. Se dice que R es una relación de orden parcial si R es reflexiva, antisimétrica y transitiva.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 15/23

Ejemplos

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 16/23

Ejemplos

1

2

4

3

Relación que no es Orden Parcial

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 16/23

Ejemplos

1

2

1

2

4

3

4

3

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Relación que no es Orden Parcial Relación de Orden Parcial

Relaciones entre Conjuntos: Propiedades

Matemáticas Discretas - p. 16/23

Ejemplo

Considere el conjunto A = {1, 2, 3} y la relación: R=

(

(2, 2) , (2, 3) , (1, 1) , (3, 3)

(1, 2) ,

)

Indique cuáles propiedades tiene la relación.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 17/23

Ejemplo

Indica cuáles de las siguientes son relaciones de equivalencia: 1. mod5 en los enteros 2. La relación vecinos en los paises 3. Primos en una familia 4. ≥ en los enteros

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 18/23

Cerradura Transitiva de una Relación ´ Definicion

Sean A un conjunto y R una relación. La cerradura transitiva de R es una relación R0 que cumple:

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 19/23

Cerradura Transitiva de una Relación ´ Definicion

Sean A un conjunto y R una relación. La cerradura transitiva de R es una relación R0 que cumple: ■ R0 es transitiva,

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 19/23

Cerradura Transitiva de una Relación ´ Definicion

Sean A un conjunto y R una relación. La cerradura transitiva de R es una relación R0 que cumple: ■ R0 es transitiva, ■ R ⊆ R0 (R0 contiene a R), y

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 19/23

Cerradura Transitiva de una Relación ´ Definicion

Sean A un conjunto y R una relación. La cerradura transitiva de R es una relación R0 que cumple: ■ R0 es transitiva, ■ R ⊆ R0 (R0 contiene a R), y ■ Cualquier otra relación transitiva que contiene a R también contiene a R0 .

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 19/23

Cerradura Transitiva de una Relación ´ Definicion

Sean A un conjunto y R una relación. La cerradura transitiva de R es una relación R0 que cumple: ■ R0 es transitiva, ■ R ⊆ R0 (R0 contiene a R), y ■ Cualquier otra relación transitiva que contiene a R también contiene a R0 . Es decir, la cerradura transitiva de una relación R es la más pequeña relación transitiva que contiene a R.

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 19/23

Ejemplos

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 20/23

Ejemplos

1

2

4

3 Relación

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 20/23

Ejemplos

1

2

1

2

4

3

4

3

Relación

Relaciones entre Conjuntos: Propiedades

Cerradura Transitiva

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 20/23

Ejemplos

1

2

1

2

4

3

4

3

Relación

Cerradura Transitiva

Cuidado: A veces hace falta una segunda pasada para revisar si ya es transitiva. Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 20/23

Considere el conjunto A = {1, 2, 3} y la relación sobre A: ( (1, 1) , (1, 2) , R= (2, 1) , (2, 2) ,

(1, 3) , (3, 3)

)

Sólo de la siguiente lista indique cuáles parejas deben aãdirse a R en la cerradura transitiva: 1. (2, 3) 2. (3, 1) 3. (3, 2)

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 21/23

Partición de un Conjunto ´ Definicion

Sea A un conjunto no vacío. Una partición para A es una colección de subconjuntos de A, A1 , A2 ,. . . ,Am tal que

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 22/23

Partición de un Conjunto ´ Definicion

Sea A un conjunto no vacío. Una partición para A es una colección de subconjuntos de A, A1 , A2 ,. . . ,Am tal que ■ Ningún subconjunto Ai es vacío: ∀i, Ai 6= ∅

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 22/23

Partición de un Conjunto ´ Definicion

Sea A un conjunto no vacío. Una partición para A es una colección de subconjuntos de A, A1 , A2 ,. . . ,Am tal que ■ Ningún subconjunto Ai es vacío: ∀i, Ai 6= ∅ ■

Los conjuntos no tienen elemento en común: ∀i, j, (i 6= j → Ai ∩ Aj = ∅)

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 22/23

Partición de un Conjunto ´ Definicion

Sea A un conjunto no vacío. Una partición para A es una colección de subconjuntos de A, A1 , A2 ,. . . ,Am tal que ■ Ningún subconjunto Ai es vacío: ∀i, Ai 6= ∅ ■

Los conjuntos no tienen elemento en común: ∀i, j, (i 6= j → Ai ∩ Aj = ∅)

■

La unión de los conjuntos es igual a A: A1 ∪ A2 ∪ · · · ∪ Am = A

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 22/23

Ejemplo

Indica cuáles de las siguientes son particiones del conjunto: {1, 3, {5, 2}, 4} 1. 2. 3. 4.

{∅, {1, 3, {5, 2}, 4}} {{1}, {3, {5, 2}, 4}} {{{1, 3}}, {5, 2}, {4}} {{1}, {3}, {{5, 2}}, {4}}

Relaciones entre Conjuntos: Propiedades

´ Representacion Ejemplo 1 Reflexiva Ejemplo 2 Ejemplo 3 Simetr´ıa Ejemplo 3 Antisimetr´ıa Ejemplo 4 Transitividad Ejemplo 5 Equivalencia Ejemplo 6 Orden Parcial Ejemplo 7 Ejemplo 8 Ejemplo 9 Cerradura Ejemplo 10 Ejemplo 11 ´ Particion Ejemplo 12

Matemáticas Discretas - p. 23/23