Relaciones De Equivalencia Y Relaciones De Orden 12u6t

Lenguaje matem´ atico, conjuntos y n´ umeros Cap´ıtulo 3 (Primera parte) Relaciones de equivalencia y relaciones de orden

Relaci´ on definida en un conjunto Una relaci´ on R en un conjunto U es cualquier subconjunto de U × U : R ⊂ U × U. Ejemplo Si U = {a, b, c, d} entonces R = {(a, a), (b, d), (c, c)} es una relaci´ on definida en U . t

d

t

c b a

t a

b

c

d

Propiedades b´ asicas de una relaci´ on Sea R definida en U . Propiedad reflexiva: Ejemplos • En el caso del conjunto U = {a, b, c, d}, la relaci´ on

∀x ∈ U

xRx

• En el conjunto de los tri´angulos del plano euclidiano la relaci´on “x es semejante a y” es reflexiva.

R = {(a, a), (a, b), (b, b), (b, d), (c, c), (d, d)}

es reflexiva. t

d

t t

c b

t

a

t a

t

b

c

d

• En el conjunto de los n´ umeros reales “x es menor o igual que y” es reflexiva.

Propiedades b´ asicas de una relaci´ on Sea R definida en U . Propiedad sim´ etrica:

∀x, y ∈ U

Ejemplos • En el conjunto U = {a, b, c, d} la relaci´ on R = {(a, a), (a, b), (b, a), (b, b), (d, d)}

si xRy entonces yRx

• En el conjunto de las rectas del plano euclidiano la relaci´on “x es paralela a y” es sim´etrica.

es sim´etrica. t

d c b

t

t

a

t

t

a

b

c

d

• En el conjunto de las rectas del plano euclidiano la relaci´on “x es perpendicular a y” es sim´etrica.

Propiedades b´ asicas de una relaci´ on Sea R definida en U . Propiedad antisim´ etrica: Ejemplos • En el conjunto U = {a, b, c, d} la relaci´ on R = {(a, a), (b, c), (d, b)}

es antisim´etrica.

t t

b a

t a

b

c

si xRy e yRx entonces x = y

• En el conjunto de los n´ umeros naturales la relaci´on “x divide a y” es antisim´etrica. • En el conjunto de los n´ umeros reales la relaci´on “x es menor o igual que y” es antisim´etrica.

d c

∀x, y ∈ U

d

Propiedades b´ asicas de una relaci´ on Sea R definida en U . Propiedad transitiva: ∀x, y, z ∈ U Ejemplos • En el conjunto U = {a, b, c, d} la relaci´ on R = {(a, a), (a, b), (a, c), (b, c), (d, d)}

es transitiva. t

d c

t

b

t

a

t a

t

b

c

d

si xRy e yRz entonces xRz

• En el conjunto de los n´ umeros naturales la relaci´on “x divide a y” es transitiva. • En el conjunto de las rectas del plano euclidiano la relaci´on “x es paralela a y” es transitiva.

Relaci´ on de equivalencia Se dice que una relaci´ on E definida en U es de equivalencia si cumple las tres propiedades siguientes: 1. P. Reflexiva:

∀x ∈ U

´trica: 2. P. Sime

∀x, y ∈ U

3. P. Transitiva:

∀x, y, z ∈ U

xEx. si xEy entonces yEx. si xEy e yEz entonces xRz.

Relaci´ on de equivalencia • En el conjunto de las rectas del plano euclidiano la relaci´on de paralelismo es una relaci´on de equiE = {(a, a), (b, b), (b, d), (c, c), (d, b), (d, d)} valencia. es una relaci´ on de equivalencia en U . • En el conjunto de los tri´angulos del plano euclidiano la relaci´on de semejanza es una relaci´on de t t d equivalencia. t c • En el conjunto de los vectores t t b fijos del plano o del espacio la relaci´ on de equipolencia es una t a relaci´ on de equivalencia.

Ejemplos • Si U = {a, b, c, d} entonces

a

b

c

d

Clases de equivalencia Dada una relaci´ on de equivalencia E en el conjunto U , se llama clase de equivalencia de x ∈ U al subconjunto de U formado por los elementos con los que x est´ a relacionado, lo denotamos por [x]. [x] = {y ∈ U | xEy} Ejemplo Las clases de equivalencia de la relaci´ on E = {(a, a), (b, b)(b, d), (c, c), (d, b), (d, d)} definida en U = {a, b, c, d} son: [a] = {a},

[b] = {b, d},

[c] = {c},

[d] = {b, d}.

1. Las clases de equivalencia de dos elementos relacionados coinciden, en este caso [b] = [d] = {b, d}. Y tanto b como d son representantes de la clase de equivalencia. 2. Las clases de equivalencia de dos elementos no relacionados son disjuntas. En este caso [a] ∩ [b] = ∅, [a] ∩ [c] = ∅, [b] ∩ [c] = ∅. 3. La uni´ on de las clases de equivalencia es el conjunto total U , en este caso {a} ∪ {b, d} ∪ {c} = {a, b, c, d} = U . Se dice que las clases de equivalencia constituyen una partici´ on de U , es decir, son disjuntas entre s´ı y su uni´ on es todo el conjunto. a c b U

d

Clases de equivalencia 4. Rec´ıprocamente, toda partici´ on del conjunto U , permite definir una relaci´ on de equivalencia E en el conjunto U : xEy si y s´ olo si {x, y} est´ a contenido en alg´ un subconjunto de la partici´ on. Ejemplo La partici´ on del conjunto U = {a, b, c, d} en los subconjuntos {a, c} y {b, d} a d

c b U

define la relaci´ on: E = {(a, a), (a, c), (c, a), (c, c), (b, b), (b, d), (d, b), (d, d)}. 5. Dada una relaci´ on de equivalencia E en el conjunto U , se denomina conjunto cociente, y se denota por U/E, al conjunto de todas las clases que genera la relaci´ on de equivalencia E. Ejemplo Dado el conjunto U = {a, b, c, d} con la relaci´ on de equivalencia E = {(a, a), (a, c), (c, a), (c, c), (b, b), (b, d), (d, b), (d, d)}, el conjunto cociente es U/E = {[a], [b]} ≡ {{a, c}, {b, d}}.

Relaci´ on de orden Se dice que una relaci´ on R definida en U es una relaci´ on de orden si cumple las tres propiedades siguientes: 1. P. Reflexiva:

∀x ∈ U

´trica: 2. P. Antisime 3. P. Transitiva:

xRx.

∀x, y ∈ U

∀x, y, z ∈ U

si xRy e yRx entonces x = y. si xRy e yRz entonces xRz.

Un conjunto ordenado (U, ) es un conjunto en el que se ha definido una relaci´ on de orden.

Relaci´ on de orden Ejemplos • Consideremos (R, ≤), (≤, menor o igual) . Para cualesquiera a, b, c ∈ R se verifica 1. a ≤ a 2. Si a ≤ b y b ≤ a entonces a = b 3. Si a ≤ b y b ≤ c entonces a ≤ c Se dice que es una relaci´ on de orden total: dados dos n´ umeros reales a y b siempre es posible decidir si “a es anterior a b” o “a es posterior a b” • En el conjunto de los naturales N∗ se define la relaci´ on divide: n|m si y s´ olo si ∃k ∈ N∗ tal que m = kn Es reflexiva; n = 1n. Es antisim´ etrica; si n = km y m = k0 n entonces n = kk0 n; y k = k0 = 1 y m=n Es transitiva; si n = km y m = k0 h entonces n = kk0 h. Esta es una relaci´ on de orden parcial, por ejemplo 2 y 3 no est´ an relacionados. Para esta relaci´ on de orden 2 no es anterior ni posterior a 3.

Intervalos en un conjunto ordenado Sea un conjunto ordenado (U, ), y a, b ∈ U tal que a b

Intervalo abierto (a, b) = {x ∈ U : a ≺ x ≺ b}

Intervalo cerrado [a, b] = {x ∈ U : a x b}

(

(a, b] = {a ≺ x b}

Intervalo semiabierto [a, b) = {a x ≺ b}

Orden lexicogr´ afico en R2 Con el orden usual en R, la relaci´ on definida en R2 : (a, b) 6L (c, d) si y s´ olo si (a < c) o (a = c y b 6 d) es una relaci´ on de orden total.

r(a, b)

r(a, b) r(c, d)

(x, y) 6L (a, b)

(a, b) 6L (x, y)

(a, b) 6L (x, y) 6L (c, d)

Orden producto en R2 La relaci´ on definida en R2 : (a, b) 6P (c, d) si y s´ olo si a 6 c y b 6 d ea una relaci´ on de orden parcial.

r

(c, d)

r

(a, b)

r

(a, b)

(x, y) 6P (a, b)

(a, b) 6P (x, y) (a, b) 6P (x, y) 6P (c, d)

Cotas en un conjunto ordenado Ejemplo Consideremos (R, ≤) y A1 = (2, 5), A2 = [2, 5), A3 = (2, 5] , A4 = [2, 5]. COTAS INFERIORES

COTAS SUPERIORES

c A1

2 ´ınfimo

m´ınimo

A2

2 ´ınfimo

c A3

A4

c 5 supremo

c 5 supremo

m´ aximo

2 ´ınfimo

5 supremo

m´ınimo

m´ aximo

2 ´ınfimo

5 supremo

Cotas en un conjunto ordenado Ejemplo Consideremos (R2 , 6L ) y sea el conjunto A = {(x, y) ∈ R2 | 1 ≤ x ≤ 2, 1 ≤ y < 2}

b (2, 2)

El punto (1, 1) es el ´ınfimo y el m´ınimo. El punto (2, 2) es el supremo pero no es el m´aximo del conjunto.

(1, 1)

6L

Cotas en un conjunto ordenado Ejemplo Consideremos (R2 , 6P ) y sea el conjunto A = {(x, y) ∈ R2 | 1 ≤ x ≤ 2, 1 ≤ y < 2}

b

(2, 2)

(1, 1)

6P

El punto (1, 1) es el ´ınfimo y el m´ınimo. El punto (2, 2) es el supremo pero no es el m´aximo del conjunto.

Cotas en un conjunto ordenado Ejemplo Consideremos (R2 , 6L ) y sea el conjunto B = {(x, y) ∈ R2 | 1 ≤ x ≤ 2, y = 1 o x = 1, 1 ≤ y < 2}

El punto (1, 1) es el ´ınfimo y el m´ınimo.

b (1, 2) r (2, 1)

(1, 1)

6L

El punto (2, 1) es el supremo y es el m´aximo del conjunto.

Cotas en un conjunto ordenado Ejemplo Consideremos (R2 , 6P ) y sea el conjunto B = {(x, y) ∈ R2 | 1 ≤ x ≤ 2, y = 1 o x = 1, 1 ≤ y < 2}

b

b

El punto (1, 1) es el ´ınfimo y el m´ınimo.

r

El punto (2, 2) es el supremo pero no es el m´aximo del conjunto.

(2, 2)

(1, 1)

6P

Cotas en un conjunto ordenado Ejemplo Consideremos (R2 , 6L ) y sea C = {(x, y) ∈ R2 |0 ≤ x, 0 ≤ y, x + y ≤ 1}

El punto (0, 0) es el ´ınfimo y el m´ınimo.

(0, 1)

El punto (1, 0) es el supremo y el m´aximo del conjunto. (0, 0)

(1, 0)

6L

Cotas en un conjunto ordenado Ejemplo Consideremos (R2 , 6P ) y sea C = {(x, y) ∈ R2 |0 ≤ x, 0 ≤ y, x + y ≤ 1}

El punto (0, 0) es el ´ınfimo y el m´ınimo. b

(0, 1)

(1, 1)

(1, 0) (0, 0)

6P

El punto (1, 0) es el supremo pero no es el m´aximo del conjunto. Los puntos del segmento que une (0, 1) con (1, 0) son elementos maximales del conjunto.

Cotas en un conjunto ordenado Ejemplo Se considera el conjunto de los naturales N∗ con la relaci´on n es anterior a m si n divide a m. Sea el conjunto A = {2, 3, 4, 5, 6, 7, 8, 9, 10} Minimales: 2, 3, 5, 7 (no tienen ning´ un elemento anterior) Maximales: 6, 7, 8, 9, 10 (no tienen ning´ un elemento posterior) Sea el conjunto B = {2, 4, 8, 16, 32, 64, 128} Minimal y m´ınimo: 2 Maximal y m´ aximo: 128

Cotas en un conjunto ordenado Ejemplo Consideremos (R2 , 6L ) y sea D = {(x, y) ∈ R2 | 1 ≤ x ≤ 2}

Un conjunto acotado puede no tener ni ´ınfimo y ni supremo. x=1

x=2

≤L