asdas

Lecci´on 6
Relaciones
Contenido
6.1 Generalidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
6.1.1 Relaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.1.2 Igualdad de Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.2 Relaciones Binarias . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 132
6.2.1 Dominio e Imagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.3 Matriz de una Relaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.3.1 Definici´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.4 Grafo Dirigido de una Relaci´on . . . . . . . . . . . . . . . . . . . . . . .. . . 136
6.4.1 Definici´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
6.4.2 Representaci´on Gr´afica de un Grafo Dirigido . . . . . . . . . . . . . . . . . . . 136
6.5 Propiedades de las Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.5.1 Reflexividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1386.5.2 Simetr´ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6.5.3 Asimetr´ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.5.4 Antisimetr´ıa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
6.5.5 Transitividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
Lasmatem´aticas aparecen como la ciencia que estudia las relaciones entre ciertos objetos abstractos.
Emile Borel
En esta lecci´on estudiaremos algunas estructuras b´asicas que pueden representarse a trav´es de la relaci´on
entre elementos de conjuntos. Las relaciones tienen una importancia fundamental tanto en la teor´ıa como
en las aplicaciones a la inform´atica.
Una estructura de datos talescomo una lista, una matriz o un ´arbol, se usan para representar conjuntos
de elementos junto con una relaci´on entre los mismos.
Las relaciones que son parte de un modelo matem´atico est´an a menudo impl´ıcitamente representadas por
relaciones en una estructura de datos.
Aplicaciones num´ericas, recuperaci´on de informaci´on y problemas de redes son algunos ejemplos donde
las relacionesocurren como parte de la descripci´on del problema, y la manipulaci´on de relaciones es
importante en la resoluci´on de procedimientos.
Las relaciones tambi´en juegan un importante papel en la teor´ıa de computaci´on, incluyendo estructuras
de programas y an´alisis de algoritmos.
131Universidad de C´adiz Departamento de Matem´aticas
En esta lecci´on desarrollaremos algunas de las herramientasfundamentales y los conceptos asociados a
las relaciones.
6.1 Generalidades
Hemos estudiado ya dos relaciones importantes entre proposiciones: la implicaci´on y la equivalencia.
Tambi´en hemos estudiado la relaci´on de subconjunto para conjuntos. En ´algebra y c´alculo son importantes las relaciones entre variables; en geometr´ıa lo son las relaciones entre figuras. Hasta el momento
no hemosnecesitado una definici´on precisa de la palabra relaci´on. Sin embargo, sin una definici´on formal
es dif´ıcil responder preguntas sobre relaciones. ¿Qu´e se quiere dar a entender, por ejemplo, cuando se
dice que dos relaciones aparentemente diferentes son iguales?
En la realidad que nos circunda existen relaciones entre elementos, entre conjuntos y entre elementos y
conjuntos. Existenrelaciones de parentesco, de amistad, de paisanaje, etc., entre personas; relaciones
diplom´aticas, econ´omicas, etc., entre pa´ıses; relaciones de paralelismo o de perpendicularidad entre rectas
de un plano; relaciones de inclusi´on entre conjuntos; relaciones como “mayor que” o “menor o igual que”
entre n´umeros, etc. La matem´atica intenta, como ahora veremos, hacerse eco de tales sucesos y,...