Formulario de Algebra I Relaciones Definicin de relacin: Dominio de una relacin: Rango de una relacin: Relacin Inversa:

Relaciones

R A B = {( x, y ) / x A, y B} Dom[R] = {x A / ( x, y ) R} Rg[R] = {y B / (x, y ) R}R B A R 1 = {( y, x ) / (x, y ) R} R A B S B C S o R = {( x, y ) / y B ( x, y ) R ( y , z ) S }

Composicin de relaciones:

Propiedades de la composicin: Asociatividad:

(T o S ) o R = T o (S o R )Relacin Inversa:

(S o R )1 = R 1 o S 1Relaciones definidas

R es una relacin definida en A, R A 2 R A A R es una relacin definida en A, R P (A 2 )Propiedades de las relaciones definidas: R A2 Reflexividad: No reflexividad: Arreflexividad: Simetra: No simtrica:

R es reflexiva x : x A (x, x ) R R no es reflexiva x / x A ( x, x ) R R es arreflexiva x : x A ( x, x ) R R es simtrica xy A : ( x, y ) R ( y, x ) R R no es simtrica xy / ( x, y ) R ( y, x ) R

www.carlos-eduardo.webs.tl

1

Formulario de Algebra I Asimetra: Antisimetra: Transitividad: No transitividad: Atransitividad:

Relaciones

R es asimtrica xy : ( x, y ) R ( y, x ) R R es antisimtrica xy : ( x, y ) R ( y, x ) R x = y R es transitiva xyz : ( x, y ) R ( y, z ) R ( x, z ) R R no es transitiva xyz / ( x, y ) R ( y, z ) R ( x, z ) R R es atransitiva xyz : ( x, y ) R ( y, z ) R ( x, z ) R

Relaciones de Equivalencia (~) La relacin R A2 es de equivalencia en A, si y solo si cumple la: Reflexividad: Simetra: Transitividad:

x : x A x ~ x

xy : x ~ y y ~ x

xyz : x ~ y y ~ z x ~ z

Clases de equivalencia: Clase de equivalencia del elemento a A es el conjunto de todos los elementos de A equivalentes a a :

K a = {x A / x ~ a}Conjunto de ndices: Sea A un conjunto dotado de una relacin de equivalencia. Se denomina conjunto de ndices a un conjunto formado por los representantes de cada clase de equivalencia. Es decir:

I = {a A / K a es una clase de equivalencia en A}Conjunto cociente: El conjunto formado por las clases de equivalencia se llama conjunto cociente de A por la relacin de equivalencia, donde I es el conjunto de ndices:

A = {K u / u I } ~

www.carlos-eduardo.webs.tl

2

Formulario de Algebra I Particin de un conjunto:

Relaciones

Sean dos conjuntos A e I tales que, cualquiera que sea elemento u I , existe un subconjunto K u A . Entonces el conjunto {K u / u I } es una particin de A si y solo s: i. u : u I K u ii. iii.

u v Ku Kv = a A, u I / a K u

Relaciones de equivalencia definidas en un conjunto: Si ~ es una relacin de equivalencia definida en el conjunto A , entonces existe un subconjunto I A , tal que cualquiera que sea u en I , existe K u A : i. ii. iii. iv. v.

u I Ku a ~ a' a a' K u

Ku Kv Ku = Kv

u v Ku Kv a A, u I / a K u

Particin y relacin de equivalencia:

R A2 {K u / u I }: una particin de A (a, b ) R a b K uReflexibilidad: a A u I / a K u a a K u

Transitividad: (a, b ) R (b, c ) R a, b c K u a c K u (a, c ) R

Simetra: (a, b ) R a b K u b a K u (b, a ) R

Relaciones de Orden Orden Amplio: Sea R A2 , R es una relacin de orden amplio en A si y solo s cumple la: Reflexividad: Antisimetra: Transitividad:

a A (a, a ) R (a, b) R (b, a ) R a = b (a, b) R (b, c ) R (a, c ) R

www.carlos-eduardo.webs.tl

3

Formulario de Algebra I

Relaciones

Orden Parcial: Sea R una relacin de orden parcial de A existen pares de elementos incomparables:

a, b / (a, b ) R (b, a ) ROrden Total: Sea R una relacin de orden total de A no existen pares de elementos incomparables:

a b (a, b ) R (b, a ) ROrden Estricto: Sea R A2 , R es una relacin de orden estricto en A si y solo s cumple la: Arreflexividad: Asimtrica: Transitividad:

a A (a, a ) R (a, b) R (b, a ) R (a, b) R (b, c ) R (a, c ) R

El signo de preceder: Sea (a, b ) R y se puede igualmente denotar por aRb y con el signo de preceder a p b . Con esta notacin se tiene: - Reflexividad: - Antisimetra: - Transitividad: - Linealidad:

a A a p a a pbb p a a =b a pbb p c a p c a b a pbb p a

Relaciones Funcionales Sea R una relacin binaria que R A B , que es lo mismo decir de que R es una relacin o aplicacin de A en B : R : A B , Si R cumple dos condiciones: Condicin de Existencia: Condicin de Unicidad:

a A, b B / (a, b ) R (a, b) R (a, c ) R b = c

Se dice que esta relacin R que cumple estas dos condiciones, se llama Funcin, Aplicacin o Transformacin Lineal y se denota por f :

f :AB

www.carlos-eduardo.webs.tl

4