Recordatorio de Relaciones y Funciones Dr. Felipe Orihuela-Espina

Recordatorio deRelaciones y Funciones

Dr. Felipe Orihuela-Espina

Contenido

Relaciones Propiedades de las relaciones Clases de equivalencia Conjuntos parcial y totalmente ordenados Funciones Tipos de funciones

(c) 2013-5. Dr. Felipe Orihuela-Espina 2


RELACIONES

Relaciones

Una relación (n-aria) R es un subconjunto del producto cartesiano de n conjuntos A1x…xAn. R⊆ A1x…xAn Ai se denominan los dominios de la relación A n se le denomina el grado de la relación, y se

cumple que n≥0.

R consiste de un conjunto de n-tuplas ordenadas, tal que el i-ésimo elemento de la tupla proviene del conjunto Ai. R={(a11,a21,a31),…}



Relaciones

Ejemplo: R=AxBxC

A B C

R{ , , }

{ , , }

{ , , }

Relaciones

Ejemplo: Supongamos los conjuntos: Alumno={Juan, María, Pepe, Luis, Pedro} Profesor={Santiago, Pilar, Pablo, Rosa} Asignatura={Matemáticas, Lengua, Filosofía} Horario={10am, 11am, 12pm, 13pm}

La relación 4-aria Rcurso se define sobre los dominios anteriores: Rcurso ={(Juan, Santiago, Lengua, 11am), …}


Relaciones

En particular, una relación binaria (n=2) R de un conjunto A a otro conjunto B es un subconjunto del producto cartesiano AxB (R⊆AxB) tal que si los elementos a∊A y b∊B están relacionados entonces (a,b)∊R Esto lo se denota ARB en el caso de referirse a la

relación de los conjuntos, o aRb en el caso de referirse a la relación de los elementos y se lee “A/a está relacionado con B/b”

A se denomina el conjunto dominio o inicio B se denomina el conjunto codominio o destino

Si los “dos” conjuntos son el mismo, i.e. A=B, entonces se dice que R es una relación binaria sobre A.


Relaciones

Ejemplo: Relacion “divisible por” (resto 0) Sea el conjunto A={2,3,4,5,6,7,8} Sea la relación binaria sobre A, R/

Entonces: R/ ={(x,y)∈AxA | mod(y,x)=0}

= {(2,2), (2,4), (2,6), (2,8), (3,3), (3,6), (4,4), (4,8),(5,5), (6,6), (7,7),(8,8)}


Ejemplo corregido de: [http://www.youtube.com/watch?v=h34hZ_hynzE]

Relaciones

Ejemplo: Relacion “cuadrado de” Sea el conjunto A={R} de los números reales Sea la relación binaria sobre A, R^2

Entonces: R^2 ={(x,y)∈ R2 | y=x2}


Relaciones

Ejemplo: Relacion “menor que” Sea el conjunto A={1,2,3,4} Sea la relación binaria sobre A, R<

Entonces: R< ={(x,y)∈AxA | x<y}

= {(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)}


Ejemplo de: [http://www.youtube.com/watch?v=h34hZ_hynzE]

☞ Más adelante, veremos que esta relación cumple que es una relación de orden o simplemente un orden (es decir que tiene las propiedades reflexiva, antisimétrica y transitiva).

Relaciones

Sean dos conjuntos B={b1, …, bn} y C={c1, …, cm} y la relación R⊆BxC.

Se denomina matriz de adyacencia AR a la matriz* de tamaño nxm cuyas filas indexan a B y sus columnas indexan a C de tal forma que:


* Una matriz se define como un vector de rango 2 (relación binaria). Un vector se define como un conjunto de elementos estructurados en sólidos rectangulares. Estructurados significa que el conjunto está dotado de una estructura algebraica. Una estructura algebraica es un conjunto de operaciones (relaciones de tipo función –a lo sumo 1 imagen por cada elemento del dominio- sobre el conjunto potencia).

Relaciones

Ejemplo: Matriz de adyacencia


Figura de [http://commons.wikimedia.org/wiki/Category:Relations_%28mathematics%29]

Relaciones

A partir de la matriz de adyacencia es fácil definir/dibujar un grafo* que represente la relación:


a b

c d

Figuras de la matriz de adyacencia: [Wikipedia]Figuras de los grafos: [Elaboración propia]

* Sea V un conjunto de elementos que se denominan nodos. Sea E una relación (binaria) sobre V, E:VxV, donde a cada elemento de E se denomina arista. Un grafo G es una relación E, aunque por conveniencia normalmente se indica de forma explícita el conjunto de nodos; G=<V,E>.

Relaciones

Sea R=SxT una relación del conjunto S al conjunto T S seria el dominio T sería el codominio

Para cada elemento s∈S podemos definir el conjunto: [s]R={t∈T | (s,t)∈R}

A este se le conoce como el conjunto imagen de s, o sea, los 1s de la fila s en la matriz de adyancencia. …y se denota más comúnmente como R(s): R(s)=[s]R


Relaciones

Sea R=SxT una relación del conjunto S al conjunto T. S seria el dominio T sería el codominio

De igual forma, para cada elemento t∈T podemos definir el conjunto: [t] R={s∈S | (s,t)∈R}

A este se le conoce como el conjunto pre-imagen de t. o sea, los 1s de la columna t en la matriz de adyancencia ☞ No tenemos un símbolo especial para denotar a este

conjunto, aunque en determinadas circunstancias coincide con R-1.


PROPIEDADES DE LAS RELACIONES


Propiedades de las relaciones

Una relación binaria sobre A es: Reflexiva si ∀x∈A ⇒ xRx, léase (x,x)∈R Irreflexiva si ∀x∈A ⇒ (x,x)∉R Transitiva si xRy e yRz ⇒ xRz Simétrica si xRy ⇔ yRx Antisimétrica si xRy e yRx ⇒ x=y


* El cuantificador universal “Para todo” (∀) es como no, una relación. ¿Te atreves a formalizarla?

Relaciones

Observa que para que sea reflexiva, toda la diagonal principal debe tener 1s en la matriz de adyacencia,

…o de forma equivalente en el grafo todos los nodos deben tener flechas hacia si mismos:


a b

c d

a b

c d

Reflexivo No Reflexivo

Figuras de la matriz de adyacencia: [Wikipedia]Figuras de los grafos: [Elaboración propia]

Relaciones

Observa que para que sea irreflexiva, ningún elemento de diagonal principal debe tener 1s en la matriz de adyacencia,

…o de forma equivalente en el grafo ningún nodo deben tener flechas hacia si mismo:


a b

c dFiguras de la matriz de adyacencia: [Wikipedia]Figuras de los grafos: [Elaboración propia]

Relaciones

Observa que para que la relación sea simétrica, la matriz de adyacencia debe ser simétrica*,

…o de forma equivalente en el grafo todos los enlaces deben ser bidireccionales:


a b

c d

Simétrica

Figuras de los grafos: [ambas elaboración propia]

* Aún no he definido simetría en matrices, pero por ahora, baste decir que una matriz (cuadrada) es simétrica si para aij=aji, i,j i∀ j


Ejemplo: La relación binaria R< sobre A es: ¿Reflexiva?: No, ya que para ningún x∈A

⇒ xRx ¿Irreflexiva?: Si, ya que para todo x∈A ⇒

x≮x ¿Transitiva?: Si, ya que si x<y e y<z ⇒

x<z ¿Simétrica?: No, ya que si x<y entonces

y≮x ¿Antisimétrica?: No, ya que no es

posible que x<y e y<x a la vez(c) 2013-5. Dr. Felipe Orihuela-Espina 21


Ejemplo: La relación binaria R≤ sobre A es: Reflexiva: Si, ya que para todo x∈A ⇒ x≤x Irreflexiva: No, ya que para todo x∈A ⇒

x≤x Transitiva: Si, ya que si x≤y e y≤z ⇒ x≤z Simétrica: No, ya que si x≤y entonces

no necesariamente y≤x Antisimétrica: Si, ya que si x≤y e y≤x a

la vez, entonces x=y


CLASES DE EQUIVALENCIA


Clases de equivalencia

Una relación R sobre un conjunto S se dice que es una relación de equivalencia si y sólo si posee las siguientes propiedades: Reflexiva Simétrica, y Transitiva



Ejemplo: La relación binaria R= sobre A es: Reflexiva: Si, ya que para todo x∈A ⇒ x=x Transitiva: Si, ya que si x=y e y=z ⇒ x=z Simétrica: Si, ya que si x=y entonces

y=x

…por ende; la relación “igual que” es una relación de equivalencia.


Ejemplo: La relación R de rectas paralelas en el plano es una relación de equivalencia: Reflexiva: Si, ya que

para toda x∈A ⇒ x||x

Transitiva: Si, ya que si x||y e y||z ⇒ x||z

Simétrica: Si, ya que si x||y entonces y||x (c) 2013-5. Dr. Felipe Orihuela-Espina 26


Figura de: [mathsmadness.wikispaces.com]

¡Cuidado! Este símbolo es también el que se usa para denotar

elementos no comparables!...pero no confundas abuso de notación

con ambigüedad


Sea R una relación de equivalencia del conjunto S al conjunto T.

El conjunto imagen de s en esta relación de equivalencia: [s]R=R(s)={t∈T | (s,t)∈R}

Al conjunto imagen de s en una relación de equivalencia se le conoce como la clase de equivalencia de s, y se denota s~t. [s]R=R(s)={t∈T | s~t}



Bajo una relación de equivalencia sobre el conjunto S, se cumple que:

Si b [a]∈ R entonces [b]R=[a]R

En otras palabras, bajo una relación de equivalencia, si a y b están relacionados entonces son equivalentes.



Una relación de equivalencia particiona el conjunto S en clases de equivalencia mutuamente excluyentes o disjuntas. ☞ A veces verás que a la partición misma también se le

llama la clase de equivalencia. Observa que no es una ambigüedad, ¡estrictamente es lo mismo!

Definir las clases de equivalencia permite definir a continuación: operaciones sobre estas clases de equivalencia usando

representantes individuales de cada clases de equivalencia.

Nuevos conjuntos a partir de los ya definidos



Ejemplo: Supongamos un conjunto S={1,2,3,4,5} con la siguiente relación: [x]={y∈S | x~y} ={(1,1), (1,2), (1,3), (2,1),

(2,2), (2,3), (3,1), (3,2), (3,3),(4,4),(5,5)}

Podemos comprobar que la relación es: Reflexiva Simétrica, y Transitiva

Y por ende es una relación de equivalencia


1 2 3 4 51 x x x2 x x x3 x x x4 x5 x


Ejemplo (Cont.): Supongamos un conjunto S={1,2,3,4,5} con la siguiente relación: [x]={y∈S | x~y} ={(1,1), (1,2), (1,3), (2,1), (2,2),

(2,3), (3,1), (3,2), (3,3),(4,4),(5,5)}

Si es una relación de equivalencia, podemos establecer las clases de equivalencia: [s]R=R(s)={t∈T | s~t}

En particular [1]R={1,2,3} [3]R={1,2,3} [5]R={5}

[2]R={1,2,3} [4]R={4}


Observa que elementos

equivalentes, tienen clases de equivalencia

iguales


Ejemplo: La relación R entre los números racionales R={(x,y)∈ Q2 | y=kx ; k∈R-{0}} es una relación de equivalencia*: Reflexiva: Si, ya que para

toda x∈Q ⇒ x=kx, basta que k=1∈R.

Transitiva: Si, ya que si x=k1y e y=k2z ⇒ x=k3 z, con k3=k1k2 ∈R

Simétrica: Si, ya que si x=ky entonces y=(1/k)x y 1/k∈R. Observa que k no puede ser

0.

Ejemplo: ½=2/4=3/6=… 1/3=2/6=3/9=… …

Cada una de estas forma una clase de equivalencia en R.


* Estrictamente se debe exigir además que el denominador del número racional sea distinto de 0.



☞ Aunque no la definiré aquí, una relación de equivalencia importante y muy útil es la que podemos definir entre los puntos de un espacio, y los vectores. Esta relación, una vez definida, permite

operar con vectores como si fuesen puntos en un espacio (o viceversa, según lo quieras entender) y es la base de todo el cálculo vectorial.

CONJUNTOS PARCIAL Y TOTALMENTE ORDENADOS


Conjuntos parcialmente y totalmente ordenados

Una relación R ( )⊑ sobre un conjunto S se dice que es un orden o relación de orden si posee las siguientes propiedades: Reflexiva Antisimétrica, y Transitiva

Al par del conjunto S con su relación de orden , (S, )⊑ ⊑ se le llama conjunto parcialmente ordenado, o poset.



Sean dos elementos x,y (S∈ ,⊑): Se dice que x e y son comparables si x y⊑ o

y x⊑ Si x e y son comparables entonces la relación es

un orden lineal o total. Un conjunto con un orden total es un conjunto

totalmente ordenado. O sea, un conjunto parcialmente ordenado donde todos

los pares de elementos son comparables.

Se dice que x e y no son comparables si x y⋢ y y x⋢



Implicaciones: Si ⊑ es un orden sobre el conjunto S,

entonces el grafo asociado es un grafo acíclico (no contiene

ciclos de longitud mayor a 1).

S contiene un elemento máximo y un mínimo …pero no tienen que ser únicos, …ni tienen que existir

Ejemplo: ( ,ℝ ≤)


Diagrama de Hasse: Representación gráfica

simplificada de un conjunto parcialmente ordenado finito.

Cada elemento del conjunto se indica como un punto. Se dibujan aristas entre los

elementos del conjunto y sus predecesores inmediatos

…si y sólo si solo si uno sigue a otro sin haber otros elementos intermedios.



Figura de: [http://es.wikipedia.org/wiki/Diagrama_de_Hasse]

FUNCIONES



Funciones Función matemática: Una relación que asocia miembros (subconjunto) de un

conjunto origen con miembros de otro conjunto destino. En ambos conjuntos puede haber miembros no asociados pero, para aquellos

miembros de A para los que existe una relación, esa es una relación única. PERO: En aquellos elementos de A para los que no existe una relación se dice que la función

no está definida, y formalmente esos elementos NO pertenecen al dominio …de hecho, a veces, se indica que la función requiere que CADA elemento de A tenga una

imagen.

Del mismo miembro origen no pueden salir más de una relación. Miembros del conjunto destino sin embargo, si pueden recibir varias relaciones.A B

* Las definiciones formales las podéis encontrar en libros, o en Wolfram World of Maths [http://mathworld.wolfram.com/]

Funciones

Al conjunto de elementos del conjunto A para los que está definida la función se le conoce como dominio. dominio ⊆ A

Al conjunto de elementos del conjunto B que la función puede producir se le conoce como rango. rango ⊆ B B sigue siendo conocido como codominio


Funciones

Todas las funciones son relaciones, pero no al revés.


Tabla de: [http://www.purplemath.com/modules/fcns.htm]*Observa que el último ejemplo en esta web (omitido aquí) es erróneo; está marcado como no función, pero si es una función!

Funciones

Ejemplo: Estas NO son funciones


[www.mathsisfun.com]

[www.mathcaptain.com]

[en.wikipedia.org]

TIPOS DE FUNCIONES


Tipos de funciones

Inyectiva (o uno-a-uno): Cada elemento del conjunto codominio es cómo máximo la imagen de un único elemento del dominio En otras palabras, dos elementos no pueden tener la misma imagen.

Sobreyectiva: Cada elemento del codominio tiene al menos una preimagen En otras palabras, la imagen es el codominio completo; rango=B

Biyectiva: Inyectiva + Sobreyectiva

☞ El término uno-a-uno estrictamente describe a las funciones inyectivas [Cameron PJ (2006) Notes on Algebraic Structures]. No obstante, ya que las biyectivas también son inyectivas, muchas veces vereis que a estas también se las denomina funciones uno-a-uno.



Tipos de funciones

Formalmente [Cameron PJ (2006) Notes on Algebraic Structures]:

Inyectiva: a1a2 f(a1)f(a2) Alternativamente, también verás a veces [ Brin

(2011) Modern Algebra]; a1,a2: f(a1)=f(a2) a1=a2

Sobreyectiva: b:a tal que b=f(a)

Biyectiva: Inyectiva y sobreyectiva.

Tipos de funciones

Ejemplo: Inyectiva y no sobreyectiva


Ejemplo de: [http://en.wikipedia.org/wiki/Injective_function]

Tipos de funciones

Ejemplo: No inyectiva pero sobreyectiva



Tipos de funciones

Ejemplo: Inyectiva y sobreyectiva (biyectiva)



GRACIAS, ¿PREGUNTAS?


Documents

Recordatorio de Relaciones y Funciones Dr. Felipe Orihuela-Espina