araceli guzm an y guillermo garro · 2017. 8. 1. · carmen g omez laveaga. algebra superior ,...

Relaciones y funciones

Algebra

Araceli Guzman y Guillermo Garro

Facultad de CienciasUNAM

Semestre 2018-1

doyouwantmektalwar.wordpress.com

Relaciones y funciones Algebra

Relaciones y funciones

Los conceptos de relacion y funcion son, sin duda alguna, de los mas importantes dentrode las matematicas modernas. La mayor parte de la investigacion en matematicas secentra en el estudio de relaciones y funciones, por lo cual, no ha de sorprender que estosconceptos sean de una gran generalidad. Hausdorff consideraba que el concepto defuncion es casi tan primitivo como el de conjunto, y que decir del concepto de relacion,el cual intuitivamente parece mas esencial que el de funcion.

Fernando Hernandez, Teorıa de conjuntos.

Referencias

1. Antonio Lascurain, Algebra Superior, 2011. Bajar aquı.

2. Carmen Gomez Laveaga. Algebra Superior, 2016. Bajar aquı.

3. A. Bravo, H. Rincon y C. Rincon. Algebra superior, 2014. Bajar aquı.

Araceli Guzman y Guillermo Garro doyouwantmektalwar.wordpress.com Facultad de Ciencias UNAM

https://drive.google.com/open?id=0B12efZWbDYZbLUNQOTFYTF8yeXc

https://www.freelibros.org/algebra/algebra-superior-curso-completo-carmen-gomez-laveaga.html

https://www.scribd.com/document/249209475/Algebra-Superior-Bravo-Rincon-Rincon


Pares ordenadas. Producto cartesiano

Sean A y B conjuntos. Si a ∈ A y b ∈ B, entonces el par ordenado de a y b es elconjunto

(a, b) := {{a}, {a, b}} ∈ ℘(℘(A ∪B)).

El producto cartesiano de A y B es el conjunto A × B de todos los pares ordenados(a, b) tales que a ∈ A y b ∈ B.

Si A = B, entonces escribimos A2 en lugar de A×A.

Ejemplo

Sean A = {1, 2, 3} y B = {a, b}.

A×B = {(a, b) : a ∈ A ∧ b ∈ B}= {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}.

Note que (1, a) ∈ A×B, pero (1, a) /∈ A×B. El orden sı importa!



Ejemplo

Sean los intervalos cerrados de numeros reales:

[a, b] = {x ∈ R : a ≤ x ≤ b} y [c, d] := {x ∈ R : c ≤ x ≤ d}.

El producto cartesiano [a, b]× [c, d] tiene una representacion geometrica tıpica



Ejemplo

Sea A := {x ∈ R : |x| < 1}. Note que

|x| < 1 ⇔ −1 < x < 1.

De modo que A es el intervalo abierto (−1, 1).

La representacion geometrica del producto cartesiano

A× R = {(x, y) : −1 < x < 1 ∧ y ∈ R}

tiene tambien una representacion geometrica tıpica.



El plano cartesiano R2

El producto cartesiano R2 := R×R es el conjunto de todas las parejas ordenadas (x, y)tales que x ∈ R y y ∈ R



La propiedad mas importante de las parejas ordenadas

Teorema : El orden sı importa

Sean A y B conjuntos. Para todos a, c ∈ A y para todos b, d ∈ B,

(a, b) = (c, d) si y solo si a = c y b = d.

Demostracion.

[⇒] Supongamos que (a, b) = (c, d). Luego, por definicion

(a, b) = {{a}, {a, b}} = {{c}, {c, d}} = (c, d).

Por el principio de extension, hay dos casos, a saber,

Caso I: {a} = {c} y {a, b} = {c, d}.

Caso II: {a} = {c, d} y {a, b} = {c}.

En cualquier caso, a = c y b = d.

Caso I: {a} = {c} y {a, b} = {c, d}.

{a} = {c} ⇒ a = c,

∴ {a, b} = {a, d} ⇒ b ∈ {a, d} y d ∈ {a, b}⇒ a = b y en cuyo caso a = b = c = d,

o bien, b = d (y ya sabemos que a = c).

Caso II: {a} = {c, d} y {a, b} = {c}.

{a} = {c, d} ⇒ a = c = d

{a, b} = {c} ⇒ a = b = c.

De donde, obviamente, a = c y c = d.

[⇐] Trivial.Araceli Guzman y Guillermo Garro doyouwantmektalwar.wordpress.com Facultad de Ciencias UNAM


La propiedad mas importante de las parejas ordenadas

Teorema : El orden sı importa

Sean A y B conjuntos. Para todos a, c ∈ A y para todos b, d ∈ B,

(a, b) = (c, d) si y solo si a = c y b = d.

Demostracion.

[⇒] Supongamos que (a, b) = (c, d). Luego, por definicion

(a, b) = {{a}, {a, b}} = {{c}, {c, d}} = (c, d).

Por el principio de extension, hay dos casos, a saber,

Caso I: {a} = {c} y {a, b} = {c, d}.

Caso II: {a} = {c, d} y {a, b} = {c}.

En cualquier caso, a = c y b = d.

[⇐] Trivial.



Relaciones

Una relacion entre los conjuntos A y B, es cualquier subconjunto del producto cartesianoA×B. Si R ⊂ A×B y (a, b) ∈ R, algunas veces escribimos aRb. Si A = B decimossimplemente que R es una relacion sobre A.

Si (a, b) ∈ R, decimos que b es la imagen a respecto a R, y que a es la preimagen de brespecto a R.

El dominio de una relacion R ⊂ A × B, es el subconjunto DR ⊂ A de todos loselementos de A que tienen imagen en B respecto a R. Esto es:

DR = {a ∈ A : (∃b ∈ B)(a, b) ∈ R}.

Para toda a ∈ A,

a ∈ DR ⇔ (∃b ∈ B)(a, b) ∈ R.

La imagen de una relacion R ⊂ A × B, es el subconjunto IR ⊂ B de todos loselementos de B que tiene preimagen en A respecto a R. Esto es:

IR = {b ∈ B : (∃a ∈ A)(a, b) ∈ R}.

Para toda b ∈ B,

b ∈ IR ⇔ (∃a ∈ A)(a, b) ∈ R.

La relacion inversa de una realcion R ⊂ A×B, es la relacion sobre B ×A dada por

R−1 = {(b, a) ∈ B ×A : (a, b) ∈ A×B}.

Para toda a ∈ A y toda b ∈ B,

(b, a) ∈ R−1 ⇔ (a, b) ∈ R.



Ejemplo

Sean A = {a, b, c, d} y B = {1, 2, 3, 4, 5}. Sea la relacion

R = {(a, 2), (a, 4), (b, 4), (d, 5)}.

Tenemos entoncesDR = {a, b, d} y IR = {2, 4, 5}.

Y en este caso,R−1 = {(2, a), (4, a), (4, b), (5, d)}.

b

b

b

b

b

b

b

b

b

a

b

c

d

1

2

3

4

5

A B

R



Ejemplo

Sean A = {a, b, c, d} y B = {1, 2, 3, 4, 5}. Sea la relacion

R = {(a, 2), (a, 4), (b, 4), (d, 5)}.

Tenemos entoncesDR = {a, b, d} y IR = {2, 4, 5}.

Y en este caso,R−1 = {(2, a), (4, a), (4, b), (5, d)}.

b

b

b

b

b

b

b

b

b

a

b

c

d

1

2

3

4

5

A B

R−1



Ejemplo

En Z definimos R tal que

∀m,n ∈ Z : (m,n) ∈ R⇔ (m > 0) ∧ (m | n).

Algunos pares (m,n) de R son

(2,−6), (2, 6), (3,−9), (3, 9), ...

En este caso,DR = Z+ y IR = Z.

Y por otro lado,

∀m,n ∈ Z : (m,n) ∈ R−1 ⇔ (n > 0) ∧ (n | m).

Algunos pares (m,n) de R−1 son

(−6, 2), (6, 2), (−9, 3), (9, 3), ...



Ejemplo

La relacion R ⊂ Z2



Ejemplo

La relacion R−1 ⊂ Z2



Dos observaciones utiles

Teorema

Si R ⊂ A×B,

(R−1)−1 = R.

Demostracion.

(a, b) ∈ R⇔ (b, a) ∈ R−1

⇔ (a, b) ∈ (R−1)−1.

Teorema

Si R ⊂ S ⊂ A×B,

R−1 ⊂ S−1.

Demostracion.

(b, a) ∈ R−1 ⇒ (a, b) ∈ R⇒ (a, b) ∈ S⇒ (b, a) ∈ S−1.



Composicion de relaciones

Dadas las relaciones R ⊂ A × B y S ⊂ B × C, definimos la composicion de R y Scomo la relacion

S ◦R = {(a, c) ∈ A× C : (∃b ∈ B)(a, b) ∈ R ∧ (b, c) ∈ S}.

b ba

A B

R

C

bb c

S

S ◦R

aRb bSc



Ejemplo

Sean los conjuntos

A = {−1, 0, 1}, B = {1, 3} y C = {3, 5},

y las relaciones

R = {(−1, 1), (1, 1)} ⊂ A×B y S = {(1, 3), (3, 5)} ⊂ B × C.

EntoncesS ◦R = {(−1, 3), (1, 3)}.




Teorema

Sean A, B y C conjuntos, y sean R ⊂ A×B y S ⊂ B×C relaciones. Entonces

(S ◦R)−1 = R−1 ◦ S−1.

b ba

A B

R

C

bb c

S

S−1R−1

S ◦R

(S ◦R)−1 = R−1 ◦ S−1

aRb bSc

bR−1a cS−1b




Teorema

Sean A, B y C conjuntos, y sean R ⊂ A×B y S ⊂ B×C relaciones. Entonces

(S ◦R)−1 = R−1 ◦ S−1.

Demostracion.

Para todo a ∈ A y c ∈ C, tenemos,

(c, a) ∈ (S ◦R)−1 ⇔ (a, c) ∈ S ◦R⇔ (∃b ∈ B)(a, b) ∈ R ∧ (b, c) ∈ S⇔ (∃b ∈ B)(b, a) ∈ R−1 ∧ (c, b) ∈ S−1

⇔ (∃b ∈ B)(c, b) ∈ S−1 ∧ (b, a) ∈ R−1

⇔ (c, a) ∈ R−1 ◦ S−1.




Teorema : La composicion de relaciones es asociativa

Sean A, B, C y D conjuntos, y sean R ⊂ A × B, S ⊂ B × C y T ⊂ C × D.Entonces

(T ◦ S) ◦R = T ◦ (S ◦R).

Demostracion.

[⊂] Observamos primero que T ◦ S ⊂ B ×D, ası que para toda a ∈ A y toda d ∈ D,si (a, d) ∈ (T ◦ S) ◦ R, existira un b ∈ B tal que (a, b) ∈ R y (b, d) ∈ T ◦ S; se sigueque habra un c ∈ C tal que (b, c) ∈ S y (c, d) ∈ T . Tenemos ası que (a, c) ∈ S ◦ R y(c, d) ∈ T . En consecuencia, (a, d) ∈ T ◦ (S ◦R).

[⊃] Observamos primero que S ◦ R ⊂ A × C, ası que para toda a ∈ A y toda d ∈ D,si (a, d) ∈ T ◦ (S ◦ R), existira un c ∈ C tal que (a, c) ∈ S ◦ R y (c, d) ∈ T ; se sigueque habra un b ∈ B tal que (a, b) ∈ R y (b, c) ∈ S. Tenemos ası que (a, b) ∈ R y(b, d) ∈ T ◦ S. En consecuencia, (a, d) ∈ (T ◦ S) ◦R.

Otra forma de probar [⊃] asumiendo [⊂]

Note que

(T ◦ (S ◦R))−1 = (S ◦R)−1 ◦ T−1 = (R−1 ◦ S−1) ◦ T−1

((T ◦ S) ◦R)−1 = R−1 ◦ (T ◦ S)−1 = R−1 ◦ (S−1 ◦ T−1).

Y por otra parte,

(R−1 ◦ S−1) ◦ T−1 ⊂ R−1 ◦ (S−1 ◦ T−1).

De donde(T ◦ (S ◦R))−1 ⊂ ((T ◦ S) ◦R)−1,

esto esT ◦ (S ◦R) ⊂ (T ◦ S) ◦R.





Sean A, B, C y D conjuntos, y sean R ⊂ A × B, S ⊂ B × C y T ⊂ C × Drelaciones. Entonces

(T ◦ S) ◦R = T ◦ (S ◦R).

Pero la mejor forma de probar el teorema es...

(a, d) ∈ (T ◦ S) ◦R⇔ (∃b ∈ B)(a, b) ∈ R ∧ (b, d) ∈ T ◦ S

⇔ (∃b ∈ B)(a, b) ∈ B ∧ ((∃c ∈ C)(b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃b ∈ B)(∃c ∈ C)(a, b) ∈ R ∧ ((b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃c ∈ C)(∃b ∈ B)((a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)((∃b ∈ B)(a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)(a, c) ∈ S ◦R ∧ (c, d) ∈ T⇔ (a, d) ∈ T ◦ (S ◦R).






(T ◦ S) ◦R = T ◦ (S ◦R).


(a, d) ∈ (T ◦ S) ◦R⇔ (∃b ∈ B)(a, b) ∈ R ∧ (b, d) ∈ T ◦ S⇔ (∃b ∈ B)(a, b) ∈ B ∧ ((∃c ∈ C)(b, c) ∈ S ∧ (c, d) ∈ T )

⇔ (∃b ∈ B)(∃c ∈ C)(a, b) ∈ R ∧ ((b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃c ∈ C)(∃b ∈ B)((a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)((∃b ∈ B)(a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)(a, c) ∈ S ◦R ∧ (c, d) ∈ T⇔ (a, d) ∈ T ◦ (S ◦R).






(T ◦ S) ◦R = T ◦ (S ◦R).


(a, d) ∈ (T ◦ S) ◦R⇔ (∃b ∈ B)(a, b) ∈ R ∧ (b, d) ∈ T ◦ S⇔ (∃b ∈ B)(a, b) ∈ B ∧ ((∃c ∈ C)(b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃b ∈ B)(∃c ∈ C)(a, b) ∈ R ∧ ((b, c) ∈ S ∧ (c, d) ∈ T )

⇔ (∃c ∈ C)(∃b ∈ B)((a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)((∃b ∈ B)(a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)(a, c) ∈ S ◦R ∧ (c, d) ∈ T⇔ (a, d) ∈ T ◦ (S ◦R).






(T ◦ S) ◦R = T ◦ (S ◦R).


(a, d) ∈ (T ◦ S) ◦R⇔ (∃b ∈ B)(a, b) ∈ R ∧ (b, d) ∈ T ◦ S⇔ (∃b ∈ B)(a, b) ∈ B ∧ ((∃c ∈ C)(b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃b ∈ B)(∃c ∈ C)(a, b) ∈ R ∧ ((b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃c ∈ C)(∃b ∈ B)((a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T

⇔ (∃c ∈ C)((∃b ∈ B)(a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)(a, c) ∈ S ◦R ∧ (c, d) ∈ T⇔ (a, d) ∈ T ◦ (S ◦R).






(T ◦ S) ◦R = T ◦ (S ◦R).


(a, d) ∈ (T ◦ S) ◦R⇔ (∃b ∈ B)(a, b) ∈ R ∧ (b, d) ∈ T ◦ S⇔ (∃b ∈ B)(a, b) ∈ B ∧ ((∃c ∈ C)(b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃b ∈ B)(∃c ∈ C)(a, b) ∈ R ∧ ((b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃c ∈ C)(∃b ∈ B)((a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)((∃b ∈ B)(a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T

⇔ (∃c ∈ C)(a, c) ∈ S ◦R ∧ (c, d) ∈ T⇔ (a, d) ∈ T ◦ (S ◦R).






(T ◦ S) ◦R = T ◦ (S ◦R).


(a, d) ∈ (T ◦ S) ◦R⇔ (∃b ∈ B)(a, b) ∈ R ∧ (b, d) ∈ T ◦ S⇔ (∃b ∈ B)(a, b) ∈ B ∧ ((∃c ∈ C)(b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃b ∈ B)(∃c ∈ C)(a, b) ∈ R ∧ ((b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃c ∈ C)(∃b ∈ B)((a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)((∃b ∈ B)(a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)(a, c) ∈ S ◦R ∧ (c, d) ∈ T

⇔ (a, d) ∈ T ◦ (S ◦R).






(T ◦ S) ◦R = T ◦ (S ◦R).


(a, d) ∈ (T ◦ S) ◦R⇔ (∃b ∈ B)(a, b) ∈ R ∧ (b, d) ∈ T ◦ S⇔ (∃b ∈ B)(a, b) ∈ B ∧ ((∃c ∈ C)(b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃b ∈ B)(∃c ∈ C)(a, b) ∈ R ∧ ((b, c) ∈ S ∧ (c, d) ∈ T )⇔ (∃c ∈ C)(∃b ∈ B)((a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)((∃b ∈ B)(a, b) ∈ R ∧ (b, c) ∈ S) ∧ (c, d) ∈ T⇔ (∃c ∈ C)(a, c) ∈ S ◦R ∧ (c, d) ∈ T⇔ (a, d) ∈ T ◦ (S ◦R).



Clasificacion de relaciones sobre un conjunto A

Sea R una relacion sobre un conjunto A, i.e. R ⊂ A×A = A2.

R es reflexiva ⇔ ∀x ∈ A : (x, x) ∈ R.

R es simetrica ⇔ ∀x, y ∈ A : (x, y) ∈ R⇒ (y, x) ∈ R.

R es antisimetrica ⇔ ∀x, y ∈ A : (x, y) ∈ R ∧ (y, x) ∈ R⇒ x = y.

R es transitiva ⇔ ∀x, y, z ∈ A : (x, y) ∈ R ∧ (y, z) ∈ R⇒ (x, z) ∈ R.



Ejemplo

Sea A = {a, b, c, d, e, f, g, h}, y sea la relacion sobre A

R1 = {(a, b), (b, a), (c, c), (c, d), (c, h), (e, c), (f, f), (h, g)}

r s tR1

R2

R3

R4Credito imagen aquı.


http://cms.dm.uba.ar/academico/materias/1ercuat2016/algebra_I/


Ejemplo


R2 = {(a, a), (a, b), (b, a), (b, b),(c, c), (c, d), (c, e), (c, h), (d, c),(d, d), (e, e), (f, f), (g, g), (h, h), (h, g)}

r s tR1

R2 XR3

R4Credito imagen aquı.




Ejemplo


R3 = {(a, a), (a, b), (b, a), (b, b), (c, c), (c, e), (c, g), (c, h), (f, f), (h, g)}

r s tR1

R2 XR3 XR4

Credito imagen aquı.




Ejemplo


R4 = {(a, a), (a, b), (b, a), (b, b), (c, c),(d, d), (e, e), (e, g), (e, h),(f, f), (g, e), (g, g), (g, h), (h, e), (h, g), (h, h)}

r s tR1

R2 XR3 XR4 X X X





Ejemplo

Sobrre R definimos R con la sentencia

∀x, y ∈ R : (x, y) ∈ R⇔ x− y ∈ Z.

Tenemos

1. R es reflexiva:x ∈ R⇒ x− x = 0 ∈ Z.

2. R es simetrica:

(y, x) ∈ R⇒ x− y ∈ Z⇒ y − x = −(x− y) ∈ Z⇒ (y, x) ∈ R.

3. R es transitiva:

(x, y) ∈ R ∧ (y, z) ∈ R⇒ x− y ∈ Z ∧ y − z ∈ Z⇒ x− y + y − z ∈ Z⇒ x− z ∈ Z⇒ (x, z) ∈ R.

Para cada y ∈ R,

x ∼ y ⇔ (∃k ∈ Z) y = x+ k

Representacion grafica de R



Ejemplo importante: divisibilidad

Si m y n son enteros, decimos que m divide a n, y escribimos m | n, si existe un enterok tal que n = mk.

Propiedades:

1. | es reflexiva:m ∈ Z⇒ m = m · 1⇒ m | m.

2. | no es antisimetrica:

1 | −1 y − 1 | 1 pero 1 6= −1.

No obstante, | es casi antisimetrica: Sean m y n enteros tales que m | n y n | m.Existen enteros k y k′ tales que n = mk y m = nk′. Ası,

n = mk = (nk′)k = n(kk′).

Entonces kk′ = 1, y por lo tanto k y k′ tienen el mismo signo y |k| = |k′| = 1. Demodo que n = m o bien n = −m.



Ejemplo importante: divisibilidad

Si m y n son enteros, decimos que m divide a n, y escribimos m | n, si existe un enterok tal que n = mk.

Propiedades:

3. | no es simetrica:1 | 2 pero 2 - 1.

4. | es transitiva: Sean m,n, l enteros tales que m | n y n | l. Existen enteros k y k′

tales que n = mk y l = nk′. Luego

l = nk′ = (mk)k′ = m(kk′).

De modo que m | l.



Otras propiedades de la divisibilidad

Teorema

Para todo entero a, a∣∣0 y 1

∣∣a. Y

0∣∣a si y solo si a = 0.

Demostracion.0 = a · 0 y a = 1 · a.

Teorema

Si a∣∣b y b 6= 0, entonces |a| ≤ |b|.

Demostracion.Si b = ak, entonces |b| = |a||k|. Si b 6= 0,de hecho |k| ≥ 1. Luego |b| ≥ |a|.

Corolario

Si a∣∣b y b

∣∣a, entonces |a| = |b|.

Teorema

Si a∣∣b y a

∣∣c entonces a∣∣xb+yc para

cualesquiera enteros x y y.

Demostracion.Si b = ak y c = ak′, entonces

xb+ yc = a(xk + yk′).

Teorema

Si a∣∣b entonces ac

∣∣bc, para todo c.

Y si ac∣∣bc y c 6= 0 entonces a

∣∣b.Demostracion.Si b = ak, entonces bc = ack.



Lema de Euclides

Si m y n son enteros, entonces el maximo comun divisor de m y n, es el numero enteropositivo

MCD(m,n) = (m,n) := max{d ≥ 1 : d∣∣n y d

∣∣m}.Los enteros m y n son primos relativos si (m,n) = 1.

Teorema : Lema de Euclides

Si a∣∣bc y (a, b) = 1, entonces a

∣∣c.Demostracion.

Si k es un entero tal que bc = ak, entonces

b

a· ca

= k.

Por lo que al menos uno de ba

y ca

es entero. Pero ba

no puede ser entero. Ası que ca

es un entero. Esto es, a∣∣c.



Numeros Primos

Un numero entero p > 1 es primo si los unicos divisores positivos de p son 1 y p.

Teorema

Si p es primo y p∣∣mn entonces p

∣∣m o p∣∣n.

Demostracion.

Supongamos que p 6 | m. En particular, si d∣∣m entonces |d| 6= p. Luego, (m, p) = 1.

Ası que, por el Lema de Euclides, p∣∣n.



Relaciones de equivalencia

Una relacion R sobre un conjunto A es de equivalencia si es reflexiva, simetrica ytransitiva. Algunas veces se escribe ∼ para denotar una relacion de equivalencia. Laexpresion x ∼ y se lee “x es equivalente a y”.

Si x ∈ A, entonces la clase de equivalencia (relativa a ∼) de x es el conjunto

K[x] = {y ∈ A : x ∼ y}.

El conjunto cociente relativo a ∼ es el conjunto

A/∼ = {K[x] : x ∈ A}.

Esto es, el conjunto cociente es el de todas las clases de equivalencia relativas a ∼.

Convenio

Sera mas comodo usar [x] para denotar las clases de equivalencia.



Ejemplo: Recordemos


R = {(a, a), (a, b), (b, a), (b, b), (c, c),(d, d), (e, e), (e, g), (e, h),(f, f), (g, e), (g, g), (g, h), (h, e), (h, g), (h, h)}

R es reflexiva, simetrica y transitiva. Por tanto R es equivalencia. Ademas

[a] = [b] = {a, b}, [c] = {c}, [d] = {d}, [e] = [g] = [h] = {e, g, h}, [f ] = {f}.





Relacion de congruencia

Sea n > 0 entero. Dos numeros enteros a y b son congruentes modulo n, si n | a− b.Escribimos

a ≡ b (mod n).

Teorema

La relacion de congruencia es de equivalencia.

Demostracion.

Reflexividad:∀x ∈ Z : n | x− x = 0

Simetrıa:

a ≡ b (mod n)⇔ n | a− b⇔ b ≡ a (mod n).



Relacion de congruencia

Sea n > 0 entero. Dos numeros enteros a y b son congruentes modulo n, si n | a− b.Escribimos

a ≡ b (mod n).

Teorema

La relacion de congruencia es de equivalencia.

Demostracion.

Transitividad:

a ≡ b y b ≡ c (mod n)⇒ n | a− b y n | b− c⇒ n | (a− b) + (b− c) = a− c⇒ a ≡ c (mod n).



Clases de equivalencia de la relacion de congruencia

Sean n > 0 un entero. Sea x ∈ Z. Preferiblemente usamos x para nombrar la clase deequivalencia de x (modulo n). Para todo entero y,

y ∈ x⇔ y ≡ x (mod n)

⇔ n | y − x⇔ (∃k ∈ Z)y − x = nk

⇔ (∃k ∈ Z)y = nk + x.

En consecuenciax = {nk + x : k ∈ Z}.

Algunos casos:

−2 = {...,−3n− 2,−2n− 2,−2, 2n− 2, 3n− 2, ...}−1 = {...,−3n− 1,−2n− 1,−1, 2n− 1, 3n− 1, ...}0 = {...,−3n,−2n,−n, 0, n, 2n, 3n, ...}1 = {...,−3n+ 1,−2n+ 1,−n+ 1, 1, n+ 1, 2n+ 1, 3n+ 1, ...}2 = {...,−3n+ 2,−2n+ 2,−n+ 2, 2, n+ 2, 2n+ 2, 3n+ 2, ...}




En particular,y ∈ n⇔ (∃k ∈ Z)y = nk + n.

Pero,y = nk + n = n(k + 1).

Y desde luego, k + 1 ∈ Z⇔ k ∈ Z. Por lo tanto,

y ∈ n⇔ (∃k ∈ Z)y = nk + n⇔ (∃k ∈ Z)y = nk.

Esto es n = 0.

Del mismo modo puede verificarse

n+ 1 = 1

n+ 2 = 2

...

2n = 0

2n+ 1 = 1

...




Por otra parte,y ∈ −1⇔ (∃k ∈ Z)y = nk − 1.

Pero,y = nk − 1 = nk − n+ (n− 1) = (k − 1)n+ (n− 1),

y desde luego k − 1 ∈ Z⇔ k ∈ Z. Por lo tanto,

y ∈ −1⇔ (∃k ∈ Z)y = nk + (n− 1).

Esto es, n− 1 = −1.

Del mismo modo puede verificarse

n− 2 = −2n− 3 = −3

...

0 = −n...




En general...

Teorema

Sea n > 0. Las unicas clases de equivalencia de la relacion de congruencia modulon son 0, 1,...,n− 1.

Demostracion.

De acuerdo al algoritmo de la division de Euclides, para todo y ∈ Z, existe un entero ky un entero x tales que

y = nk + x y 0 ≤ x ≤ n− 1.

Se sigue inmediatamente que y ∈ x.

Aritmetica modular

Puede probarse:

a ≡ b y c ≡ d (mod n) ⇒ a+ c ≡ b+ d (mod n).

a ≡ b y c ≡ d (mod n) ⇒ ac ≡ bd (mod n).



Clases de equivalencia y particiones

Teorema

Si ∼ es una relacion de equivalencia sobre un conjunto A, entonces

1. ∀x ∈ A(x ∈ [x]).

2. ∀x, y ∈ A(x ∼ y ⇔ [x] = [y]).

Demostracion.

Prueba de 1.: Dado que ∼ es de equivalencia, x ∼ x para todo x ∈ A. Esto es x ∈ [x]para todo x ∈ A.

Prueba de 2.:

[⇒] Supongamos que x ∼ y. Sea z ∈ [x]. Entonces z ∼ x y por tansitividad, z ∼ y,por lo que z ∈ [y]. Esto prueba que [x] ⊂ [y]. Pero por simetrıa, un argumento analogomuestra que [y] ⊂ [x].

[⇐] Si [x] = [y], se sigue x ∈ [y] y por tanto x ∼ y.



Clases de equivalencia y particiones

Dado un conjunto A, decimos que un conjunto Q de subconjuntos de A es una particionde A si cumple:

1. El vacıo no esta en Q: ∀B ∈ Q(B 6= ∅).2. Los elementos de Q son ajenos: ∀B,C ∈ Q(B 6= C ⇔ B ∩ C = ∅).3. A =

⋃Q.

Teorema

Si ∼ es una relacion de equivalencia sobre A, entonces el conjunto cociente A/∼es una particion de A. Recıprocamente, si Q es una particon de un conjunto A,si para todo x, y ∈ A, defnimos la relacion

x ∼ y ⇔ ∃P ∈ Q(x, y ∈ P ),

entonces ∼ es de equivalencia, y el conjunto cociente es Q.



Funciones

Una funcion de un conjunto A en un conjunto B es una relacion f ⊂ A × B tal quepara cada x ∈ A, existe un unico y ∈ B tal que (x, y) ∈ f . En sımbolos, f es funcionsi y solo si

(∀x ∈ A)(∀y1, y2 ∈ B)(x, y1) ∈ f ∧ (x, y2) ∈ f ⇒ y1 = y2.

b

b

b

b

b

b

b

b

b

a

b

c

d

1

2

3

4

5

A B

f

No es funcion

b

b

b

b

b

b

b

b

b

a

b

c

d

1

2

3

4

5

A B

f

Sı es funcion



Notacion

Si (x, y) ∈ f , entonces escribimos y = f(x). Decimos que y es la imagen de x (respectoa f) y que x es la preimagen de y (respecto a f).

Una regla de correspondencia es una formula f(x]) tal que permite asignar a cada x ∈ Aun unico y = f(x) ∈ B.

Si f es una funcion de A en B, generalmente escribimos f : A→ B. El conjunto A esel dominio y B es el contradominio de f .

Note que para toda funcion f : A → B, tenemos Df = A (el dominio de f esenteramente el conjunto A), en tanto que

If = {y ∈ B : ∃x ∈ A, y = f(x)} ⊂ B.

Tambien usamos la notacion

If = {f(x) : x ∈ A} y y ∈ If ⇔ ∃x ∈ A(y = f(x)).

Dos funciones f : A → B y g : C → D son iguales si y solo si, A = C, B = D y sipara toda x ∈ A, f(x) = g(x). Note en particular que f = g ⇒ If = Ig .



Ejemplo

Sean A y B conjuntos y sea b ∈ B. Entonces f = A × {b} es una funcion llamadafuncion constante.

Ejemplo

Si A es un conjunto, entonces f = {(x, y) ∈ A2 : x = y} es una funcion llamadafuncion identidad

Ejemplo

Si A ⊂ B son conjuntos, la funcion iA = {(x, y) ∈ A × B : x = y} es una funcionllamada inclusion, usualmente denotada por iA : A ↪→ B.

Ejemplo

Si A ⊂ B son conjuntos, la funcion χA : B → {0, 1}, dada por

χA(x) =

{1 si x ∈ A,0 si x /∈ A,

es llamada funcion caracterıstica de A.



Otras funciones tıpicas: Funciones escalonadas

La funcion piso o maximo entero menor que, es la funcion b·c : R→ Z dada por

bxc = max{n ∈ Z : n ≤ x}, ∀x ∈ R.



Otras funciones tıpicas: Funciones escalonadas

La funcion techo o mınimo entero menor que, es la funcion d·e : R→ Z dada por

dxe = min{n ∈ Z : n ≥ x}, ∀x ∈ R.



Algunas propiedades de las funciones escalonadas

Teorema

Para toda x ∈ R,bxc ≤ x < bxc+ 1

Demostracion.

De la definicion es inmediato que bxc ≤ x. Ahora, desde luego bxc ≤ bxc+1 y bxc+1es tambien un numero entero, de modo que, nuevamente por la definicion de la funcionpiso, x < bxc+ 1.

Corolario

Para toda x ∈ R y toda n ∈ Z,

bxc = n⇔ n ≤ x < n+ 1.




Teorema

Para toda x ∈ R y toda n ∈ Z,

bx+ nc = bxc+ n.

Demostracion.

Dado que bxc+ n es un entero y bxc+ n ≤ x+ n, se sigue que

bxc+ n ≤ bx+ nc.

Por otro lado, si k es un entero tal que k ≤ x + n, entonces k − n ≤ x, y por tantok − n ≤ bxc, de donde k ≤ bxc+ n. Luego,

bx+ nc ≤ bxc+ n.




Teorema

Para toda x ∈ R,

b2xc = bxc+⌊x+

1

2

⌋

Demostracion.

Supongamos primero que x− bxc < 12

. Se tiene entonces

bxc ≤ x ≤ x+1

2< bxc+ 1 y 2bxc ≤ 2x < 2bxc+ 1.

En consecuencia,

b2xc = 2bxc y

⌊x+

1

2

⌋= bxc,

y el teorema es inmediato.




Teorema

Para toda x ∈ R,

b2xc = bxc+⌊x+

1

2

⌋

Demostracion.

Si x− bxc ≥ 12

, se tiene

bxc+1 ≤ x+ 1

2< (bxc+1)+ 1 y 2bxc+1 ≤ 2x < 2(bxc+1) = (2bxc+1)+ 1.

De donde ⌊x+

1

2

⌋= bxc+ 1 y b2xc = 2bxc+ 1.

De aquı se sigue de inmediato la igualdad buscada.




Teorema

Para toda x ≥ 0,b√xc = b

√bxcc.

Demostracion.

k = b√bxcc ⇔ k ≤

√bxc < k + 1

⇔ k2 ≤ bxc < (k + 1)2

⇔ k2 ≤ x < (k + 1)2

⇔ k ≤ √x < k + 1

⇔ b√xc = k



Clasificacion de funciones

Decimos que una funcion f : A→ B es inyectiva si

(∀x, x′ ∈ A)f(x) = f(x′)⇒ x = x′.

Decimos que una funcion f : A→ B es sobreyectiva si

(∀y ∈ B)(∃x ∈ A)y = f(x).

Decimos que una funcion f : A→ B es biyectiva si es inyectiva y sobreyectiva.

b

b

b

b

b

b

b

b

b

a

b

c

d

1

2

3

4

5

A B

f

Inyectiva

b

b

b

b

b

b

b

a

b

c

d

2

4

5

A B

f

Sobreyectiva

b

b

b

b

b

b

b

b

a

b

c

d

2

3

4

5

A B

f

Biyectiva



Composicion de funciones

Si f : A → B y g : B → C son funciones, entonces la composicion de f y g es lafuncion g ◦ f : A→ C tal que para toda x ∈ A,

(g ◦ f)(x) := g(f(x)).

Teorema

Si f : A→ B, g : B → C y h : C → D son funciones, entonces

(h ◦ g) ◦ f = h ◦ (g ◦ f).

Demostracion.

Para toda x ∈ A,

((h ◦ g) ◦ f)(x) = (h ◦ g)(f(x))= h(g(f(x)))

= h((g ◦ f)(x))= (h ◦ (g ◦ f))(x)



Composicion de funciones inyectivas

Teorema

Si f : A→ B y g : B → C son funciones inyectivas, entonces g ◦ f : A→ C esinyectiva.

Demostracion.

Sean x, x′ ∈ A. Entonces,

(g ◦ f)(x) = (g ◦ f)(x′)⇒ g(f(x)) = g(f(x′))

⇒ f(x) = f ′(x)

⇒ x = x′.



Otro teorema importante

Teorema

Sean f : A → B y g : B → C funciones tales que g ◦ f : A → B es inyectiva,entonces f : A→ B es inyectiva.

Demostracion.

Sean x, x′ ∈ A. Tenemos,

f(x) = f(x′)⇒ g(f(x)) = g(f(x′))

⇒ (g ◦ f)(x) = (g ◦ f)(x′)⇒ x = x′.



Composicion de funciones sobreyectivas

Teorema

Si f : A→ B y g : B → C son funciones sobreyectivas, entonces g ◦ f : A→ Ces sobreyectiva.

Demostracion.

Sea z ∈ C. Como g es sobreyectiva, existe y ∈ B tal que z = g(y). Pero f es tambiensobre, ası que existe un x ∈ A tal que f(x) = y. Ası entonces

z = g(y) = g(f(x)) = (g ◦ f)(x).



Otro teorema importante

Teorema

Sean f : A→ B y g : B → C funciones tales que g ◦ f es sobreyectiva, entoncesg : B → C es sobreyectiva.

Demostracion.

Sea z ∈ C. Como g ◦ f es sobreyectiva, existe un x ∈ A tal que

(g ◦ f)(x) = g(f(x)) = z.

Pero de hecho, f(x) ∈ B.



Composicion de funciones biyectivas

Teorema

Si f : A→ B y g : B → C son funciones biyectivas, entonces g ◦ f es biyectiva.

Teorema

Si f : A → B y g : B → C son funciones tales que g ◦ f es biyectiva, entoncesf es inyectiva y g es sobreyectiva.



Funciones inversas

Sea f : A→ B una funcion.

Decimos que f tiene (funcion) inversa por la derecha si existe g : B → A tal que

f ◦ g = IdB .

Decimos que f tiene (funcion) inversa por la izquierda si existe h : B → A tal que

h ◦ f = IdA.



Funciones inversas

Ejemplo

Sean A = {1, 2} y B = {0} y sea f : A→ B tal que

f(1) = f(2) = 0.

Entonces f es una funcion, y las funciones g, g′ : B → A dadas por

g(0) = 1 y g′(0) = 2,

son inversas por la derecha de f . En efecto:

(f ◦ g)(0) = f(g(0)) = f(1) = 0 y (f ◦ g′)(0) = f(g′(0)) = f(2) = 0.

Sin embargo, f no tiene inversa por la izquierda: En efecto, para cualquier funcionh : B → A, se cumple que

(h ◦ f)(1) = h(f(1)) = h(0) = h(f(2)) = (h ◦ f)(2),

por lo que h ◦ f 6= IdA.



Funciones inversas

Teorema

Una funcion f : A→ B es inyectiva si y solo si tiene inversa por la izquierda.

Demostracion.

[⇒] Supongamos que f : A→ B es inyectiva. Elegimos algun x∗ ∈ A arbitrariamente.Definimos h : B → A dada por

h(y) =

{x si y = f(x)

x∗ si (@x ∈ A)y = f(x).

Entonces h ◦ f = IdA.

b

b

b

b

b

b

b

b

b

A B

f : A → B

x∗

b

h : B → A

h(y) = x y = f(x)



Funciones inversas

Teorema

Una funcion f : A→ B es inyectiva si y solo si tiene inversa por la izquierda.

Demostracion.

[⇐] Supongamos que h : B → A es una inversa izquierda de f : A → B. Sean x1 yx2 en A tales que f(x1) = f(x2). Entonces, como h ◦ f = IdA, tenemos,

x1 = h(f(x1)) = h(f(x2)) = x2.



Funciones inversas

Teorema

(Con Axioma de Eleccion). Una funcion f : A → B es sobre si y solo si tieneinversa por la derecha.

Demostracion.

[⇒] Supongamos que f : A → B es una funcion sobre. Vamos a definir una inversapor la derecha del siguiente modo: Para cada y ∈ B, dado que f es sobre,

Ay = {x ∈ A : f(x) = y} 6= ∅.

Elegimos entonces algun xy ∈ Ay (aquı es donde interviene el Axioma de Eleccion).Definimos ası una funcion g : B → A tal que g(y) = xy , para cada y ∈ B. Noteentonces que para todo y ∈ B,

f(g(y)) = f(xy) = y.



Funciones inversas

Teorema

(Con Axioma de Eleccion). Una funcion f : A → B es sobre si y solo si tieneinversa por la derecha.

Demostracion.

[⇐] Supongamos que g : B → A es una inversa derecha de f : A → B. Si y ∈ B,entonces tomamos x = g(y) ∈ A, de manera que

f(x) = f(g(y)) = y.

Ası que f es sobre. (Aquı no usamos el Axioma de Eleccion).



Funciones inversas

Teorema

Si una funcion f : A → B tiene inversa por la izquierda h : B → A, e inversapor la derecha g : B → A, entonces g = h.

Demostracion.

Sea y ∈ B. Por hipotesis,

h ◦ f = IdA y f ◦ g = IdB .

En particular,y = f(g(y)).

Luego,h(y) = h(f(g(y))) = g(y).



Funciones inversas

Decimos que una funcion f : A → B tiene (funcion) inversa si existe una funcionf−1 : B → A tal que f ◦ f−1 = IdB y f−1 ◦ f = IdA.

Esto es, f tiene inversa si y solo si, tiene inversa por la izquierda y por la derecha.

Teorema

Una funcion f : A→ B tiene inversa si y solo si es biyectiva.

Se sigue de inmediato el teorema siguiente de unicidad de las funciones inversas.

Teorema

Si una funcion f : A→ B tiene inversa, entonces esta es unica.


araceli guzm an y guillermo garro · 2017. 8. 1. · carmen g omez laveaga. algebra superior ,...

Documents