Formulario de Relaciones

Formulario de Algebra I Relaciones
Relaciones
Definición de relación: R ⊂ A × B = {( x, y ) / x ∈ A, y ∈ B}
Dominio de una relación: Dom[R] = {x ∈ A / ( x, y ) ∈ R}
Rango de una relación: Rg[R] = {y ∈ B / (x, y ) ∈ R}
Relación Inversa: R ⊂ B× A
R −1 = {( y, x ) / (x, y ) ∈ R}
Composición de relaciones: R ⊂ A× B ∧ S ⊂ B × C
S o R = {( x, y ) / ∃ y ∈ B ∧ ( x, y ) ∈ R ∧ ( y , z ) ∈ S }
Propiedades de la composición:
- Asociatividad:
(T o S ) o R = T o (S o R )
- Relación Inversa:
(S o R )−1 = R −1 o S −1
Relaciones definidas
R es una relación definida en A, ⇔ R ⊂ A 2 ∨ R ⊂ A × A
R es una relación definida en A, ⇔ R ∈ P (A 2 )
Propiedades de las relaciones definidas: R ⊂ A2
- Reflexividad: R es reflexiva ⇔ ∀x : x ∈ A ⇒ (x, x ) ∈ R
- No reflexividad: R no es reflexiva ⇔ ∃x / x ∈ A ∧ ( x, x ) ∉ R
- Arreflexividad: R es arreflexiva ⇔ ∀x : x ∈ A ⇒ ( x, x ) ∉ R
- Simetría: R es simétrica ⇔ ∀x∀y ∈ A : ( x, y ) ∈ R ⇒ ( y, x ) ∈ R
- No simétrica: R no es simétrica ⇔ ∃x∃y / ( x, y ) ∈ R ∧ ( y, x ) ∉ R
www.carlos-eduardo.webs.tl 1
- Asimetría: R es asimétrica ⇔ ∀x∀y : ( x, y ) ∈ R ⇒ ( y, x ) ∉ R
- Antisimetría: R es antisimétrica ⇔ ∀x∀y : ( x, y ) ∈ R ∧ ( y, x ) ∈ R ⇒ x = y
- Transitividad: R es transitiva ⇔ ∀x∀y∀z : ( x, y ) ∈ R ∧ ( y, z ) ∈ R ⇒ ( x, z ) ∈ R
- No transitividad: R no es transitiva ⇔ ∃x∃y∃z / ( x, y ) ∈ R ∧ ( y, z ) ∈ R ⇒ ( x, z ) ∉ R
- Atransitividad: R es atransitiva ⇔ ∀x∀y∀z : ( x, y ) ∈ R ∧ ( y, z ) ∈ R ⇒ ( x, z ) ∉ R
Relaciones de Equivalencia (~)
La relación R ⊂ A2 es de equivalencia en A, si y solo si cumple la:
- Reflexividad: ∀x : x ∈ A ⇒ x ~ x
- Simetría: ∀x∀y : x ~ y ⇒ y ~ x
- Transitividad: ∀x∀y∀z : 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 relación 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
relación de equivalencia, donde I es el conjunto de índices:
A
= {K u / u ∈ I }
~
Partición de un conjunto:
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 partición de A si y
solo sí:
i. ∀u : u ∈ I ⇒ K u ≠ Ø
ii. u ≠ v ⇒ Ku ∩ Kv = Ø
iii. ∀a ∈ A, ∃ u ∈ I / a ∈ K u
Relaciones de equivalencia definidas en un conjunto:
Si ~ es una relación 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. u ∈ I ⇒ Ku ≠ Ø
ii. a ~ a' ⇔ a ∧ a' ∈ K u
iii. Ku ∩ Kv ≠ Ø ⇒ Ku = Kv
iv. u ≠ v ⇒ Ku ∩ Kv ≠ Ø
v. ∀a ∈ A, ∃ u ∈ I / a ∈ K u
Partición y relación de equivalencia:
R ⊂ A2
{K u / u ∈ I }: una partición de A
(a, b ) ∈ R ⇔ a ∧ b ∈ K u
- Reflexibilidad: a ∈ A ⇒ ∃ u ∈ I / a ∈ K u ⇒ a ∧ a ∈ K u
- Simetría: (a, b ) ∈ R ⇒ a ∧ b ∈ K u ⇒ b ∧ a ∈ K u ⇒ (b, a ) ∈ R
- Transitividad: (a, b ) ∈ R ∧ (b, c ) ∈ R ⇒ a, b ∧ c ∈ K u ⇒ a ∧ c ∈ K u ⇒ (a, c ) ∈ R
Relaciones de Orden
Orden Amplio: Sea R ⊂ A2 , R es una relación de orden amplio en A si y solo sí cumple la:
- Reflexividad: a ∈ A ⇒ (a, a ) ∈ R
- Antisimetría: (a, b) ∈ R ∧ (b, a ) ∈ R ⇒ a = b
- Transitividad: (a, b) ∈ R ∧ (b, c ) ∈ R ⇒ (a, c ) ∈ R
Orden Parcial: Sea R una relación de orden parcial de A ⇔ existen pares de elementos
incomparables:
∃ a, ∃ b / (a, b ) ∉ R ∧ (b, a ) ∉ R
Orden Total: Sea R una relación de orden total de A ⇔ no existen pares de elementos
incomparables:
a ≠ b ⇒ (a, b ) ∈ R ∨ (b, a ) ∈ R
Orden Estricto: Sea R ⊂ A2 , R es una relación de orden estricto en A si y solo sí cumple

la:
- Arreflexividad: a ∈ A ⇒ (a, a ) ∉ R
- Asimétrica: (a, b) ∈ R ⇒ (b, a ) ∉ R
- Transitividad: (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 notación se tiene:
- Reflexividad: a∈ A⇒ a p a
- Antisimetría: a pb∧b p a ⇒ a =b
- Transitividad: a pb∧b p c ⇒ a p c
- Linealidad: a ≠ b⇒ a pb∨b p a
Relaciones Funcionales
Sea R una relación binaria que R ⊆ A × B , que es lo mismo decir de que R es una relación o
aplicación de A en B : R : A → B ,
Si R cumple dos condiciones:
- Condición de Existencia: ∀a ∈ A, ∃ b ∈ B / (a, b ) ∈ R

- Condición de Unicidad: (a, b) ∈ R ∧ (a, c ) ∈ R ⇒ b = c
Se dice que esta relación R que cumple estas dos condiciones, se llama Función,
Aplicación o Transformación Lineal y se denota por f :
f :A→B

Formulario de Relaciones

Cargado por

Copyright:

Formatos disponibles

Formulario de Relaciones

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Formulario de Relaciones

Cargado por

Copyright:

Formatos disponibles

Formulario de Algebra I Relaciones

Dominio de una relación: Dom[R] = {x ∈ A / ( x, y ) ∈ R}

Rango de una relación: Rg[R] = {y ∈ B / (x, y ) ∈ R}

R es una relación definida en A, ⇔ R ⊂ A 2 ∨ R ⊂ A × A

R es una relación definida en A, ⇔ R ∈ P (A 2 )

Propiedades de las relaciones definidas: R ⊂ A2

- Reflexividad: R es reflexiva ⇔ ∀x : x ∈ A ⇒ (x, x ) ∈ R

- Simetría: R es simétrica ⇔ ∀x∀y ∈ A : ( x, y ) ∈ R ⇒ ( y, x ) ∈ R

- No simétrica: R no es simétrica ⇔ ∃x∃y / ( x, y ) ∈ R ∧ ( y, x ) ∉ R

- Asimetría: R es asimétrica ⇔ ∀x∀y : ( x, y ) ∈ R ⇒ ( y, x ) ∉ R

- Antisimetría: R es antisimétrica ⇔ ∀x∀y : ( x, y ) ∈ R ∧ ( y, x ) ∈ R ⇒ x = y

- Transitividad: R es transitiva ⇔ ∀x∀y∀z : ( x, y ) ∈ R ∧ ( y, z ) ∈ R ⇒ ( x, z ) ∈ R

- No transitividad: R no es transitiva ⇔ ∃x∃y∃z / ( x, y ) ∈ R ∧ ( y, z ) ∈ R ⇒ ( x, z ) ∉ R

- Atransitividad: R es atransitiva ⇔ ∀x∀y∀z : ( x, y ) ∈ R ∧ ( y, z ) ∈ R ⇒ ( x, z ) ∉ R

Relaciones de Equivalencia (~)

La relación R ⊂ A2 es de equivalencia en A, si y solo si cumple la:

Clase de equivalencia del elemento a ∈ A es el conjunto de todos los elementos de A

Sea A ≠ φ un conjunto dotado de una relación de equivalencia. Se denomina conjunto de

I = {a ∈ A / K a es una clase de equivalencia en A}

Relaciones de equivalencia definidas en un conjunto:

Si ~ es una relación de equivalencia definida en el conjunto A ≠ Ø, entonces existe un

Partición y relación de equivalencia:

Orden Estricto: Sea R ⊂ A2 , R es una relación de orden estricto en A si y solo sí cumple

Si R cumple dos condiciones:

- Condición de Existencia: ∀a ∈ A, ∃ b ∈ B / (a, b ) ∈ R

También podría gustarte