relaciones binarias

Relaciones binarias
Definici´n 1. Llamaremos relaci´n binaria R en un conjunto A a una
o
o
relaci´n de A en A, es decir un subconjunto de A × A.
o
De forma an´loga se definen las relacionesn–arias como los subconjuntos
a
del producto cartesiano A × . . . × A = An.
Ejemplo 1. Dado A = {1, 2, 3, 4} la relaci´n
o
R = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 1), (4, 2)}
se puederepresentar mediante un grafo dirigido
1

2

4

I. Fortes, J. Medina. Dpto. Matem´tica Aplicada
a

3

1

Relaci´n identidad: Sobre un conjunto A denotaremos por I a la relaci´n
o
o
binariaaI b ⇔ a = b
En ocasiones especificaremos el conjunto como sub´
ındice IA.
Una relaci´n binaria R ⊆ A × A se dice que es
o
Reflexiva: si para cada a ∈ A, aRa
Sim´trica: si para cada a, b ∈ A, aRb⇒ bRa
e
Antisim´trica: si para cada a, b ∈ A, aRb y bRa ⇒ a = b
e
Transitiva: si para cada a, b, c ∈ A, aRb y bRc ⇒ aRc
Relaci´n de equivalencia:
o

Reflexiva

Sim´trica
e


TransitivaI. Fortes, J. Medina. Dpto. Matem´tica Aplicada
a

Relaci´n de orden:
o

Reflexiva

Antisim´trica
e


Transitiva

2

Ejemplo 2.
Sobre el conjunto A = Z × Z∗ la relaci´nbinaria
o
(a, b)R(c, d) ⇔ ad = bc es de equivalencia
En A = Z+ la relaci´n binaria a | b es de orden
o
Definici´n 2. Dada R en A se define
o
R0 = I
para todo n ∈ N, Rn+1 = R ◦ Rn
Si R est´ definidasobre un conjunto finito, entonces generalizamos las
a
potencias de la matriz asociada del siguiente modo
M (R0) = In
Si k ∈ Z+, M (Rk) = M (R)

M ((Rk−1)

Se representar´ de la siguiente formaa
M (Rn) = M (R)n
I. Fortes, J. Medina. Dpto. Matem´tica Aplicada
a

3

Relaci´n de conectividad: Dada R en A, construimos R∞ como sigue
o
aR∞b ⇔ ∃n ∈ Z+ | aRnb
Teorema 1. Si R es unarelaci´n binaria, entonces
o
∞

R∞ =

Rn
n=1

I. Fortes, J. Medina. Dpto. Matem´tica Aplicada
a

4

Otras definiciones

|A| = n < ∞
R reflexiva

I⊆R

In ≤ M (R)

R sim´trica
e...