conjuntos y teoria de grupos

Curso de conjuntos y numeros.

Apuntes

Juan Jacobo Simon Pinero

Curso 2013/2014

Indice general

I Conjuntos 5

1. Conjuntos y elementos 71.1. Sobre el concepto de conjunto y elemento. . . . . . . . . . . . . . 71.2. Pertenencia, contenido e igualdad. . . . . . . . . . . . . . . . . . 71.3. Operaciones con subconjuntos . . . . . . . . . . . . . . . . . . . 10

1.3.1. Familias de conjuntos y operaciones . . . . . . . . . . . . 131.4. Pares ordenados, producto cartesiano y relaciones binarias . . . . 15

2. Aplicaciones 192.1. Relaciones y aplicaciones . . . . . . . . . . . . . . . . . . . . . . . 192.2. Tipos de aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . 212.3. Imagenes directas e inversas . . . . . . . . . . . . . . . . . . . . . 222.4. Composicion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.4.1. Inversa de una aplicacion biyectiva . . . . . . . . . . . . . 25

3. Orden 293.1. Conjuntos ordenados y sus elementos distinguidos . . . . . . . . 293.2. Conjuntos bien ordenados. . . . . . . . . . . . . . . . . . . . . . . 34

4. Relaciones de equivalencia 374.1. Conceptos basicos . . . . . . . . . . . . . . . . . . . . . . . . . . 374.2. Clases de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . 384.3. El conjunto cociente y la proyeccion canonica . . . . . . . . . . . 394.4. Relaciones de equivalencia y particiones . . . . . . . . . . . . . . 40

5. Conjuntos numericos 435.1. Cardinalidad. Conjuntos finitos e infinitos . . . . . . . . . . . . . 43

5.1.1. Orden y operaciones aritmeticas . . . . . . . . . . . . . . 485.2. Numeros enteros . . . . . . . . . . . . . . . . . . . . . . . . . . . 485.3. Numeros racionales . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.3.1. Escritura decimal de numeros racionales. . . . . . . . . . 525.4. Numeros reales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.5. Numeros complejos . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.5.1. Forma exponencial de un numero complejo. . . . . . . . . 60

3

4 INDICE GENERAL

5.6. Conjuntos numerables y no numerables . . . . . . . . . . . . . . 61

6. Analisis combinatorio. 636.1. Variaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

6.1.1. Numero de variaciones. . . . . . . . . . . . . . . . . . . . 636.2. Permutaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646.3. Combinaciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

II Numeros y polinomios 67

7. El anillo de los numeros enteros. 697.1. Artimetica de los enteros. . . . . . . . . . . . . . . . . . . . . . . 69

7.1.1. Division entera y maximo comun divisor. . . . . . . . . . 697.1.2. Mnimo comun multiplo . . . . . . . . . . . . . . . . . . . 757.1.3. La ecuacion diofantica lineal . . . . . . . . . . . . . . . . 767.1.4. Numeros primos.Teorema Fundamental de la Aritmetica . 78

7.2. Congruencias. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 807.2.1. Propiedades aritmeticas de las congruencias . . . . . . . . 817.2.2. Estructuras algebraicas. . . . . . . . . . . . . . . . . . . . 827.2.3. Algunas aplicaciones . . . . . . . . . . . . . . . . . . . . . 84

7.3. Teoremas de Euler, Fermat y Wilson . . . . . . . . . . . . . . . . 877.4. Teorema chino de los restos . . . . . . . . . . . . . . . . . . . . . 90

8. Polinomios 958.1. Polinomios con coeficientes en un cuerpo. . . . . . . . . . . . . . 958.2. Races de polinomios. . . . . . . . . . . . . . . . . . . . . . . . . 1018.3. Irreducibilidad y teorema fundamental del algebra. . . . . . . . . 1038.4. Factores multiples. . . . . . . . . . . . . . . . . . . . . . . . . . . 1068.5. Polinomios irreducibles en Q[X ]. . . . . . . . . . . . . . . . . . . 107

A. Apendice 111A.1. La funcion sucesor . . . . . . . . . . . . . . . . . . . . . . . . . . 111A.2. Operaciones en N . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

Parte I

Conjuntos

5

Captulo 1

Conjuntos y elementos

1.1. Sobre el concepto de conjunto y elemento.

Comenzamos con la definicion de conjunto de G. Cantor:

Un conjunto es una coleccion (dentro de un todo) de distintos objetosdefinidos por nuestra intuicion o pensamiento

Esta forma de abordar los conjuntos se llama concepcion intuitiva de losconjuntos.

La nocion formal de conjunto corresponde con fundamentos de la ma-tematica que quedan fuera del alcance de nuestro curso.

Tambien queda fuera del alcance de este texto el concepto de pertenencia.

Vamos a asumir entonces que hay unos objetos que llamamos conjuntosque poseen unos objetos que llamamos elementos.

1.2. Pertenencia, contenido e igualdad.

Las colecciones a las que llamaremos conjuntos seran construidas de las si-guientes dos formas principales.

1. Por extension: haciendo la lista de objetos. Por ejemplo

A = {X1, . . . , Xn, . . . } o A = {a, b, c, . . .}.

2. Por comprehension: a traves de una formula proposicional que siempretendra, a su vez, un conjunto de referencia. Por ejemplo, si B es un con-junto,

A = {X B | p(X) (es verdadera) } .Cuando el conjunto B sea obvio quien es por el contexto, podemos noescribirlo.

7

8 CAPITULO 1. CONJUNTOS Y ELEMENTOS

Asumimos (como axioma) que cualquiera de las dos escrituras anterioresdetermina un unico conjunto.

1.2.1. Ejemplo. Las siguientes colecciones son conjuntos.

1. A = {a, e, i, o, u} o A = {x | x es una vocal }.2. A = {2, 4, . . .} o A = {x N | x es par }.

1.2.2. Ejercicio. Escribir, usando las formas de comprehension y extension,los siguientes conjuntos:

1. Los numeros naturales que son impares y menores que 20.

2. Las vocales de la palabra murcielago.

3. Los numeros impares positivos.

1.2.3. Observacion. La exigencia del conjunto de referencia en la escritura decomprehension es importante. El todo de donde tomamos los elementos debede ser, de antemano, un conjunto. De no ser as, podemos tener problemas, comose muestra a continuacion.

Sea U la coleccion de todos los conjuntos y definimos

A = {x U | x 6 x} .

Si U fuese conjunto entonces A tambien lo sera y entonces es inmediata lasiguiente proposicion: A A si y solo si A 6 A, conocida como la paradoja deRussell.

Lo que ocurre aqu es que U no es un conjunto y por tanto, no podemosformar el conjunto A por comprehension.

1.2.4. Notacion. Si a es un elemento del conjunto A, escribiremos a A. Encaso contrario escribimos a / A.1.2.5. Inclusion. Sean A y B conjuntos. Decimos que A esta contenido en B,o que A es subconjuntos de B si para todo elemento a A se tiene que a B.

Se denota A B y se expresa a A a BSi A no esta contenido en B entonces escribimos A 6 B.

1.2.6. Observacion. Es claro que A 6 B si y solo si existe a A tal quea 6 B.1.2.7. Ejemplo. Sea I = {x N | x es impar } = {x N | x = 2n +1, con n N}, que a veces, para abreviar, escribimos {2n+1 | n N} (aunqueesta escritura no estaba contemplada, se usa mucho y se entiende perfectamente,as que podemos introducirla). Entonces I N.1.2.8. Notacion. Sean A y B conjuntos, tales que A B. Si queremos destacarla posibilidad de que A y B sean iguales podemos escribir A B. Cuandoqueremos poner enfasis en justo lo contrario, escribimos A ( B; lo expresamoscomo a A a B pero b B tal que b 6 A.

1.2. PERTENENCIA, CONTENIDO E IGUALDAD. 9

1.2.9. Igualdad. Diremos que dos conjuntos A y B son iguales cuando tenganexactamente los mismos elementos. Lo expresamos a A a B.1.2.10. Proposicion. Sean A y B conjuntos. A = B si y solo si A B yB ADemostracion. Inmediata.

Conjunto vaco.

1.2.11. Definicion. Un conjunto vaco es aquel que no tiene elementos.

1.2.12. Proposicion. Sean A y B conjuntos. Si A es vaco entonces A B.Demostracion. Por reduccion al absurdo. SeaA un conjunto vaco y supongamosque existe B, conjunto tal que A * B. Entonces existe a A tal que a 6 B.Luego A no es vaco lo cual es imposible.

1.2.13. Corolario. Solo hay un conjunto vaco.

Demostracion. Inmediata de la proposicion anterior.

Notacion. El conjunto vaco se denota 1.2.14. Ejercicio. Decidir razonadamente si la siguiente afirmacion es verda-dera o falsa:

A = x, x 6 A.1.2.15. Partes de un conjunto. Sea A un conjunto. La coleccion

P(A) = {B | B A}se conoce como el conjunto de las partes de A o el conjunto potencia de A.

1.2.16. Ejercicios.

1. Determinar P().2. Sea A = {x1, x2, x3}. Escribir P(A) y comprobar que tiene 23 elementos.3. (Taller 2012-2013) Probar que A 6= P(A).

Solucion. Solo veremos el ejercicio del taller. Supongamos que A = P(A). Setendra entonces que X A implica que X A. Vamos a formar el conjuntoB = {X A | X 6 X}. Como B A entonces B A; ademas, ocurre una dedos:

1. B B, en cuyo caso B A y B B y por tanto B 6 B, lo cual esabsurdo.

2. B 6 B, en cuyo caso B A y B 6 B y por tanto B B, lo cual esabsurdo.

As que la suposicion de que A = P(A) reduce al absurdo y por tanto es falsa.Luego lo contrario es verdadero.


1.3. Operaciones con subconjuntos

1.3.1. Union. Sean A y B conjuntos. El conjunto

A B = {x | x A o x B}

se conoce como la union de A y B.

Se escribe x A B si y solo si x A o x B.Lo contrario es x / A B si y solo si x / A y x / B.

1.3.2. Ejercicio. Sea A un conjunto arbitrario. Probar que para cualquier con-junto B, se tiene que A A B.1.3.3. Interseccion. Sean A y B conjuntos. El conjunto

A B = {x | x A y x B}

se conoce como la interseccion de A y B.

Se escribe x A B si y solo si x A y x B.Lo contrario es x / A B si y solo si x / A o x / B.

1.3.4. Ejercicio. Para los conjuntos A, B y C, probar las siguientes propieda-des:

1. Si A B y B C entonces (A B) C.

2. (A B) C = A (B C).

3. A B si y solo si A B = B si y solo si A B = A

4. Como consecuencia, A = A y A = .

1.3.5. Ejemplos. 1) Vamos a comenzar abordando un caso muy concreto hastaotener la maxima generalidad, en el uso de la escritura comprehensiva.

Sea U = R2, el plano eucldeo, A = {(x, y) U | x+ y = 3}, B = {(x, y) U | x + y = 7} y C = {(x, y) U | x y = 0}. Probar que A B y queA 6 C.

Mas en general, si P (r) = {(x, y) U | x + y = r}, con r R, probar queP (r) P (s) si y solo si r s.

Finalmente, probar que si U es un conjunto arbitrario, A = {x U | p(x) }y B = {x U | q(x) }, entonces A B si y solo si [p(x) q(x)].

2) Vamos a ver un caso donde podemos comparar el uso de escritura com-prehensiva y el de listas. Para cualquier a N, se define N a = {a, 2a, . . .} ={x N | x = na, con n N}. En este caso, la escritura con lista parece maselegante que la comprehensiva. Tambien N a N b = N mcm(a, b); pero launion N a N b se escribe mal como lista.

1.3. OPERACIONES CON SUBCONJUNTOS 11

Diagramas de Venn

En 1880 John Venn introdujo los diagramas para una mejor comprension delos conjuntos y sus operaciones. Los siguientes diagramas representan la unione interseccion de dos conjuntos A y B contenidos en otro conjunto, digamos U .

U

A B

&%'$

&%'$

Union

U

A B

&%'$

&%'$

Interseccion

Leyes distributivas.

1.3.6. Proposicion. Sean A, B y C conjuntos. Entonces

1. A (B C) = (A B) (A C).

2. A (B C) = (A B) (A C).

Demostracion. Probaremos la primera, la otra se deja como ejercicio.

] Sea x A (B C). Entonces x A y x B C; es decir, x A yademas x B o x C. Ahora separamos en dos casos. Primero, x A y x B,de donde x A B. El otro es x A y x C, de donde x A C. No haymas casos y por tanto x (A B) (A C).

] Si x (A B) (A C) entonces x A y x B o bien x A y x C.Luego x A en ambos casos y as, x A y ademas x B o x C, de dondex A (B C).

Vamos ahora con la segunda.

] Sea x A (B C). Tenemos dos casos. Primero, si x A entoncesx A B y ademas x A C (Ejercicio 1.3.2) luego x (A B) (A C).Ahora, si x 6 A entonces x B C entonces x A B y x A C (otra vezEjercicio 1.3.2) y por tanto x (A B) (A C).

] Sea x (A B) (A C). Consideramos dos casos. Primero, si x Aentonces x A (B C) (otra vez Ejercicio 1.3.2). Segundo, si x 6 A entoncesx B y ademas x C por lo que x B C, de donde x A (B C).

1.3.7. Diferencia de conjuntos. Sean A y B conjuntos. La diferencia deconjuntos es la coleccion

A \B = {X | X A y X 6 B}.

Expresado como diagrama de Venn


U

A B

&%'$

&%'$

Diferencia

1.3.8. Ejercicio. Considerense los conjuntos A = {X R | 0 x2 6} yB = {X R | X22 < 8}. Se pide:

1. Representar estos conjuntos en la recta real.

2. Determinar los conjuntos AB, AB, A \B y B \A, escribiendolos deforma comprehensiva y graficamente en la recta real.

1.3.9. Complemento. Sean A y U conjuntos, con A U . Se conoce comocomplemento de A en U a la coleccion

A = U \A = {X U | X 6 A}.

Leyes de De Morgan.

Augustus De Morgan 1806 (Madras, India)-1871(Londres). Fue hijo de unmilitar britanico. Hizo contribuciones importantes en algebra, geometra y ademasfue cofundador de la London Mathematical Society, as como su primer presi-dente.

1.3.10. Proposicion. Sean A y B conjuntos.

1. (A B) = A B.

2. (A B) = A B.

Demostracion.

1. x (A B) x 6 A B x 6 A o x 6 B x A o x B x A B.

2. x (A B) x 6 A B x 6 A y x 6 B x A y x B x A B.

Expresado como diagrama de Venn

1.3. OPERACIONES CON SUBCONJUNTOS 13

U

A B

&%'$

&%'$

(A B) = A B

U

A B

&%'$

&%'$

(A B) = A B

1.3.1. Familias de conjuntos y operaciones

Algunas veces queremos hacer colecciones de objetos y no podemos o nonos interesa garantizar que todos ellos sean distintos. Vamos a ver un par deejemplos.

Sean N el conjunto de los numeros naturales y P el conjunto de los nume-ros pares positivos. Definimos, para cada n N, An como el conjunto de losmultiplos pares de n; es decir An = {x P | xn N}.

Entonces, la coleccion C = {An}nN no es conjunto porque, por ejemplo,Ap = A2p, para todo primo impar. En este caso, decimos que C es una familia(de conjuntos).

Aun as, es claro que podemos considerar su union e interseccion y respe-tara las leyes habituales de conjuntos.

Otro ejemplo es el siguiente. Considerese p1(X) = X3 X2 + X 1 y

p2 = X3 + X2 2. Sean R1 y R2 los conjuntos de races reales de p1(X) y

p2(X) respectivamente, y R = {R1, R2}. En principio, no podemos asegurarque R sea o no conjunto, pero es inmediato comprobar que, visto como familia1 R1 R2.1.3.11. Definicion. Una familia de conjuntos es una coleccion {Ai | i I},donde I es un conjunto y Ai son conjuntos.

Si todos los objetos son diferentes, tendremos un conjunto, si no, una familia.


Uniones e intersecciones arbitrarias en conjuntos y familias

Comenzamos con la union. Al ser una operacion binaria y asociativa, po-demos extenderla a una coleccion finita de uniendos. As, si A1, . . . , An sonconjuntos se tiene que

ni=1

Ai = {x | x Ai para alguna i {1, . . . , n}} .

Cuando la coleccion sea infinita, tambien habra union, pero ya no es unaconsecuencia de propiedades de operaciones binarias. Sera una nueva definicion.

Veamos la version mas general. Nos viene a decir que las uniones mas gene-rales seran conjuntos, siempre y cuando los uniendos pertenezcan a su vez, a unconjunto.

1.3.12. Union arbitraria. Sea C un conjunto cuyos elementos son, a su vez,conjuntos. La union arbitraria es el conjunto

C = {x | x A, para algun A C} .

En el caso de las familias, si I es un conjunto de ndices y C = {Ai | i I} ={Ai}iI , entonces escribimos

C =iI

Ai = {x | x Ai para algun i I} .

Al igual que sucede con la union, podemos definir la interseccion finita enconjuntos y familias. Si A1, . . . , An son conjuntos entonces la interseccion es elconjunto

ni=1

Ai = {x | x Ai para todo i {1, . . . , n}} .

1.3.13. Interseccion arbitraria. Sea C un conjunto, cuyos elementos son, asu vez, conjuntos. La interseccion arbitraria es el conjunto

C = {x | x A, para todo A C} .

En el caso de las familias, si I es un conjunto de ndices y C = {Ai | i I} ={Ai}iI , entonces escribimos

C =iI

Ai = {x | x Ai para todo i I} .

1.3.14. Ejemplo. Sea A = {a, b, c} y consideramos el conjunto de las partesde A, que denotamos P(A). Sea C = {{a, b}, {b, c}}. Entonces

1.C = A.

2.C = {b}.

1.4. PARES ORDENADOS, PRODUCTO CARTESIANO YRELACIONES BINARIAS15

1.3.15. Ejemplo. Sea P el conjunto de todos los numeros primos positivos.Para cada primo, p P, definimos el conjunto N p = {0, p, 2p, . . .}, o sea, losmultiplos naturales de p. Entonces:

1. La familia {N p}pP es un conjunto.2.pP N p = N.

3. Si p1, . . . , pn son primos cualesquiera entonces se tiene queni=1N pi =

{0, p1 pn, 2(p1 pn), . . . }4.pP N p = .

1.4. Pares ordenados, producto cartesiano y re-

laciones binarias

En ocasiones queremos hacer corresponder dos objetos, ya sea para compa-rarlos, sustituirlos o diversos objetivos mas. Una herramienta matematica porexcelencia para estudiar las correspondencias es la idea de pareja ordenada opar ordenado. En los estudios preuniversitarios invocamos las parejas ordenadasescribiendo (a, b). Vamos interpretar este concepto en terminos de conjuntos.

1.4.1. Definicion. Sean A y B conjuntos. La pareja ordenada formada pora A y b B es el conjunto

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

1.4.2. Observacion. La escritura de la definicion anterior puede reducirse mu-cho segun el caso. Por ejemplo (a, a) = {{a}}.1.4.3. Proposicion. Sean A y B conjuntos. Para cualesquiera elementos a, c A y b, d B se tiene que (a, b) = (c, d) si y solo si a = c y b = d.Demostracion. Se deduce de la igualdad {{a}, {a, b}} = {{c}, {c, d}}.

Ahora vamos a considerar el conjunto de las parejas ordenadas. Notese queuna vez establecida la definicion conjuntista de pareja ordenada volvemos aexpresiones completamente familiares.

1.4.4. Producto cartesiano. Sean A y B conjuntos. El producto cartesianode A y B es el conjunto

AB = {(a, b) | a A y b B} .

1.4.5. Observacion. Es claro que siendo el producto cartesiano un operacionbinaria, podemos extender el concepto a un numero finito de factores. En estecaso, es inmediato comprobar que el producto cartesiano de tres conjuntos no esasociativo; sin embargo, la identificacion (a, (b, c)) con ((a, b), c) es demasiadoclara como para pasarla de largo. Intuitivamente identificamos los conjuntos,


teniendo precauciones formales pues no tenemos por ahora una descripcion enterminos de conjuntos para la expresion (a, b, c). Mas adelante le daremos sen-tido, con un concepto mas general, el de producto directo.

1.4.6. Proposicion. Sea A un conjunto arbitrario. Entonces

A = A = .

Demostracion. Supongamos que A 6= . Entonces existe una pareja (a, b) A , con b . Pero eso es imposible. El otro producto es completamenteanalogo.

1.4.7. Observacion. De la propia definicion de pareja ordenada se desprendeque si A y B son conjuntos puede ocurrir que AB 6= B A.1.4.8. Ejercicios.

1. Sea A = 1, 2, 3 y B = a, b. Formar el producto cartesiano.

2. Probar que A (B C) = (AB) (A C)3. Probar que A (B C) = (AB) (A C)Ahora vamos expresar en terminos de conjuntos la nocion de relacion (o

correspondencia) entre dos objetos.

1.4.9. Definicion. Sean A y B conjuntos. Una relacion binaria (o correspon-dencia) entre elementos de A y de B es un subconjunto R AB.

Cuando (a, b) R decimos que a esta relacionado con b (dicho en ese orden)y escribimos aRb.

Cuando ocurra A = B, diremos simplemente que R es una relacion en A.

1.4.10. Observacion. Algunos autores obligan a que las relaciones sean con-juntos no vacos. Otros reservan el termino relacion para correspondencias enun solo conjunto.

Si no causa confusion, diremos relacion en vez de relacion binaria.

1.4.11. Observacion. Notese que puede ser que un elemento a este relacionadocon otro b, pero no recprocamente.

1.4.12. Ejemplos. 1. Si A = y B es arbitrario, entonces AB = y porlo tanto, la unica posible relacion entre A y B es la vaca.

2. Sean A y B conjuntos cualesquiera. Siempre se tienen dos relaciones (quepueden coincidir), una es el vaco y la otra es la total.

3. Sea R R2 la relacion dada por

R ={(x, y) R2 | x y} ;

es decir, xRy x y.

1.4. PARES ORDENADOS, PRODUCTO CARTESIANO YRELACIONES BINARIAS17

4. Sea R Z2 Z2 tal que

(a, b)R(a, b) ab = ab.

5. Sea A un conjunto. La diagonal de A2; es decir, (a, b) R a = b, esuna relacion (la igualdad).

6. Sea R Z2 la relacion dada por aRb a | b (a divide a b; o bien, b esmultiplo de a, vease 7.1.6).

7. Sea R R2 la relacion dada por xRy y = x2 + 1. En este caso R ={(x, y) R2 | y = x2 + 1} y podemos dibujarla en el plano.

1.4.13. Definicion. Sean A y B, conjuntos, y R una relacion entre A y B.

1. Al conjunto A se le llama conjunto inicial.

2. Al conjunto B se le llama conjunto final.

3. Se conoce como dominio de la relacion, al conjunto

DomR = {a A | b B, (a, b) R} .

4. Se conoce como imagen de la relacion, al conjunto

ImR = {b B | a A, (a, b) R} .

1.4.14. Ejemplo. Sea R R2 tal que

(x, y) R x = y2 xy

.

Se puede comprobar que DomR = R y que ImR = R \ {0}.Podemos representar las relaciones en graficas planas, como se hace en el

calculo. Vamos a ver un ejemplo, sean A = {a, b, c} y B = {a, b, c, d} yconsiderese la relacion R = {(a, b), (a, c), (b, c)}. La grafica es

a

b

c

d

a b c

Un ejercicio interesante es estudiar la relacion entre la forma de las graficasy las propiedades de las relaciones.

Captulo 2

Aplicaciones

2.1. Relaciones y aplicaciones

En cursos anteriores hemos visto que una aplicacion es una correspondenciaentre los elementos de dos conjuntos. Mas actualmente, en captulos anerio-res hemos expresado el concepto de correspondencia en terminos de conjuntos.Vamos a trabajar ahora el concepto de aplicacion en terminos de conjuntos.

2.1.1. Definicion. Sean A y B conjuntos. Una aplicacion entre A y B es unarelacion f AB que cumple la siguiente propiedad:

Para todo a A, existe un unico b B tal que (a, b) f .O bien, si (a, b) y (a, c) pertenecen a f , entonces c = d.

Notese que esta definicion en realidad no difiere de la que hemos visto enestudios previos. Estamos diciendo, en terminos de conjuntos, que una aplicaciones una correspondencia entre los elementos del conjunto A y del conjunto B,que satisfacen que para todo a A existe un unico elemento b B que lecorresponde.

2.1.2. Notacion. Sean A y B conjuntos y f una aplicacion de A a B. Escri-bimos entonces

f : A B o A f B.Ademas, si a A y (a, b) f , como b es unico podemos escribir

b = f(a).

En ocasiones expresamos la igualdad anterior b = f(a), que tambien lla-mamos regla de corespondencia, a traves de ecuaciones. Por ejemplo, podemosdefinir f : N N tal que f(n) = n2.

Cuando partimos de una ecuacion como por ejemplo y = x2 +1 y queremosinterpretarla como la regla de una relacion, la llamamos funcion1 y tenemos que

1Algunos autores no distinguen estos conceptos y a todo le llaman funciones.

19

20 CAPITULO 2. APLICACIONES

determinar su dominio de definicion es decir, el mayor conjunto que puedeser el dominio con el que podemos interpretar y = x2 + 1 como la regla decorrespondencia de una aplicacion.

Existen diversas maneras de representar graficamente a las aplicaciones. Va-mos a ver dos de ellas. La primera muy tpica:

Sean A = {a, b, c} y B = {a, b, c, d} conjuntos. Representamos la aplica-cion f : A B tal que f = {(a, a), (b, c), (c, d)} como

A Ba

b

c

a

b

c d

f

La siguiente es la grafica habitual de las coordenadas, que ya hemos vistopara relaciones.

a

b

c

d

a b c

Otra grafica habitual es la de la funcion y = x2 + 1

2.1.3. Observacion. En ocasiones, sobre todo en el calculo y la topologa,se suele identificar la aplicacion con la regla de correspondencia y a la propiaaplicacion con la grafica (o grafo).

2.1.4. Observacion. Como hemos dicho, una aplicacion es una relacion, queescribimos f : A B. De este modo tenemos

1. El dominio de f , que es Domf = A. Es decir, el dominio coincide con elconjunto inicial, as que este ultimo termino ya no se usa.

2. La imagen (o imagen directa) de f , que es Imf = f(A) B.Ademas, tenemos otras definiciones.

2.1.5. Definicion. Sean A y B conjuntos y f : A B.1. Al conjunto final B se le llama el codominio de f .

2.2. TIPOS DE APLICACIONES 21

2. A la igualdad b = f(a) se le llama la regla de correspondencia de f , ytiene especial sentido cuando se establece por formula.

3. Si (a, b) f , decimos que a es una preimagen de b y que b es la imagende a.

2.1.6. Ejemplos.

1. Sea A un conjunto. La relacion diagonal es una aplicacion que llamamosla identidad.

2. Sea f : Z N, tal que f(a) = a2. Entonces f es una aplicacion.3. La relacion xRy x2 + y2 = 1 no es una aplicacion. Sin embargo, y =

1 x2 s lo es.2.1.7. Ejemplo. Operaciones binarias. Sean A y B conjuntos no vacos. Unaley de composicion externa es una aplicacion

B A A

cuya imagen habitualmente denotamos b a en vez de (b, a). Un ejemplo tpicode esto es el producto por un escalar en espacios vectoriales.

Otra operacion binaria es la ley de composicion interna. Sea A un conjunto.Una operacion binaria en A es una aplicacion

B A A

cuya imagen habitualmente denotamos a a en vez de (a, a). Un ejemplotpico de esto es la suma en los numeros naturales.

2.2. Tipos de aplicaciones

2.2.1. Definicion. Sea f : A B una aplicacion.1. Decimos que f es inyectiva (o uno a uno) si para cada elemento de la

imagen, la preimagen es unica. Escribimos

f(a) = f(b) a = b o a 6= b f(a) 6= f(b)

2. Decimos que f es suprayectiva (o sobreyectiva o exhaustiva) si cubre todoel codominio. Escribimos

b B, a A tal que f(a) = b.

3. Decimos que f es biyectiva si es inyectiva y suprayectiva.

2.2.2. Ejemplos. Se pueden comprobar facilmente las siguientes afirmaciones:


1. La aplicacion f : N N tal que f(x) = 2x es biyectiva.

2. La aplicacion f : [1,) (0, 1] tal que f(x) = 1x es biyectiva.

3. Sean A = {a, b, c} y B = {a, b, c, d}. Entonces

a) La aplicacion f = {(a, b), (b, b), (c, b)} no es inyectiva ni suprayec-tiva (es constante).

b) La aplicacion f = {(a, b), (b, c), (c, d)} es inyectiva pero no supra-yectiva.

c) Ninguna aplicacion f : A B puede ser suprayectiva.

2.3. Imagenes directas e inversas

2.3.1. Definicion. Sea f : A B una aplicacion.1. Para X A, definimos la imagen (directa) de X como

f(X) = {f(x) | x X} = {b B | x X, b = f(x)}.

2. Para Y B, definimos la imagen inversa como

f(Y )1 = {a A | f(a) Y }

que tambien podemos escribir f1(Y ) teniendo cuidado de no confundirlacon la aplicacion inversa.

En el caso de las imagenes inversas, cuando el conjunto Y solo tiene unelemento, digamos Y = {y} se suele denotar f(y)1.2.3.2. Proposicion. Sea f : A B una aplicacion. La imagen directa verificalas siguientes propiedades.

1. f() = .

2. Si X Y entonces f(X) f(Y ).

3. Si X,Y A entonces f (X Y ) = f(X) f(Y ).

4. Si X,Y A entonces f (X Y ) f(X) f(Y ).

Mas en general, si I es un conjunto y {X}I una familia de subconjuntos deA entonces

f

(I

X

)=I

f (X) y f

(I

X

)I

f (X)

2.3. IMAGENES DIRECTAS E INVERSAS 23

Demostracion. 1. Es inmediata de (1.4.6).2. Si X = el resultado se sigue de lo anterior, y del hecho de que el

vaco esta contenido en todo conjunto (1.2.12). En otro caso, sea y f(X).Entonces existe x X tal que f(x) = y. Como X Y entonces x Y , luegoy = f(x) f(Y ).

Finalmente haremos la primera de las generales y los apartados restantes losdejaremos como ejercicio.

] Sea y f (IX). Entonces existe x IX tal que f(x) = y.Como x IX entonces x X para alguna I. Luego y f (X) If (X).

] Considerese y If (X). Entonces y f (X) para alguna I,as que existe x X tal que f(x) = y. De hecho x

I X, as que

y = f(x) f (IX).2.3.3. Ejercicio. Dar ejemplos de funciones f : A B y conjuntos X,Y Atales que f (X Y ) ( f(X)f(Y ) y f : A B y conjuntos X , Y A talesque f (X Y ) = f(X ) f(Y )Respuesta. Sean A = {1, 2}, B = {b}, X = {1} e Y = {2}. Sea f : A Btal que f es la constante b. Entonces X Y = , luego f (X Y ) = , perof(X) f(Y ) = B.2.3.4. Proposicion. Sea f : A B una aplicacion e Y B. La imageninversa verifica las siguientes propiedades.

1.(f(Y )1

)= f

(Y )1

.

2. Si I es un conjunto e {Y}I una familia de subconjuntos de B entonces

f

(I

Y

)1=I

f (Y)1

y f

(I

Y

)1=I

f (Y)1

Demostracion. Probaremos la ultima afirmacion. El resto se deja como ejercicio.] Sea x f (IY)1. Entonces f(x) IY, entonces f(x) Y paratodo I luego x f (Y)1 para todo I, as que x If (Y)1.

] Sea x If (Y)1. Entonces x f (Y)1 para todo I, lue-go f(x) Y para todo I, entonces f(x) IY. Por lo tanto x f(

I Y)1

.

2.3.5. Ejemplo. Sea f : R R dada por f(x) = x2. Sea X = [1,2] R. Sepuede comprobar que:

1. f(X) = [1, 2].

2. f (f(X))1 = [2,1] [1,2].


3. f(X)1 =[ 42,1] [1, 42]

4. f(f(X)1

)= [1,

2].

Como ejercicio se puede hacer lo mismo para la aplicacion dada por g(x) =senx, e Y = [2, 2].

2.4. Composicion

Permtasenos comenzar este parrafo con el siguiente ejercicio.

2.4.1. Ejercicio. Sean f : A B y g : B C aplicaciones. Definimos larelacion g f A C tal que (a, c) (g f) si y solo si, existe b B tal que(a, b) f y (b, c) g.

Probar que g f es una aplicacion.Respuesta. Sea a A. Entonces existe un unico b B tal que (a, b F y ununico c C tal que (b, c) g, por tanto (a, c) g f . Vamos a ver que c esunico. Si (a, c) g f entonces existe b B tal que (a, b) f y (b, c) g,pero la definicion de aplicacion nos dice que b = b y por tanto c = c.

Entonces podemos introducir el siguiente concepto.

2.4.2. Definicion. Sean f : A B y g : B C aplicaciones. Se conoce comola composicion de f seguida de g y la denotamos g f a la aplicacion siguiente:

1. g f : A C. Tal que2. (g f)(a) = g(f(a)).Entonces, en la composicion ocurre que Dom(g f) = Domf y el codominio

de la composicion es igual al codominio de g.

2.4.3. Ejemplos.

1. Sean f : N N y g : N Z, dadas por f(n) = 2n + 1 y g(n) = n2.Entonces la composicion de f seguida de g es

(g f)(n) = g(f(n)) = g(2n+ 1) = (2n+ 1)2.

Notese que la composicion de g seguida de f no puede definirse, porqueno coinciden la imagen de g y el dominio de f . Tambien notemos que aefectos practicos, eso podra corregirse. Una manera es la siguiente.

2. Al hilo del apartado anterior, sean f : N N y g : N N, dadas porf(n) = 2n + 1 y g(n) = n2. Ahora podemos hacer ambas composicionesy queda

(g f)(n) = (2n+ 1)2 y (f g)(n) = 2n2 + 1.

Notese que (g f) 6= (f g).

2.4. COMPOSICION 25

2.4.4. Teorema. Sean f : A B, g : B C y h : C D aplicaciones.Entonces h (g f) = (h g) f .Demostracion. La coincidencia de los dominios y codominios es clara, luego lascomposiciones pueden considerarse. Sea a A. Calculamos

(h (g f))(a) = h ([g f ](a)) = h (g(f(a))) = (h g)(f(a)) = ((h g) f)(a)

2.4.5. Proposicion. La composicion de aplicaciones inyectivas es inyectiva.

Demostracion. Sean f : A B y g : B C aplicaciones inyectivas. Seana, a A tales que (g f)(a) = (g f)(a). Entonces g(f(a)) = g(f(a)) y comog es inyectiva f(a) = f(a), y como f es inyectiva a = a.

2.4.6. Proposicion. La composicion de aplicaciones suprayectivas es supra-yectiva.

Demostracion. Sea c C. Entonces existe b B tal que g(b) = c y, a su vez,existe a A tal que f(a) = b. Luego (g f)(a) = c.2.4.7. Corolario. La composicion de aplicaciones biyectivas es biyectiva.

Demostracion. Inmediata de las dos anteriores.

2.4.8. Proposicion. Sean f : A B y g : B C. Entonces1. Si g f es inyectiva entonces f es inyectiva.2. Si g f es suprayectiva entonces g es suprayectiva.

Demostracion. Ejercicio.

2.4.1. Inversa de una aplicacion biyectiva

2.4.9. Notacion. Sea A un conjunto arbitrario. Denotamos a la aplicacionidentidad en A, como 1A : A A; es decir, 1A(a) = a, para todo a A.2.4.10. Definicion. Sea f : A B una aplicacion. Decimos que f tieneinversa si existe g : B A tal que g f = 1A y f g = 1B.

En este caso, decimos que f es una aplicacion invertible.

2.4.11. Proposicion. Sea f : A B una aplicacion invertible. Entonces lainversa es unica.

Demostracion. Supongamos que g y h son inversas. Entonces

g = g 1B = g (f h) = (g f) h = 1A h = h.


2.4.12. Notacion. Para una aplicacion invertible f : A B, denotamos lainversa como f1.

2.4.13. Teorema. Sea f : A B una aplicacion. Entonces f es invertible siy solo si es biyectiva.

Demostracion. Supongamos primero que f es invertible y veamos que es biyec-tiva. Sean a, a A. Si f(a) = f(a) entonces f1(f(a)) = f1(f(a)), luegoa = a. Ahora, sean b, b B. Hacemos a = f1(b) y a = f1(b) y se tiene quef(a) = b y f(a) = b. Por tanto es biyectiva.

Recprocamente, supongamos que f es biyectiva y queremos definir la in-versa. Para cada b B consideremos la imagen inversa f({b})1. Se afirmaque la imagen inversa tiene exactamente un elemento. Como f es sobre, en-tonces f({b})1 6= . Si a, a f({b})1 entonces b = f(a) y b = f(a), dedonde f(a) = f(a) y como es inyectiva a = a. Definimos g : B A tal queg(b) f(b)1, el unico elemento. Es inmediato comprobar que g es inversa def y por tanto g = f1.

2.4.14. Proposicion. Sean f : A B y g : B C aplicaciones invertibles.Entonces

(g f)1 = f1 g1.

Demostracion. Es un calculo directo.

2.4.15. Ejemplo. Las permutaciones. Sea 0 6= n N y A = {a1, . . . , an} unconjunto (con n elementos). Una permutacion es una biyeccion : A A. Laspermutaciones se denotan

=

(a1 . . . an

(a1) . . . (an)

).

Como ejemplo mas concreto, si A = {1, 2, 3, 4, 5} entonces una permutacionpuede ser

=

(1 2 3 4 53 4 5 1 2

).

Dado un conjunto no vaco A con n elementos, se denota S(A) el conjuntode las permutaciones de A. En caso de que A = {1, . . . , n} escribimos Sn.

Producto directo

Vamos a ver una extension de la idea del producto cartesiano (1.4.4) quellamaremos el producto directo. A diferencia del producto cartesiano, el pro-ducto directo no implica un orden en las coordenadas. Cuando el conjunto dendices esta ordenado, los identificamos, con la idea de extension del productocartesiano a un numero finito de factores (vease 1.4.5).

2.4. COMPOSICION 27

2.4.16. Definicion. Sea I un conjunto y F = {Ai}iI una familia de conjun-tos. Se conoce como producto directo de la familia F al conjunto

iIAi = {f : I iIAi | f(i) Ai} .

2.4.17. Notacion. Los elementos se denotan imitando la escritura de las pa-rejas ordenadas; es decir, si f iI Ai, escribimos f = (xi)iI .

Cuando I es finito y se escribe como una lista, escribimos sus elementosrepitiendo la lista en los ndices. No tenemos que seguir el orden de la lista,pero es conveniente y se acostumbra.

Por ejemplo si I = {1, . . . , n}, escribimosA1 An = {(x1, . . . , xn) | xi Ai} .

En caso de que no se quiera escribir a una familia con ndices, simplementese presupone; es decir, a la familia {A,B,C} la vemos como {A1, A2, A3} ousando cualquier otro conjunto de ndices con tres elementos.

2.4.18. Ejemplos.

1. R2 = {f : {1, 2} R | f(i) R, i = 1, 2} = {(x1, x2) | xi R}, elplano habitual.

2. Rn = {f : {1, . . . , n} R | f(i) R, i = 1, . . . , n}.3.

nN An = {f : N nNAn | f(n) An}, es un producto infinito. De-notamos sus elementos tambien como f = (x1, x2, . . . ).

Ya hemos comentado que el producto cartesiano con mas de dos factores noes asociativo (vease 1.4.5). El producto directo tampoco lo es, pero todo puedeidentificarse. Por ejemplo existe una biyeccion entre A (BC) y (AB)Cque nos permite escribir ABC, e identificar (a, (b, c)) ((a, b), c) (a, b, c).

La comprobacion es demasiado laboriosa como para ocuparnos de ella, peroen general depende del siguiente resultado que es mucho mas simple. Esta partela dejamos para los lectores mas curiosos.

2.4.19. Proposicion. Sean I y J conjuntos y F = {Ai}iI y G = {Bj}jJfamilias de conjuntos. Si existe una biyeccion : I J , junto con un conjuntode biyecciones {fi : Ai B(i)}iI entonces existe una biyeccion f :

iI Ai

jJ Bj, dada por f(x)(j) = f1(j)(x(1(j))

).

Demostracion. Notese que para cada x iI Ai y cada j J , se tiene ununico elemento f1(j)

(x(1(j))

), as que la relacion es aplicacion. Vamos a

ver que es biyectiva. Considerese g :

jJ Bi

iI Ai, dada por g(y)(i) =

f1i (y((i))) (notese que f1i : B(i) Ai). Es claro que tambien es aplicacion.

Se afirma que son inversas. Sea x iI Ai. Entoncesg(f(x))(i) = f1i (f(x)((i))) = f

1i

(f1((i))(x(

1((i)))))=

= f1i (fi(x(i))) = x(i).


De forma completamente analoga se tiene que f(g(y)) = y. Como tiene inversa,(2.4.13) nos asegura que f es biyectiva.

Producto directo arbitrario y axioma de eleccion

Como acabamos de ver, el producto directo finito puede identificarse conel producto cartesiano de conjuntos. De aqu se desprende que si tengo unafamilia finita de conjuntos no vacos, el producto de conjuntos es no vaco.Sin embargo, no podemos establecer directamente del primer captulo que elproducto arbitrario de una familia de conjuntos no vacos sea no vaca.

Los enunciados que veremos a continuacion, son equivalentes. Es facil com-probarlo.

2.4.20. Axioma de eleccion.

1. Sea I un conjunto arbitrario y {Ai}iI una familia. Si cada Ai no vacoentonces se puede elegir un elemento de cada conjunto.

O, equivalentemente

2. Sea I un conjunto no vaco y {Ai}iI una familia de conjuntos no vacos.Entonces el producto directo

iI Ai es no vaco.

Mas adelante veremos conexiones muy interesantes entre esta y otras pro-piedades.

Captulo 3

Orden

3.1. Conjuntos ordenados y sus elementos dis-

tinguidos

Recordemos que una relacion binaria, correspondencia o simplemente rela-cion (1.4.9 y 1.4.10) es un subconjunto del producto cartesiano entre dos con-juntos. En este captulo nos vamos a referir a cierto tipo de relaciones donde elconjunto inicial y el final, coinciden.

Comenzamos con una lista de propiedades que utilizaremos durante todo eltexto.

3.1.1. Definicion. Sea A un conjunto y R una relacion en A.

1. Decimos que R es reflexiva si (a, a) R, para todo a A.2. Decimos que R es simetrica si para a, b A, cada vez que (a, b) R se

tiene que (b, a) R.3. Decimos que R es antisimetrica si dados a, b A tales que (a, b) R y

(b, a) R, se tiene que a = b.4. Decimos que R es transitiva si, dados a, b, c A, cada vez que (a, b) R

y (b, c) R se tiene que (a, c) R.3.1.2. Ejemplo. Se pide que como ejemplo se clasifiquen las siguientes relacio-nes.

1. Se puede comprobar que si A = {a, b} y B = {1, 2} entonces existen 16relaciones entre A y B. Un ejercicio puede ser clasificarlas todas.

2. Sea A = N y aRb si y solo si a+ b es par.

3. Sea A = Z y aRb si y solo si a y b tienen distinta paridad.

4. Sea A = R y aRb si y solo si

29

30 CAPITULO 3. ORDEN

a) a b.b) a 6= b.c) |a+ b| 1.

5. Sea A = N y aRb si y solo si a divide a b (recordemos a | b, vease 7.1.6).6. Sea C un conjunto arbitrario y A = P(C). Definimos

a) aRb si y solo si a \ b = b \ a.b) aRb si y solo si a b.

7. Sea A = R2 y (x1, x2)R(y1, y2) si y solo si x1 < x2 o bien, si x1 = x2 setiene que x2 y2.

3.1.3. Ejercicio. El orden que hemos visto en el Ejemplo 7 se conoce comoorden lexicografico. Se pide extender la idea de orden lexicografico en dosdirecciones. La primera a cualquier numero de coordenadas. La segunda susti-tuyendo R por un conjunto ordenado arbitrario.

3.1.4. Definicion. Sea A un conjunto.

1. Una relacion en A se dice que es una relacion de orden (o un ordenparcial) si es reflexiva, antisimetrica y transitiva.

2. Un par (A,), donde A es un conjunto y es una relacion de ordenen A, se dice que es un conjunto ordenado (o parcialmente ordenado).

Si el contexto no deja dudas sobre la relacion de orden, solo escribiremosque A es un conjunto ordenado.

3.1.5. Notacion. Sea (A,) un orden parcial. Para a, b A, escribimos a < bsi a b y ademas a 6= b (tambien se escribe a b).3.1.6. Ejemplos.

1. Los ejemplos 4a, 5, 6a y 7, son todos ordenes. Los otros no lo son.

2. A = R con el orden a b a b (el orden usual).3. A = N \ {0} con el orden a b a | b (la divisibilidad 7.1.6).4. B = {1, 2, 3} y A = P(B) con el orden a b a b (la inclusion).

5. A = R2 con el orden (a1, a2) (b1, b2){a1 < b1; o bien

a1 = b1 y a2 b2Una propiedad notable de la relacion menor o igual de siempre en todos los

conjuntos de numeros es que dados dos numeros, siempre podemos distinguirentre tres posibilidades. Que sean iguales, que uno sea mayor que el otro oviceversa. Vamos a formalizar este concepto en la llamada ley de tricotoma.

3.1. CONJUNTOS ORDENADOS Y SUS ELEMENTOS DISTINGUIDOS 31

3.1.7. Definicion. Sea (A,) un conjunto ordenado.Decimos que A satisface la ley de tricotoma si, dados a, b A, ocurre una

y solo una de las tres condiciones siguientes:

1) a = b. 2) a < b. 3) b < a.

3.1.8. Definicion. Sea (, A) un conjunto ordenado.1. Decimos que la relacion de orden es un orden total o lineal, si satisface

la ley de tricotoma.

2. En el caso anterior, diremos ademas que A es un conjunto totalmente olinealmente ordenado.

3.1.9. Ejercicio. Considerense los conjuntos ordenados (A,) dados en losejemplos (3.1.6). Se pide decidir cuales de ellos son conjuntos totalmente orde-nados, razonando la respuesta.

Vamos a ver dos representaciones graficas para conjuntos ordenados. La pri-mera es conocida como los diagramas de Hasse o upward drawing, o simple-mente diagrama de grafo de un orden parcial.

Consideremos a, b (A,), tales que a b, pero a 6= b; es decir, a < b.Entonces dibujamos una lnea hacia arriba que conecte a con b. Lo hacemoscon todos los elementos de A (escritos en lista si es finito o en caso infinito,con formula cuando sea posible) con la condicion de no repetir ningun elementode A. Ademas, no escribimos bucles; es decir, no conectamos ningun elementoconsigo mismo.

3.1.10. Ejemplo. Sea C = {1, 2, 3} y A = P(C) junto con la relacion deinclusion que ya vimos. El diagrama de Hasse asociado es:

{1, 2, 3}

{1, 2} {1, 3} {2, 3}

{1} {2} {3}

HHHH

HH

HHHHHH

HHHH

HH

HHHH

HH

La otra representacion, tambien bastante conocida se llama las -matrices.Si tenemos un conjunto (parcialmente) ordenado, se construye entonces la matrizA con ndices en A, tal que

a,b =

{1 si a < b

0 otro caso


3.1.11. Ejemplo. Sea, otra vez, C = {1, 2, 3} y A = P(C) junto con la relacionde inclusion que ya vimos. La representacion de -matriz es

{1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}

{1}

{2}

{3}

{1, 2}

{1, 3}

{2, 3}

{1, 2, 3}

0 1 1 1 1 1 1 10 0 0 0 1 1 0 10 0 0 0 1 0 1 10 0 0 0 0 1 1 10 0 0 0 0 0 0 10 0 0 0 0 0 0 10 0 0 0 0 0 0 10 0 0 0 0 0 0 0

Vamos a ocuparnos de algunos elementos notables.

3.1.12. Definicion. Sea (A,) un conjunto ordenado y a A.1. Decimos que a es maximo de A, cuando b a para todo b A2. Decimos que a es el primer elemento o mnimo de A, cuando a b, para

todo b AEn el Ejemplo 3.1.10 podemos ver que el maximo {1, 2, 3} es el que ocupa

el extremo superior, mientras que el primer elemento ocupa el extremo inferior.En cambio en el Ejemplo 3.1.11, el maximo tiene toda su columna 1 menos laentrada de el mismo, mientras que el primer elemento es el que tiene toda sufila 1 excepto la entrada de el mismo.

3.1.13. Proposicion. Sea (A,) un conjunto ordenado. Entonces1. Si A tiene maximo entonces este es unico.

2. Si A tiene primer elemento o mnimo entonces este es unico.

Demostracion. Se deja como ejercicio.

3.1.14. Definicion. Sea (A,) un conjunto ordenado y a A.1. Decimos que a es un elemento maximal de A cuando se verifica que si

a b entonces b = a2. Decimos que a es un elemento minimal de A cuando se verifica que si

b a entonces b = a3.1.15. Ejemplos. Sobre los siguientes conjuntos, vamos a establecer los ele-mentos notables, cuando los haya.

1. A ={1n | n N

}, junto con el habitual. El maximo es 1 y no tiene

primer elemento.

2. A = {n N | n es par} junto con el habitual. No tiene maximo.Tiene primer elemento 0.

3.1. CONJUNTOS ORDENADOS Y SUS ELEMENTOS DISTINGUIDOS 33

3. A = NN junto con el orden lexicografico. No tiene maximales y el primerelemento es el (0, 0).

4. Un intervalo abierto en R. No tiene maximo, mnimo, maximales ni mini-males.

5. Un intervalo cerrado en R. El extremo de la izquierda es el minimo y elde la derecha es el maximo.

6. A = {a N | 1 6= a N}, junto con la inclusion. Si a es primo entoncesa N es maximal. No hay minimales.

7. A = N\{0, 1}, junto con la divisibilidad. No tiene maximales ni minimales.Tiene minimales. Todos los primos.

8. Sea C = {1, 2, 3} y A = P(C)\C, junto con la inclusion. Entonces A tieneprimer elemento y tiene maximales, pero no tiene maximo.

3.1.16. Definicion. Sea (A,) un conjunto ordenado, B A un subconjuntoy c A.

1. Decimos que c es una cota superior de B en A si b c, para todo b B2. Decimos que c es una cota inferior de B en A si c b, para todo b BEn los ejemplos de (3.1.15) se tiene: En (1), A puede verse contenido en Q

y as, 0 es cota inferior y todo racional q 1 es cota superior. En (2), A puedeverse contenido en N y as, el 0 es cota inferior (y primer elemento). En (3) (0, 0)es cota inferior y primer elemento, tambien. En (4) y (5) A puede verse conteni-do en R y as, todos los menores o iguales que el extremo izquierdo del intervaloson cotas inferiores, mientras que los mayores o iguales al extremo derecho delintervalo son cotas superiores. En (6) A puede verse contenido en A {N, } yas, se tiene que N es cota superior y es cota inferior. En (7), A puede versecontenido en N \ {0} y as, el 1 es cota inferior. En (8), A puede verse contenidoen P(C) y as, el {1, 2, 3} es cota superior.

3.1.17. Definicion. Sea (A,) un conjunto ordenado, B A un subconjuntoy c A.

1. Decimos que c A es el supremo (o extremo superior) de B en A si es elmnimo del las cotas superiores de B en A.

2. Decimos que c A es nfimo (o extremo inferior) de B en A si es elmaximo de las cotas inferiores de B en A.

3.1.18. Ejemplos. En los siguientes ejemplos vamos a establecer si existen elsupremo e nfimo de cada uno.

1. A ={1n | n N

} Q, junto con el habitual. El maximo y el supre-mo es 1. El nfimo es 0.


2. A = {n N | n es par} N junto con el habitual. El nfimo y primerelemento 0.

3. El intervalo (a, b) R. Supremo b e nfimo a.4. El intervalo [a, b] R. Supremo b e nfimo a.

3.1.19. Proposicion. Sea (A,) un conjunto ordenado y B A un subcon-junto, con el orden de A. Si B tiene supremo (o nfimo) en A este es unico.


El siguiente resultado nos muestra por que podemos decir el supremo enfimo, en vez de un supremo o nfimo.

3.1.20. Proposicion. Sea (A,) un conjunto ordenado y B A un subcon-junto, con el orden de A.

1. Si b B es un maximo (o mnimo) entonces b es tambien el supremo deB en A.

2. Si a A es supremo (nfimo) de B en A y a B, entonces a es maximo(mnimo) de A.


3.2. Conjuntos bien ordenados.

Es inmediato comprobar que los numeros naturales, enteros, racionales yreales son conjuntos con orden total o lineal. Sin embargo, existe una grandiferencia entre el orden de los numeros naturales y los enteros y los otros dos.A saber, podemos establecer el antecesor y el sucesor de cualquier numero entero(excepto el 0 en los naturales). Vamos a describir este fenomeno en el lenguaje delos conjuntos ordenados, estableciendo el concepto de conjunto bien ordenado.

3.2.1. Definicion. Sea (A,) un conjunto ordenado. Diremos que es bien or-denado si todo subconjunto no-vaco de A tiene un mnimo

3.2.2. Proposicion. Todo conjunto bien ordenado es totalmente ordenado. Elrecproco no se verifica.

Demostracion. Supongamos que un conjunto A es bien ordenado y considerodos elementos a y b, de A. Consideramos el subconjunto B = {a, b} de A.Como B no es vaco, tiene primer elemento. De ah se desprende la tricotomatrivialmente.

3.2.3. Ejemplo. Considerense N N junto con el orden lexicografico.(1, 1) < (1, 2) < . . . < (1, n) < . . .

< (2, 1) < (2, 2) < . . . < (2, n) < . . .

...

3.2. CONJUNTOS BIEN ORDENADOS. 35

Este conjunto esta bien ordenado.

Demostracion. Sea A NN no vaco y A1 = {x N | (x, y) A p.a. y N}.Claramente A1 6= y A1 N, por tanto, tiene primer elemento. Sea x0 A1,dicho primer elemento. Sea ahora A2 = {y N | (x0, y) A}. Como antes, A2tambien tiene primer elemento, digamos y0 A2.

Se afirma que (x0, y0) es el primer elemento de A. Sea (a, b) A, arbitrario.Como a A1 entonces x0 a. Si x0 < a ya terminamos, si no, entonces x0 = a,as que b A2 y as y0 b.

Intuitivamente, es claro que si tenemos un conjunto con un numero deter-minado de elementos, entonces es posible hacer una lista estableciendo un buenorden entre ellos; de hecho, si existe una biyeccion entre dos conjuntos y unotiene un buen orden, el otro podra ser dotado de un buen orden (probarlo comoejercicio). En el caso de conjuntos arbitrarios, eso ha de ser un axioma. Se cono-ce como el principio de la buena ordenacion. Es interesante hacer notar que esteaxioma es equivalente al axioma de eleccion (2.4.20) aunque la demostracionexcede los alcances de estos apuntes. Terminamos entonces con el enunciado.

3.2.4. Principio de la buena ordenacion. Si A es un conjunto no-vaco,entonces existe una relacion de orden en A tal que (A,) es un conjunto bienordenado.

Captulo 4

Relaciones de equivalencia

4.1. Conceptos basicos

Como hemos comentado, un metodo importante de las matematicas consis-te relacionar los elementos de un conjunto. Recordemos que en (3.1.1) vimosalgunas propiedades de las relaciones. Vamos a trabajar con ellas.

4.1.1. Definicion. Sea A un conjunto y R una relacion en A A. Decimosque R es una relacion de equivalencia si es reflexiva, simetrica y transitiva.

4.1.2. Ejemplos.

1. La diagonal; es decir, la igualdad, en cualquier conjunto.

2. En Z, la relacion a 5 b si y solo si 5 | (a b).3. En R, la relacion a b si y solo si a b Z.4. En los triangulos, la semejanza; es decir, triangulos cuyos angulos coinci-

den.

5. Cuando una relacion de orden es relacion de equivalencia?

6. Sea A = {a, b, c} y R = {(a, a), (b, b), (c, c), (a, b), (b, a), (a, c), (c, a)}. De-terminar si es relacion de equivalencia.

Otro ejemplo que puede resultar muy interesante es el siguiente.

4.1.3. Ejemplo. Sea f : A B una aplicacion. Definimos la relaciona a f(a) = f(a).

Se puede comprobar que es relacion de equivalencia.

4.1.4. Notacion. Si R es una relacion de equivalencia en A y a, b A estanrelacionados, entonces podemos escribir cualquiera de las tres siguientes formas

1. La tradicional: aRb, que tambien usamos para relaciones en general.

37

38 CAPITULO 4. RELACIONES DE EQUIVALENCIA

2. Tambien, a R b3. O la anterior, pero mas corta si no causa confusion, a b.

4.2. Clases de equivalencia

Sea A un conjunto no vaco y R una relacion de equivalencia en A. Para cadaelemento a A, podemos considerar el conjunto de todos aquellos elementosde A que esten relacionados con a. Estas colecciones son una herramienta detrabajo importante en algebra.

4.2.1. Definicion. Sea A 6= un conjunto y R una relacion de equivalencia enA. Para cada a A, su clase de equivalencia es el conjunto

[a] = {b A | a b }.

Las siguientes propiedades son muy faciles de verificar:

4.2.2. Proposicion. Sea A 6= un conjunto R una relacion de equivalencia enA. Las siguientes condiciones son equivalentes, para a, b A:

1. [a] [b] 6= .2. a R b.3. [a] = [b].

Demostracion. (1 2) Si x [a] [b] entonces a x y x b, luego a b.(2 3) Por hipotesis, a b. Si x [a] entonces x a y como a b se tiene

que x b, luego x [b]. Analogamente se tiene que cualquier y [b] verificay [a].

(3 1) Inmediato del hecho de que (a, a) [a].Si C es una clase de equivalencia cualquiera y a C entonces [a] = C,

trivialmente. En este caso decimos que a es un representante de C.Como se vera en los siguientes ejemplos, una correcta eleccion de los repre-

sentantes puede simplificar mucho la descripcion de las clases de equivalencia.

4.2.3. Ejemplos.

1. De las siguientes relaciones se pide determinar si son relaciones de equiva-lencia (si lo son, hay que probarlo, si no, indicar cual de las tres condicionesfalla). En caso de que lo sean, determinar las clases de equivalencia.

a) En Z, la relacion a b si y solo si a+ b es impar.b) En N N, la relacion (a, b) (c, d) si y solo si a+ d = b+ c.c) En A = {1, 2, 3}, la relacion R = {(1, 1), (1, 2), (2, 1), (2, 2)}.d) En Z (Z \ {0}), la relacion (a, b) (c, d) si y solo si ad = bc.

Que pasara si incluyesemos al (0, 0)?

4.3. EL CONJUNTO COCIENTE Y LA PROYECCION CANONICA 39

e) En Z, la relacion a 5 b si y solo si 5 | (a b) (vease el Ejemplo 2 de4.1.2).

f ) En el conjunto de todas las rectas en el plano, L, la relacion L1 L2si y solo si son paralelas.

2. Determinar las clases de equivalencia de (4.1.3).

4.3. El conjunto cociente y la proyeccion

canonica

4.3.1. Definicion. Sea A un conjunto y R una relacion de equivalencia en A.Se conoce como conjunto cociente de A, respecto de la relacion R, al conjuntode las clases de equivalencia de los elemetos de A respecto de R.

Se denota A/R, A/R o simplemente A/.

Vamos a calcular los conjuntos cociente de las relaciones de equivalencia enlos ejemplos de (4.1.2). Calcular los conjuntos cociente consiste en dar un con-junto de representantes (tambien llamado un juego completo de representantes)En el Ejemplo 1 de (4.1.2), la diagonal, se tiene que A/ = {[a] | a A}.En el Ejemplo 2 no podemos escribir Z/ = {[a] | a Z} porque la coleccionanterior no es un conjunto. Notese que [0] = [5] = [10] = [15] = . . . y as. Dehecho Z/ = {[0], [1], [2], [3], [4]}. Para el Ejemplo 3 tomando en cuenta quetodo numero real tiene una parte entera y una parte decimal que tiene valorabsoluto menor que 1, se tiene que R/ = {[r] | 0 r < 1}. Para el Ejemplo 4,asociamos a cada triangulo la terna sin orden de sus angulos internos, (, , ),tal que ++ = 180. Dos triangulos son semejantes si coinciden en sus ternassalvo el orden. As que A/ = {(, , ) | + + = 180}.4.3.2. Proposicion. Sea A un conjunto, R una relacion de equivalencia en Ay consideremos el conjunto cociente A/R. La correspondencia dada por a 7 [a]es una aplicacion que denotamos R : A A/RDemostracion. Se deja como ejercicio.

4.3.3. Definicion. Sea A un conjunto, R una relacion de equivalencia en A yconsideremos el conjunto cociente A/R. La aplicacion R : A A/R se conocecomo proyeccion canonica.

4.3.4. Ejemplos.

1. Vamos a continuar analizando la situacion del ejemplo que aparece en(4.1.3). Recordemos que se tienen dos conjuntos A,B y una aplicacionf : A B. Se define una relacion dada por a a si y solo si f(a) = f(b).Consideremos la correspondencia entre el conjunto cociente g A/ B, dada por g = {([a], f(a)) | a A}; o bien, g : A/ B, tal queg([a]) = f(a). Queremos ver que es aplicacion y que, como tal, es inyectiva.La particularidad que tiene esta correspondencia es que esta definida en


terminos de representantes y no de clases generales. Esto nos obliga acomprobar que la correspondencia no depende del representante que seelija. Es decir que si [a] = [a] entonces g ([a]) = g ([a]). En este caso, comog = f , sabemos de antemano que g es aplicacion, luego g([a]) = g([a]).Decimos entonces que g esta bien definida.

Para abreviar, se suele abusar de la notacion y definir directamente la pre-tendida aplicacion g : A/ B y luego afirmar y probar que la aplicacionesta bien definida. Probar que, de hecho, la aplicacion es inyectiva es facil.

2. El siguiente ejemplo puede resultar vistoso. Se considera la relacion deequivalencia en R, dada por

x y x y2

Z;

es decir, los numeros reales que distan en un multiplo de 2. Podemosentonces identificar a estas clases con los angulos, al elegir a los represen-tantes en el intervalo [0, 2); es decir, R/ = {[r] | 0 r < 2}. Ahora,considerese la circunferencia en el plano real de radio 1, con centro en (0, 0),que denotamos C(0, 1) o S1. Entonces la aplicacion f : R/ S1 talque f [x] = (cosx, senx) esta bien definida (en el sentido anterior) y esbiyectiva.

3. Continuamos con el ejemplo anterior y volvemos a considerar los angulos,R/ = {[x] | 0 x < 2}. Queremos comprobar que la correspondenciasuma de angulos + : R/ R/ R/ tal que [x] + [x] = [x + x]esta bien definida. Supongamos que x y y que x y. Entonces

x+ x (y + y)2

=x y2

+x y2

Z

y por tanto [x+ x] = [y + y].

4. Ahora vamos a ver un caso en el que las cosas no funcionan. Vamos a verque pasa si queremos definir el producto de angulos. Queremos ver si lacorrespondencia : R/ R/ R/ tal que [x] [x] = [x x] esta biendefinida. Si uno intenta hacer un argumento como antes las cosas no salen.Despues se comprueba que [ 12 ] = [

4pi+12 ], pero sus cuadrados no coinciden.

4.4. Relaciones de equivalencia y particiones

En esta seccion probaremos que toda relacion de equivalencia induce unaparticion y viceversa.

Sea A un conjunto no vaco y R una relacion de equivalencia. Consideremosel conjunto cociente A/ y cualquier elemento C A/ . Sabemos que sia, b C entonces [a] = C = [b]. Ademas de esto se tiene el siguiente resultado.4.4.1. Proposicion. Sea A un conjunto no vaco y R una relacion de equiva-lencia. Las clases de equivalencia de R verifican las siguientes propiedades:

4.4. RELACIONES DE EQUIVALENCIA Y PARTICIONES 41

1. [a] [b] = si y solo si a 6 b.2.

[a]A/[a] = A.

Demostracion. 1. Inmediato de (4.2.2). 2. Sea b A. Como b b entoncesb [b] [a]A/[a].

Este es un resultado importante dentro del algebra. De hecho, las familiasde conjuntos que verifican estas propiedades tienen nombre propio.

4.4.2. Definicion. Sean A e I conjuntos y P = {Bi}iI una familia de sub-conjuntos. Decimos que la familia P forma una particion para A si se verificanlas siguientes propiedades.

1. Bi Bj = si y solo si i 6= j.2. La union (disjunta)

iI Bi = A.

4.4.3. Observacion. Podemos separar la propiedad (1) en dos, si escribimos

Para cada i I, el conjunto Bi 6= .Para i, j I, si i 6= j entonces Bi Bj = .

Es decir, los elementos de una particion son conjuntos no vacos y disjuntos.

As que toda relacion de equivalencia induce una particion. El recproco severifica. Reuniendo todo se tiene el siguiente resultado.

4.4.4. Proposicion. Toda relacion de equivalencia induce una particion. Recpro-camente, toda particion determina una relacion de equivalencia.

Demostracion. Ya hemos visto en (4.4.1) que toda equivalencia determina unaparticion (en clases de equivalencia). Vamos entonces a ver el recproco.

Sea {Ci}iI una particion en A. Definimos la relacion

a b a, b Ci para alguna i I.

Se prueba entonces que es relacion de equivalencia y que las clases de equiva-lencia son justo las Ci.

Captulo 5

Conjuntos numericos

En este captulo vamos a definir y a establecer las propiedades basicas de losnumeros naturales, enteros, racionales, reales y complejos utilizando del lenguajede los conjuntos. La presentacion sera formal, aunque no totalmente, pues puedealargarse y complicarse mas de lo deseable para un primer curso.

5.1. Cardinalidad. Conjuntos finitos e infinitos

5.1.1. Definicion. Decimos que dos conjuntos X e Y son equipotentes si existeuna aplicacion biyectiva entre ellos.

5.1.2. Observacion. Notese que el ser equipotentes es una relacion reflexiva,simetrica y transitiva, y aun cuando sabemos que la coleccion de todos losconjuntos no es, a su vez, un conjunto, podemos agrupar a los conjuntos enclases de equipotencia.

5.1.3. Definicion. El cardinal de un conjunto es su clase de equipotencia.

Intuitivamente, podemos comprobar que los cardinales son colecciones dis-juntas y que todo conjunto tiene cardinal.

5.1.4. Notacion. Para un conjunto A, denotamos su cardinal con |A|.Entonces un numero cardinal es una clase de equipotencia de conjuntos.

Conjuntos finitos e infinitos

5.1.5. Definicion. Decimos que un conjunto A es infinito si existe un sub-conjunto propio B A que es equipotente a A; es decir, existe una biyeccionf : B A.5.1.6. Definicion. Decimos que un conjunto A es finito si no es infinito.

Aunque no hemos definido formalmente el concepto de numero natural oentero (lo haremos en breve) intuitivamente sabemos trabajar con ellos. Lossiguientes ejemplos nos pueden servir para fijar ideas.

43

44 CAPITULO 5. CONJUNTOS NUMERICOS

5.1.7. Ejemplos. Sea P el conjunto de los numeros enteros pares y P+ el delos pares positivos.

1. Probar que |N| = |P+| a traves de la biyeccion n 7 2n, con n N.2. Probar que |Z| = |P | a traves de la biyeccion m 7 2m, con m Z.3. Probar que |N| = |P | a traves de la biyeccion

n 7{n si n es par.

(n+ 1) si n es impar.

4. Por tanto, |N| = |Z|.5. Probar que si n N entonces Nn = {x N | x n} es finito.

5.1.8. Definicion. Un cardinal, decimos que es finito si tiene un representantefinito. En otro caso decimos que es infinito.

Por ejemplo,

0 = ||.1 = |{}|.2 = |{, {}}|.

y as, sucesivamente, hasta el 9. El resto de los numerales de los cardinales losobtenemos con la escritura decimal.

Ahora consideramos la coleccion de los cardinales finitos.

5.1.9. Definicion. La coleccion de los cardinales finitos se conoce como losnumeros naturales y se denota N.

No se puede demostrar, con los conceptos sobre conjuntos que hemos visto,que la coleccion anterior sea conjunto. Lo asumimos como un axioma.

5.1.10. Axioma del infinito. La coleccion de los numeros naturales es unconjunto.

5.1.11. Definicion. Sea n un cardinal y considerese un representante A. Seconoce como el sucesor de n, al cardinal n = |A {x}|, donde x es cualquierobjeto que no sea un elemento de A

5.1.12. Se puede probar (vease el Apendice) que si n N entonces n N. Denotamos n = n + 1. Esta propiedad nos da lugar a la definicion dela aplicacion sucesor, : N N tal que (n) = n. Tambien se prueba enel Apendice que la aplicacion es inyectiva. Como consecuencia se tiene elsiguiente resultado.

5.1.13. Proposicion. El conjunto de los numeros naturales es infinito.

5.1. CARDINALIDAD. CONJUNTOS FINITOS E INFINITOS 45

Demostracion. Sea M = {2, 3, . . .}. Modificamos el codominio de la aplicacionsucesor, definiendo : NM tal que (n) = n que claramente es inyectiva.De aqu se tiene de inmediato.

El siguiente postulado sera asumido sin demostracion. El proceso excede conmucho el objetivo principal de este captulo que es el conocimiento operativodel lenguaje de los conjuntos y sus propiedades. Para un estudio detallado veasepor ejemplo [6] o [9].

5.1.14. Principio de induccion en los numeros naturales. Si A N estal que

a) 1 A.b) n A n A

entonces A = N \ {0}.Hay una tecnica de demostracion llamada induccion matematica, que se

deriva directamente del principio de induccion. Vamos a enunciarla.

5.1.15. Induccion matematica. Supongamos que se quiere demostrar unapropiedad P (n), para n N. Los dos pasos a continuacion son suficientes:

1. Se demuestra la validez de P (0) o P (1). Es decir, que la propiedad valepara n = 0 o n = 1, como se quiera.

2. Se supone que P (n) es valida y a partir de ah, se prueba la validez paraP (n+ 1). Es decir, se prueba que si es valida para n, lo es para n+ 1.

Entonces, el principio de induccion nos asegura que el conjunto P = {x N |P (x) es verdadera} = N; es decir, que la propiedad vale para todos los numerosnaturales (tal vez, excepto el 0, si no se considero).

Mas adelante haremos varias demostraciones usando la tecnica de la induc-cion matematica, como ejemplo hagamos el siguiente ejercicio.

5.1.16. Ejercicio. Probar que n = |{1, . . . , n}|.Una variante muy util de la induccion matematica s la llamada induccion

fuerte. Vamos a eunciarla.

5.1.17. Induccion fuerte. Si queremos demostrar una propiedad P (n), paran N podemos proceder de la siguiente forma:

1. Se demuestra la validez de P (0) o P (1). Es decir, que la propiedad valepara n = 0 o n = 1, como se quiera.

2. Se supone que para cierto numero natural, k N, ocurre que P (n) esvalida para todo numero natural n < k y a partir de ah, se prueba lavalidez para P (k).

Entonces, P (n) es valida para todo n N.


Aplicaciones del principio de induccion.

Vamos a ver algunas aplicaciones del principio de induccion. Aun cuando nohayamos formalizado los conceptos de suma, producto y orden en los naturales,no quiere decir que no los conozcamos y no podamos trabajar con ellos.

5.1.18. Ejercicio. Probar por induccion las siguientes afirmaciones:

1. 1 + 2 + + n = n(n+1)2 .

2. 2n < n!

3. n3 n es multiplo de 6 para todo n N.

El conjunto de los numeros naturales que hemos construido satisface losaxiomas de Peano; a saber:

El conjunto N tiene un elemento 0 N (1 N).

Existe la funcion sucesor que es inyectiva.

El 0 no es sucesor de un numero natural.

Vale el principio de induccion.

Se puede probar que cualesquiera dos conjuntos que satisfagan estas condi-ciones son esencialmente el mismo (isomorfos). Eso se conoce como la unicidaddel sistema de Peano.

Orden en los numeros naturales

5.1.19. Definicion. Sean k y r cardinales. Decimos que k r si existen re-presentantes k = |A| y r = |B| con una aplicacion inyectiva f : A B.5.1.20. Ejercicio. Probar que 0 1 n para todo n N \ {0}.

Recordemos la definicion de buen orden en (3.2.1). Los numeros naturalesjunto con el orden definido forman un conjunto bien ordenado.

5.1.21. Principio del buen orden en los numeros naturales. (N,) esun conjunto bien ordenado; es decir, todo subconjunto 6= A N tiene primerelemento.

Vamos a comprobar que el principio del buen orden esta en armona con elconcepto de sucesor, como es de esperar.

5.1.22. Proposicion. Sea n N, arbitrario y considerese el conjunto de losnumeros naturales mayores que n; es decir, Mn = {x N | n < x}. Entoncesn es el primer elemento de Mn.

En consecuencia, si a, n N son tales que n a n entonces n = a oa = n.

5.1. CARDINALIDAD. CONJUNTOS FINITOS E INFINITOS 47

Demostracion. Sea a el primer elemento de Mn. Como n Mn entonces

a n. Por hipotesis, sabemos que existen A y N representantes de a y n,respectivamente, tales que existe una aplicacion inyectiva f : N A, pero nosobreyectiva. As, existe a A tal que a / Imf . Definimos g : N {N} A talque g(n) = f(n) para todo n N y g(N) = a. Es inmediato comprobar que ges aplicacion inyectiva y por tanto n a. Luego n = a.5.1.23. Observacion. El principio de induccion y el principio del buen ordenson equivalentes; es decir, si se asume uno de ellos el otro se puede demostrar.La demostracion puede hacerse como ejercicio; aunque es un poco larga, no esdifcil. Pero hay mas, se puede probar que, a su vez, los postulados anterioresson equivalentes al axioma de eleccion (2.4.20)

Operaciones en N

Las definimos de forma inductiva o recursiva.

5.1.24. La suma en N. Para n N, definimos1. n+ 1 = n.

2. Si tenemos definida n+m entonces n+m = (n+m).

Lo anterior viene a decir que n+(m+1) = (n+m)+1. Las demostracionesde las propiedades de la suma se pueden encontrar en el Apendice.

5.1.25. Propiedades de la suma en N.

1. (n+ 1) +m = n+ (m+ 1)

2. n+m = m+ n (conmutatividad).

3. (n+m) + r = n+ (m+ r) (asociatividad).

4. Si a+ c = b+ c entonces a = b (cancelacion).

5.1.26. El producto en N. Para n,m N, definimos1. n 1 = n.2. Si tenemos definido n m entonces n (m+ 1) = n m+ n.

5.1.27. Notacion. Escribimos, como siempre, indistintamente, n m = nm.Al igual que con la suma, las demostraciones de las propiedades del producto

se pueden encontrar en el Apendice.

5.1.28. Propiedades del producto.

1. (n+ 1)m = nm+m.

2. nm = mn (conmutatividad).

3. n(m+ k) = nm+ nk (distributividad).

4. n(mk) = (nm)k (asociatividad).


5.1.1. Orden y operaciones aritmeticas

Se puede comprobar que el orden en los numeros naturales verifica las si-guientes propiedades.

5.1.29. Teorema. Sean a, b, c N. Entonces1. a b si y solo si existe u N tal que a+ u = b.2. Si a b entonces a+ c b+ c para todo c N.3. Si a b entonces ac bc.

Demostracion. 1. Sean A y B, representantes de a y b, respectivamente. Porhipotesis, existe una aplicacion inyectiva f : A B. Hacemos B = B \ Imf .Se tiene entonces que u = |B|. Los otros se pueden probar facilmente porinduccion.

5.1.30. Notacion. En la situacion del teorema anterior, cuando a b, llama-mos u = b a.

5.2. Numeros enteros

Vamos a continuar la construccion de los conjuntos numericos bajo el len-guaje de los conjuntos.

5.2.1. Proposicion. Considese el conjunto Z = N N. La relacion

(a, b) (n,m) a+m = b+ n

es relacion de equivalencia.


5.2.2. Definicion. Llamamos numeros enteros al conjunto cociente

Z = Z/ .

5.2.3. Representantes notables. Sea (n,m) Z.1. Si n = m entonces (n,m) [(0, 0)]. Luego

[(0, 0)] = {(n,m) Z | n = m} .

2. Si n 6= m se tienen dos casos.a) Si n > m, haciendo a = n m (5.1.30), se tiene (n,m) [(a, 0)].

Luego

[(a, 0)] = {(n,m) Z | n > m, a = nm} .

5.2. NUMEROS ENTEROS 49

b) Si n < m, haciendo a = m n se tiene (n,m) [(0, b)]. Luego

[(0, b)] = {(n,m) Z | n < m, b = m n} .

5.2.4. Orden en los numeros enteros. Definimos

1. [(a, 0)] [(0, b)] para todo a, b N.2. [(a, 0)] [(b, 0)] si y solo si a b.3. [(0, a)] [(0, b)] si y solo si a b.

5.2.5. Notacion. 1. Denotamos con 0 a la clase [(0, 0)], el cero.

2. Denotamos con n a la clase [(n, 0)] y los identificamos con los numerosnaturales. Denotamos Z+ = {n Z | n N}.

3. Denotamos con n a la clase [(0, n)], que seran los numeros negativos.Z = {n Z | n N}.

5.2.6. Ejercicio. Probar directamente de la definicion anterior que para n,m Z se tiene n m si y solo si n m.5.2.7. Proposicion. (Z,) es un conjunto totalmente ordenado. Aun mas,todo entero tiene predecesor y sucesor.

Demostracion. Inmediata de (5.2.4).

Suma y producto en los enteros.

Seguimos con la lnea de presentar la construccion de los numeros enterossiguiendo el lenguaje de los conjuntos.

5.2.8. Suma. Definimos

+ : Z Z Z, tal que,+([(a, b)] , [(m,n)]) = [(a+m, b+ n)] ; es decir,

[(a, b)] + [(m,n)] = [(a+m, b+ n)]

5.2.9. Propiedades de la suma.

1. Esta bien definida (vease 4.3.4).

2. Es conmutativa.

3. Es asociativa.

4. Existe el neutro 0 = [0, 0].

5. Para todo entero no cero, existe el opuesto o inverso bajo la suma.


Demostracion. Vamos a comprobar que esta bien definida. El resto lo dejamoscomo ejercicio. Supongamos que a, a, b, b,m,m, n, n N son tales que [a, b] =[a, b] y [m,n] = [m, n]. Queremos ver que [a+m, b+n] = [a+m, b+n]. Porhipotesis, a+b = b+a ym+n = n+m, de donde a+b+m+n = b+a+n+m,luego (a+m)+(b+n) = (a+m)+(b+n), de donde se obtiene el resultado.

5.2.10. Producto. Definimos

: Z Z Z, tal que, ([(a, b)] , [(m,n)]) = [(am+ bn, an+ bm)] ; es decir,[(a, b)] [(m,n)] = [(am+ bn, an+ bm)]


1. Esta bien definido.

2. Es conmutativo.

3. Es asociativo.

4. Es distributivo.



5.3. Numeros racionales

Los numeros racionales seran ahora construidos a partir de los numerosenteros.

5.3.1. Notacion. Denotamos Z = Z \ {0}.5.3.2. Proposicion. Sea Q = Z Z. La relacion en Q dada por

[(a, b)] [(n,m)] am = bn

es una relacion de equivalencia.


5.3.3. Definicion. Llamamos numeros racionales al conjunto cociente

Q = Q/ .

5.3.4. Representantes notables. Considerese (n,m) Q.1. Si d|mcd(n,m) entonces [(n,m)] = [(n/d,m/d)]. Luego podemos elegir

representantes cuyas coordenadas son numeros coprimos (y son unicos).

2. [(0, 1)] = {(0, n) Q | n Z}.

5.3. NUMEROS RACIONALES 51

3. [(1, 1)] = {(n,m) Q | n = m}.

4. Identificamos con los enteros a los [(n, 1)] = {(a, b) Q | n = a/b Z}.5. [(1,m)] = {(a, b) Q | m = b/a Z}.

5.3.5. Orden en los numeros racionales. Sean [(n,m)] y [(a, b)] numerosracionales. Definimos

[(n,m)] [(a, b)] nb ma.

Ademas,

1. Decimos que un racional es positivo si es mayor que 0.

2. Decimos que es negativo si es menor que 0.

5.3.6. Proposicion. (Q,) es un conjunto totalmente ordenado.

Demostracion. Consideremos dos numeros racionales cuyos representantes tie-nen coordenadas coprimas, r = [n,m] y s = [a, b] y hagamos los productos nb yma. Como son enteros ha de ocurrir una de tres, nb = ma, nb > ma o nb < ma,lo que nos da la tricotoma en Q.

5.3.7. Observacion. Ningun racional tiene sucesor (ni predecesor).

Suma y producto en los enteros.

5.3.8. Suma. Definimos

+ : QQ Q, tal que,+([(a, b)] , [(m,n)]) = [(an+ bm, bn)] ; es decir,

[(a, b)] + [(m,n)] = [(an+ bm, bn)]

5.3.9. Propiedades de la suma.

1. Esta bien definida (vease 4.3.4).

2. Es conmutativa.

3. Es asociativa.

4. Existe el neutro, 0 = [0, 1].

5. Para todo racional no cero, existe el opuesto o inverso bajo la suma.

Aun mas, si n,m Z, [(n,m)] = [(n,m)] = [(n,m)].Demostracion. Ejercicio.


5.3.10. Producto. Definimos

: QQ Q, tal que, ([(a, b)] , [(m,n)]) = [(am, bn)] ; es decir,[(a, b)] [(m,n)] = [(an, bm)]


1. Esta bien definido.

2. Es conmutativo.

3. Es asociativo.

4. Es distributivo.


6. Todo racional no cero, [m,n] tiene inverso; [n,m].


5.3.12. Notacion. 1. Escribimos

m

n= [(m,n)] .

2. Denotamos con 0 a la clase 01 = [(0, 1)], el cero.

3. Denotamos con m a la clase m1 = [(m, 1)] y los identificamos con losnumeros enteros.

5.3.1. Escritura decimal de numeros racionales.

5.3.13. Definicion.

- Una sucesion de numeros (naturales, enteros, racionales, reales o comple-jos), (an)nN se dice eventualmente periodica si existe un m N y unentero positivo q > 0 tal que ai = ai+q, para todo i m.

- Si r es el menor de los m N que satisfacen dicha propiedad, entonces eltermino ar es llamado el termino inicial del periodo.

- Si p es el menor de los enteros positivos q anteriores, entonces p es llamadoel periodo de la sucesion.

5.3.14. Ejemplos. 1. Todas las sucesiones de numeros constantes o even-tualmente constantes. Una sucesion se dice eventualmente constante cuan-do existe un m N tal que ai = ai+1, para todo i m. En tal caso elperiodo de la sucesion es 1.

5.3. NUMEROS RACIONALES 53

2. La sucesion 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 2, 1, 3, 2, 1, 3, 2, 1, . . . es eventualmenteperiodica, con periodo p = 3 y con a10 como termino inicial del periodo.

5.3.15. Definicion. Una sucesion de numeros naturales (an)nN se dice de-cimal cuando an {0, 1, ..., 9} para todo n > 0 (notese que no hay restriccionsobre el termino a0).

5.3.16. Teorema. Dado un numero racional Q, 0, existe una unicasucesion decimal eventualmente periodica de numeros naturales (an)nN satis-faciendo que

0 a0 a110 a2

102 ... an

10n 0 y, por los casos anteriores,a = (b)q + r con 0 r < b = |b|. Por tanto, a = b(q) + r con 0 r < |b|.(4) Si a = 0, entonces 0 = b 0 + 0 y 0 < |b|, ya que por hipotesis b 6= 0.

Finalmente, para demostrar la unicidad de q y r supongamos que a = bq+r =bq + r con 0 r, r < |b|. Entonces, b(q q) = r r. Igualando los valoresabsolutos |b||q q| = |r r|, lo cual, dado que 0 r, r < |b|, solo puedecumplirse si q q = 0 y r r = 0.7.1.3. Definicion. En la situacion del teorema anterior, si a = bq + r, conb 6= 0 y 0 r < |b|, a q se le llama el cociente de la division y a r el resto.7.1.4. Ejemplo. Si a = 7 y b = 3, siguiendo la demostracion del teorematenemos que 7 = 3 2 + 1, de donde

7 = 3 (2) 1 = 3 (2) 3 + 3 1 = 3 (3) + 2.

Tenemos pues que el cociente es 3 y el resto 2.7.1.5. Ejercicio. Calcular la division entera de a entre b cuando: a = 27 yb = 4, a = 13 y b = 5, a = 46 y b = 9, a = 51 y b = 7.

7.1. ARTIMETICA DE LOS ENTEROS. 71

7.1.6. Definicion. Sean a, b Z. Decimos que b divide al numero a, y lodenotamos por b | a, si existe un c Z tal que a = bc. En este caso, se dice quea es multiplo de b. Si a 6= 0, decimos tambien que b es un divisor de a.

Observemos que si b 6= 0, decir que b divide a a es lo mismo que decir quela division entera de a entre b da resto cero.

Veamos ahora algunas propiedades elementales que usaremos constantemen-te:

7.1.7. Proposicion. Sean a, b, c, d Z.1. La divisibilidad es una relacion reflexiva y transitiva.

2. La divisibilidad no es antisimetrica, pero casi lo es. Si a | b y b | a entonces|a| = |b|.

3. a | b si y solo si a | b. Entonces, si b 6= 0, b y b tienen los mismosdivisores.

4. b | a si y solo si b | a (luego, todo numero tiene al menos un divisorpositivo).

5. Si c | a y c | b, entonces c | ra+ sb, para todo r, s Z.6. Si a | b y c | d entonces ac | bd.7. Si a | b entonces ra | rb para todo r Z.8. Si a | b entonces |a| |b|.


El maximo comun divisor es uno de los conceptos mas clasicos de la aritmeti-ca. Desde primaria concemos la definicion, pero falta demostrar su existencia.Comenzamos repasando la definicion y algunas propiedades basicas.

7.1.8. Definicion. Dados dos numeros enteros a, b, con, al menos, uno de ellosdistinto de cero, el maximo comun divisor de a y b se define como el mayorentero d tal que d | a y d | b. Si a = b = 0, su maximo comun divisor es cero.El maximo comun divisor de a y b se denotara por mcd(a, b) o mcd(b, a).

El maximo comun divisor existe pues el conjunto de divisores de dos numeroses finito y por tanto tiene maximo (recordemos que todo conjunto finito lineal-mente ordenado tiene maximo); aun mas, el maximo comun divisor siempre espositivo.

7.1.9. Proposicion. Si a, b Z, entonces:(1) mcd(a, b) = mcd(a, |b|) = mcd(|a|, |b|).(2) mcd(a, 0) = |a|.(3) mcd(a, b) = 0 si y solo si a = b = 0.

72 CAPITULO 7. EL ANILLO DE LOS NUMEROS ENTEROS.


Vamos a estudiar el maximo comun divisor utilizando las herramientas delos conjuntos que hemos desarrollado en captulos anteriores.

7.1.10. Teorema. Sean a, b Z, no cero ambos. El maximo comun divisor dea y b es el mnimo del conjunto de combinaciones lineales positivas de a y b; esdecir,

mcd(a, b) = mn{c = ra+ sb | c > 0 y r, s Z}.

Demostracion. Sea D = {ra + sb > 0 | r, s Z}. Notese primero que como ao b no son cero, D 6= y por tanto siempre existe = mnD. Se afirma que es el maximo comun divisor de a y b. Como D existen , Z tales que = a+b. Primero vamos a ver que es divisor comun. Por el algoritmo de ladivision (7.1.2) a = q+ r, con 0 r < . Entonces r = (1q)a+(q)b, conlo que r D o r = 0. Lo primero es imposible porque es mnimo. Luego r = 0y por tanto | a. Analogamente | b. Que es maximo se desprende directamentede (7.1.7); de hecho, todo divisor comun de a y b es divisor de .

7.1.11. Corolario. Sean a, b Z. Entonces existen r, s Z tales que mcd(a, b) =ra+ sb.

Demostracion. Si a = b = 0 hacemos r = s = 0 y tenemos el resultado. Si no sonambos cero, el resultado se desprende directamente del teorema anterior.

7.1.12. Definicion. Sean a, b Z y d = mcd(a, b). A una expresion d = ra+sbse le conoce como identidad de Bezout.

En la demostracion del teorema anterior hemos visto que el maximo comundivisor es, de hecho, multiplo de cualquier divisor comun. Vamos a expresar esojunto con otras propiedades que caracterizan al maximo comun divisor.

7.1.13. Proposicion. Sean a, b, c, d Z. Entonces d = mcd(a, b) si y solo sise cumplen las condiciones

(1) d | a y d | b.(2) Si c | a y c | b, entonces c | d.(3) d 0.

Demostracion. Supongamos d = mcd(a, b). De la definicion de maximo comundivisor tenemos las propiedades (1) y (3). La segunda es inmediata de (7.1.11).

Recprocamente, supongamos que a, b, d cumplen las tres condiciones delenunciado. Si a 6= 0 o b 6= 0, esta claro que d es el mayor de los enteros quedividen a a y b. Si a = b = 0, como 0 | a y 0 | b, la condicion (2) me dice que0 | d por lo que d = 0. Tambien en este caso se tiene d = mcd(a, b).

Este resultado puede generalizarse a un numero finito de enteros como vamosa ver a continuacion.


7.1.14. Definicion. Sean a1, . . . , an Z con algun ai 6= 0. El maximo comundivisor de a1, . . . , an, que denotaremos por mcd(a1, . . . , an), se define como elmayor entero d que los divide a todos. Definimos mcd(0, . . . , 0) = 0.

7.1.15. Proposicion. Sean a1, . . . , an Z. Entoncesmcd(a1, . . . , an) = mcd(mcd(a1, a2), a3, . . . , an).

Demostracion. Sea d = mcd(a1, . . . , an), e = mcd(mcd(a1, a2), a3, . . . , an) yf = mcd(a1, a2). Entonces, como d divide a a1, . . . , an, tenemos por la proposi-cion anterior que d divide a f, a3, . . . , an. Luego d e. Recprocamente, e dividea f, a3, . . . , an y, por tanto, e divide a a1, a2, . . . , an. Luego e d. Como d, e 0debe ser d = e.

7.1.16. Teorema. El maximo comun divisor de a1, . . . , an Z es la mnimacombinacion lineal positiva de dichos numeros.

As que existen enteros 1, . . . , n tales que

d = 1a1 + + nan.Demostracion. Inmediato por induccion, usando (7.1.10).

7.1.17. Corolario. Sean a1, . . . , an Z. Entonces d = mcd(a1, . . . , an) si ysolo si se cumplen las condiciones

(1) d | ai para todo i = 1, . . . , n.(2) Si c | ai para todo i = 1, . . . , n, entonces c | d.(3) d 0.


7.1.18. Ejemplo. Para calcular el maximo comun divisor de los numeros 45, 81, 12y 51 podemos proceder de la siguiente manera:

mcd(45, 81, 12, 51) = mcd(mcd(45, 81), 12, 51) = mcd(9, 12, 52) =

mcd(mcd(9, 12), 51) = mcd(3, 51) = 3.

7.1.19. Definicion. Dos enteros a, b se llaman primos entre s o coprimos simcd(a, b) = 1.

7.1.20. Proposicion. Sean a y b dos enteros no nulos. Entonces a y b soncoprimos si y solo si existen , Z tales que a+ b = 1.Demostracion. Inmediato de la definicion de coprimos y (7.1.11).

7.1.21. Proposicion. Sean a, b, c Z tales que a | bc. Si a y b son coprimos,entonces a | c.Demostracion. Sea 1 = a + b una identidad de Bezout. Multiplicando por ctenemos c = ac+ bc. Como a | bc, tambien a | c.

74 CAPITULO 7. EL ANILLO DE LOS NUMEROS ENTEROS.

7.1.22. Proposicion. Sean a, b, c Z. Si a y b son coprimos y a | c y b | centonces ab | c.

Demostracion. Considerese la identidad de Bezout ra + sb = 1. Por hipotesisca ,

cb Z. Entonces cara+ casb = ca , luego cr + casb = ca y as cb br + casb = ca , de

donde b( cbr +cas) =

ca , pasamos a multiplicando y se tiene ab | c.

7.1.23. Corolario. Sean a y b dos enteros no nulos y d = mcd(a, b). Si a = da

y b = db, entonces mcd(a, b) = 1.


El algoritmo de Euclides

Una forma efectiva de calcular el maximo comun divisor es mediante elalgoritmo de Euclides, para el cual necesitamos el siguiente resultado:

7.1.24. Proposicion. Sean a, b Z. Entonces, para todo s Z se tiene

mcd(a, b) = mcd(a sb, b) = mcd(a, b sa).

En particular, si b 6= 0 y a = bq + r es la division entera de a entre b, tenemosque

mcd(a, b) = mcd(b, r).

Demostracion. Si c | a y c | b, entonces c | a sb por (7.1.7). Recprocamente,si c | b y c | a sb, entonces c | a sb+ sb = a, tambien por (7.1.7).

7.1.25. Algoritmo de Euclides Vamos a calcular el maximo comun divisorde dos enteros mediante el algoritmo de Euclides que consiste en la aplicacionrepetida de la proposicion anterior. Podemos suponer que a y b son positivos ytenemos:

a = bq1 + r1 (a, b) = (b, r1) r1 < bb = r1q2 + r2 (b, r1) = (r1, r2) r2 < r1r1 = r2q3 + r3 (r1, r2) = (r2, r3) r3 < r2

......

...

Dado que b > r1 > r2 > r3 > 0 debe obtenerse resto cero en unnumero finito de pasos:

rn2 = rn1qn + rn (rn2, rn1) = (rn1, rn)rn1 = rnqn+1 (rn1, rn) = rn.

Luego (a, b) = rn.Los valores x e y de la expresion rn = ax+ by pueden obtenerse eliminando

los r1, . . . , rn1 con una sustitucion regresiva, en las igualdades anteriores apartir de la penultima igualdad.


Por ejemplo, para los enteros a = 252 y b = 198 hacemos las divisiones y setiene

252 = 198 1 + 54198 = 54 3 + 3654 = 36 1 + 1836 = 18 2.

y, a partir de la penultima igualdad vamos despejando y sustituyendo, ob-tenemos

18 = 54(1) + 36(1) = 54 + (198 54 3)(1)= 198(1) + 54(4) = 198(1) + (252 198 1) 4= 198(5) + 252(4).

La igualdad 18 = 198(5) + 252(4) es entonces una identidad de Bezout.

7.1.2. Mnimo comun multiplo

7.1.26. Definicion. Dados dos numeros enteros a, b distintos de cero, el mni-mo comun multiplo de a y b se define como el menor entero positivo que esmultiplo de a y de b a la vez.

Si a o b son cero, entonces el mnimo comun multiplo de a y b es 0. Sedenotara por mcm(a, b).

La existencia del mnimo comun multiplo esta garantizada ya que el conjuntode todos los enteros positivos que son multiplos comunes a a y b es no vaco y,por tanto, debe tener un primer elemento.

7.1.27. Proposicion. Si a, b Z, entonces:

(1) mcm(a, b) = mcm(a, |b|) = mcm(|a|, |b|).

(2) mcm(a, b) = 0 si y solo si a = 0 o b = 0.

(3) mcm(a, ab) = |ab|.

Demost

conjuntos y teoria de grupos

Documents