algebra superior i reyes

81
Álgebra Superior Araceli Reyes Septiembre 2003

Upload: amtzcastan

Post on 29-Jun-2015

2.020 views

Category:

Documents


16 download

DESCRIPTION

Un curso sencillo de introducción al álgebra en escuelas superiores

TRANSCRIPT

Page 1: Algebra superior i   reyes

Álgebra Superior

Araceli Reyes

Septiembre 2003

Page 2: Algebra superior i   reyes

ii

Page 3: Algebra superior i   reyes

Índice general

1. Método axiomático 11.1. Introducción al método axiomático . . . . . . . . . . . . . . . . . . . 11.2. Axiomas y Teoremas. . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3. Deducciones y demostraciones . . . . . . . . . . . . . . . . . . . . . . 3

2. Conjuntos y Funciones 52.1. Terminología y notación de conjuntos . . . . . . . . . . . . . . . . . 52.2. Propiedades de las operaciones entre conjuntos. . . . . . . . . . . . . 62.3. Productos cartesianos . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3. Los números naturales 93.1. Axiomas de Peano . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2. Propiedades de las operaciones entre naturales . . . . . . . . . . . . 93.3. Demostraciones por inducción . . . . . . . . . . . . . . . . . . . . . . 103.4. Definiciones inductivas . . . . . . . . . . . . . . . . . . . . . . . . . . 153.5. Cardinalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.6. Relación de orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.6.1. Propiedades del orden. . . . . . . . . . . . . . . . . . . . . . . 173.7. Principio del buen orden . . . . . . . . . . . . . . . . . . . . . . . . . 183.8. Funciones y relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.8.1. Dominio y contradominio . . . . . . . . . . . . . . . . . . . . 193.9. Clasificación de funciones . . . . . . . . . . . . . . . . . . . . . . . . 203.10. Composición de funciones . . . . . . . . . . . . . . . . . . . . . . . . 213.11. Funciones inversas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

4. Relaciones binarias 254.1. Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.2. Relaciones de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . 25

5. Matemáticas discretas 295.1. Relaciones entre conjuntos finitos . . . . . . . . . . . . . . . . . . . . 29

5.1.1. Gráfica dirigida. . . . . . . . . . . . . . . . . . . . . . . . . . 295.2. Representación matricial de una relación. . . . . . . . . . . . . . . . 34

5.2.1. Definiciones del álgebra matricial en general . . . . . . . . . . 345.2.2. Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355.2.3. Operaciones entre relaciones: . . . . . . . . . . . . . . . . . . 375.2.4. Propiedades de las relaciones y estructura de las matrices . . 39

6. Conteo 436.1. Principios básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

6.1.1. Suma y resta para contar . . . . . . . . . . . . . . . . . . . . 446.2. Principio de inclusión y exclusión para dos y tres conjuntos . . . . . 47

6.2.1. Producto y división para contar . . . . . . . . . . . . . . . . . 49

iii

Page 4: Algebra superior i   reyes

iv ÍNDICE GENERAL

6.2.2. Integración de los principios de suma y producto . . . . . . . 566.2.3. Miscelánea de problemas . . . . . . . . . . . . . . . . . . . . . 58

7. Los números enteros. 617.1. El anillo de los números enteros . . . . . . . . . . . . . . . . . . . . . 617.2. Propiedades de las operaciones entre enteros. . . . . . . . . . . . . . 617.3. Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

7.3.1. Algoritmo de la división . . . . . . . . . . . . . . . . . . . . 637.3.2. Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . 65

7.4. Números primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687.5. Teorema de factorización única . . . . . . . . . . . . . . . . . . . . . 69

8. Congruencias 718.1. Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718.2. Propiedades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 738.3. Teorema chino del residuo . . . . . . . . . . . . . . . . . . . . . . . . 74

9. Bibliografía 75

Page 5: Algebra superior i   reyes

Capítulo 1

Método axiomático

1.1. Introducción al método axiomáticoEl conocimiento matemático prácticamente nació con la cultura humana. Los

primeros temas de los que se tiene noticia que había algún conocimiento matemáti-co son de geometría. Los Babilonios y los Egipcios descubrieron una gran cantidadde relaciones geométricas, como el teorema de Pitágoras, que se siguen utilizan-do hasta nuestros días, para desde resolver problemas muy prácticos de ingenieríahasta aspectos muy teóricos de las matemáticas modernas. La manera como sedescubrieron esos conocimientos fue empíricamente. Del conocimiento del que hayinformación de esa época, sabemos que algunos de los resultados a los que ellosllegaron eran erróneos. Sirva como ejemplo la fórmula que utilizaban los babiloniospara calcular el área de un cuadrilátero cuyos lados consecutivos miden a, b, c y dque es incorrecta

K =(a+ c) (b+ d)

4Muchos conocimientos obtenidos empíricamente durante este periodo fueron incor-rectos. Sirva esta afirmación para reflexionar acerca de como podemos descubrirnuevo conocimiento matemático.Claramente transcurrieron miles de años con esta situación y fue hasta alrededor

del año 624 A.C. con Tales de Mileto que planteó el primer estudio sistemático de lageometría y se cuestionó sobre la veracidad de los resultados. Tales fue el primero enhacer una demostración. Pasaron cerca de 300 años, hasta Euclides (325−265 A.C.)que escribió sus Elementos que contienen una cadena de 465 afirmaciones ligadaslógicamente por deducción. Entre estos dos matemáticos vivió Pitágoras (569−475A.C.) que tuvo como mérito escribir formalmente y demostrar el famoso teoremaque conocemos. Con Euclides nace el método utilizado en las matemáticas para suconstrucción: el método axiomático. La base del método axiomático es el silogismoo como lo conocemos coloquialmente la deducción.En conclusión, experimentar y jugar con los objetos matemáticos, llámense fig-

uras geométricas o símbolos, nos permite descubrir relaciones para entenderlas. Estejuego o experimentación se inicia normalmente con el propósito de resolver algúnproblema. La formulación de una afirmación que suponemos correcta no es suficientepara incorporarla al conocimiento matemático. Para tener certeza de la veracidadde la proposición es necesario que se pueda deducir de un conjunto de afirmacionesprobadas como verdaderas anteriormente. Para tener un punto de partida y poderfundamentar las afirmaciones se parte de un conjunto de afirmaciones que no sedemuestran y que conocemos como axiomas.Las reglas del álgebra se sistematizaron posteriormente con Descartes(1596 −

1650 A.C.) que estaba buscando un método general para resolver los problemas

1

Page 6: Algebra superior i   reyes

2 CAPÍTULO 1. MÉTODO AXIOMÁTICO

intrincados de la geometría a los que habían llegado. Muchas de estas reglas tienesu fundamentación en la geometría.

1.2. Axiomas y Teoremas.

Los axiomas son afirmaciones matemáticas que no se demuestran y que sonel punto de partida de un conjunto de conocimientos matemáticos. Por ejemplose manejan axiomas de los números reales que sirven de base para demostrar lasdemás propiedades de los números reales. Euclides escribió sus libros basado encinco axiomas o postulados que utilizó como base para deducir el resto de los 465teoremas que demostró en sus libros.

A los matemáticos a los que les tocó darle solidez lógica al conocimiento matemáti-co vivieron a finales del siglo XIX y principios del XX. Entre ellos esta Bertrand Rus-sell, Alfred North Whitehead, Kurt Gödel y muchos mas que llegaron a la conclusiónque un concepto básico para las matemáticas es el de conjunto . La matemática sereformuló completamente utilizando el concepto de conjunto como básico.

Un teorema es una afirmación que se puede deducir de axiomas o afirmacionesanteriores que han sido demostradas como verdaderas previamente .

Con la comprensión de esta relación lógica entre axiomas y teoremas fue posi-ble cuestionar la veracidad incontrovertible de los axiomas y jugar a cambiar al-guno para realizar deducciones diferentes a las ya obtenidas. Al primer sistemade conocimientos matemáticos al que se le aplicó este cuestionamiento fue a lageometría. El quinto postulado de Euclides se cambió y esto dió origen a las geometríasno euclidianas.

Esta nueva visión acerca del conocimiento matemático se prestó a que muchaspersonas pensaran que las matemáticas solamente eran una relación lógica entreafirmaciones y pretendieron olvidarse de sus orígenes empíricos y el propósito deeste conocimiento, que es resolver problemas.

El objetivo del trabajo de un matemático es producir afirmaciones verdaderasbasadas en conocimiento anterior. Los axiomas son afirmaciones que nos parecenverdaderas en las circunstancias y para los fines que se formulan, pero los axiomasno son inamovibles ni absolutos.

Hay varias formas de descubrir nuevos teoremas, entendiendo las relaciones lóg-icas o jugando con los objetos matemáticos o desarrollando cierta intuición acercade los objetos.

Una vez que casi estamos seguros de que un resultado es verdadero solamentees cuestión de encontrar la cadena de afirmaciones que a partir de afirmacionesque sabemos verdaderas nos lleva a la primera afirmación que supusimos verdadera.Esto se llama hacer una demostración de una conjetura. La conjetura es el resultadoo afirmación que suponemos verdadero pero que no estamos ttalmente seguros quesea verdadero Podremos afirmar su veracidad cuando se haya deducido.

Un corolario es una afirmación que se deduce inmediatamente de un teorema.

Un lema es una afirmación intermedia, que se vuelve importante por si misma,en la cadena de demostración de un teorema.

En general, solamente se escriben afirmaciones verdaderas en matemáticas, poreso a veces las matemáticas nos parecen rígidas y difíciles, pero si recordamos quepara llegar a escribir de esa forma el matemático tuvo que equivocarse y corregirserá mas fácil intentar resolver problemas.

Page 7: Algebra superior i   reyes

1.3. DEDUCCIONES Y DEMOSTRACIONES 3

1.3. Deducciones y demostracionesTodos los seres humanos pensantes utilizamos las deducciones a diario. Todos

sabemos sacar conclusiones a partir de ciertas afirmaciones. En ocasiones nos equiv-ocamos al formular nuestras primeras afirmaciones pero todos sabemos deducir. Porejemplo:

Primera afirmación: Estamos en época de lluvias.

Segunda afirmación: El cielo esta nublado y las nubes son negras.

¿Cuál sería nuestra conclusión casi inmediata?Nuestra vida cotidiana esta llena de estos ejemplos.También hemos escrito demostraciones matemáticas sin ser concientes de ello.

Por ejemplo:

Theorem 1 La ecuación x2 − x− 2 = 0 tiene como solución a 2 y −1.

Proof. La expresiónx2 − x− 2

se factoriza comox2 − x− 2 = (x− 2) (x+ 1)

por lo tanto los valores x = 2 y x = −1 son solución de la ecuación.Lo mas seguro es que hayamos escrito:

x2 − x− 2 = (x− 2) (x+ 1)∴ x = 2, x = −1

o bien que hayamos aplicado la fórmula de la ecuación de segundo grado

A = 1, B = −1, C = −2

x =(−1)2 ±p1− 4 (1) (−2)

2=1±√92

=1± 32

=

½2−1

o utilizando cualquier otro método para reolver la ecuación de segundo grado.Lo importante es que se han escrito demostraciones sencillas de matemáticas.El propósito de este curso es revisar conocimientos sobre los números que se han

adquirido a través de los años en la escuela pero se vean a través de la óptica de losconjuntos y las deducciones de propiedades a partir de ciertas afirmaciones sobreellos que se van a considerar axiomas y se refieren a las propiedades de cada uno delos sistemas que se van a considerar: naturales, enteros, racionales.

Exercise 2 Demuestra que −2 es una raíz de la ecuación x2 + 2x = 0.

Exercise 3 Enuncia el teorema de Pitágoras.

Exercise 4 A partir de la conocida propiedad que afirma que la suma de los tresángulos internos de un triángulo es 180o, demuestra que en un triángulo rectángulolos otros dos ángulos son complementarios. (suman 90o).

Page 8: Algebra superior i   reyes

4 CAPÍTULO 1. MÉTODO AXIOMÁTICO

Page 9: Algebra superior i   reyes

Capítulo 2

Conjuntos y Funciones

Los conceptos que no se van a definir en teoría de conjuntos son: conjunto,elemento y pertenencia.

2.1. Terminología y notación de conjuntos

.Las letras mayúsculas se utilizarán para denotar a los conjuntos, las letras minús-

culas se utilizarán para denotar a los elementos. El símbolo ∈se utilizará para perte-nencia. Por ejemplo a ∈ A se lee, el elemento a está en el conjunto A.

Definition 5 Un conjunto A es subconjunto de un conjunto B si todos los elemen-tos del conjunto A pertenecen al conjunto B. Simbólicamente: para todo elementoa ∈ A se tiene que a ∈ B.

Notation 6 A ⊂ B denota que el conjunto A es subconjunto del conjunto B.

Example 7 Si A = Z y B = Q entonces Z ⊂ Q.

Example 8 También Q ⊂ R.

Example 9 N ⊂ Z.

Exercise 10 Escribe en notación de conjuntos: Todo número entero es un númeroreal.

Exercise 11 Escribe en palabras N ⊂ Q.

Definition 12 Dos conjuntos A y B son iguales si A ⊂ B y B ⊂ A.

Notation 13 A = B denota que los conjuntos son iguales o tienen los mismoselementos.

Example 14 Sea A = {a, e, i, o, u} y B = {vocales del alfabeto latino }. EntoncesA = B.

Example 15 Sea A = {a ∈ Z |a = 2n+ 1 para alguna n ∈ Z}y sea B = {b ∈ Z | b es impar}entonces A = B.

Exercise 16 Describe de dos formas diferentes al conjunto de números enterospares.

5

Page 10: Algebra superior i   reyes

6 CAPÍTULO 2. CONJUNTOS Y FUNCIONES

Exercise 17 Describe de dos formas diferentes al conjunto de parejas de enteros

cuyo cociente es igual al racional1

4.

Definition 18 El conjunto universal es el conjunto que contiene a todos los con-juntos.

Definition 19 El conjunto vacío es el conjunto que no tiene elementos.

Notation 20 Se denota por U al conjunto universal y por ∅ al conjunto vacío.Remark 21 Dado un conjunto A cualquiera A ⊂ U y ∅ ⊂ A.

2.2. Propiedades de las operaciones entre conjun-tos.

Las operaciones básicas entre dos conjuntos son la unión y la intersección.

Definition 22 Dados dos conjuntos A y B se dice que el conjunto formado por loselementos que están en A o están en B es la unión de ambos. Simbólicamente

A ∪B = {x ∈ U |x ∈ A ó x ∈ B }Remark 23 A ⊂ A ∪B y B ⊂ A ∪B.Definition 24 Dados dos conjuntos A y B se dice que el conjunto intersección esel conjunto formado por los elementos que están en A y están en B. Simbólicamente

A ∩B = {x ∈ U | x ∈ A y x ∈ B}Remark 25 A ∩B ⊂ A y A ∩B ⊂ B.

La operación sobre un conjunto solamente es el complemento.

Definition 26 Dado un conjunto A se define el complemento de A como el conjun-to de los elementos que están en el universo U pero no están en A. Simbólicamente

Ac = {x ∈ U | x /∈ A}Theorem 27 A ∪Ac = U

Proof. Primero se demostrará que A ∪ Ac es un subconjunto de U. Como Uesel conjunto universal entonces A ⊂ U y Ac ⊂ U. Por lo tanto A ∪Ac ⊂ U.Ahora se demostrará que U es un subconjunto de A ∪ Ac. Sea u ∈ U. Hay dos

posibilidades solamente u ∈ A o u /∈ A. Si u ∈ A entonces U ⊂ A ∪ Ac.Si u /∈ Aentonces u ∈ Ac,por lo tanto U ⊂ A ∪Ac.

Theorem 28 A ∩Ac = ∅Proof. Para demostrar la igualdad de conjuntos hay que demostrar ambas

contenciones:∅ ⊂ A ∩ Ac y A ∩ Ac ⊂ ∅. Como el ∅ es subconjunto de todos losconjuntos entonces ∅ ⊂ A ∩Ac.Supongamos x ∈ A ∩ Ac.Esto significa que x ∈ A y x ∈ Ac.Que quiere decir

x ∈ A y x /∈ A, lo cual es una contradicción. Por tanto, no existe x ∈ A ∩ Ac. Portanto A ∩Ac = ∅.Theorem 29 A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C)

Page 11: Algebra superior i   reyes

2.3. PRODUCTOS CARTESIANOS 7

Proof. Para demostrar la igualdad de conjuntos hay que demostrar que A ∩(B ∪C) ⊂ (A ∩B) ∪ (A ∩C) y que (A ∩B) ∪ (A ∩ C) ⊂ A ∩ (B ∪ C) .Para demostrar la primera parte considerar x ∈ A ∩ (B ∪ C) .Esto significa

que x ∈ A y x ∈ B ∪ C. Esto quiere decir que x ∈ A y (x ∈ B o x ∈ C).Haydos posibilidades (x ∈ A y x ∈ B) o (x ∈ A y x ∈ B). Esto quierde decir quex ∈ (A ∩B) ∪ (A ∩C) .Para demostrar la segunda parte considerar x ∈ (A∩B)∪(A ∩ C) . Esto significa

que x ∈ (A ∩ B) o x ∈ (A ∩ C).En el caso de que x ∈ (A ∩ B) entonces x ∈ A yx ∈ B.Los siguientes dos teoremas se conocen como las Leyes de De Morgan.

Theorem 30 (A ∪B)c = Ac ∩Bc

Theorem 31 (A ∩B)c = Ac ∪Bc

Exercise 32 Demostrar los últimos dos teoremas.

2.3. Productos cartesianosEl concepto de función surge primero relacionado con el Cálculo Diferencial

e Integral. De hecho cuando se trabaja en ese tema casi todas las funciones quese manejan son funciones que tienen una gráfica asociada y que se dibujan en elplano cartesiano R×R. En este contexto no se hace énfasis en el dominio y elcontradominio de la función. Al generalizar el concepto de función donde en lugardel conjunto de los números reales se toma cualquier conjunto como el dominio y otrocomo el contradominio hay que dar una definición general de producto cartesiano.

Definition 33 Dados dos conjuntos cualesquiera A y B se define el producto carte-siano de ambos como el conjunto formado por las parejas de elementos (a, b) talesque a ∈ A y b ∈ B.

Notation 34 A×B = {(a, b) | a ∈ A ∧ b ∈ B}

Example 35 Tomar como el primer conjunto al conjunto de los números naturalesN y como segundo conjunto al conjunto de los números racionales positivos entre 0y 1, que se denotará por I. N×I = {(n, x) | n ∈ N, x ∈ I}.

Example 36 Tomar como primer conjunto a todas las letras del alfabeto en españoly como segundo conjunto a los números naturales del 1 al 27. El producto cartesianoson todas las parejas formadas con una letra y un número natural entre 1 y 27.

Example 37 Tomar como primero y segundo conjunto al conjunto de los númerosreales R. El producto cartesiano son todas las parejas ordenadas de números realesque normalmente denotamos como R2.

Exercise 38 Calcula los siguientes productos cartesianos:1. A = N y B = Q2. A = N y B = N3. A = Z y B = Z4. A = {a, b, c, ..., z} y B = {1, 2, ..., 30}5. A = {x | x es mexicano en el 2020 } y B = {x ∈ Q+|x es el peso en kilogramosde una persona }

Page 12: Algebra superior i   reyes

8 CAPÍTULO 2. CONJUNTOS Y FUNCIONES

Page 13: Algebra superior i   reyes

Capítulo 3

Los números naturales

Los números naturales se utilizan para contar. Hay dos formas de abordarlos, através de los axiomas de Peano o a través de los axiomas para las propiedades de lasoperaciones. En este curso se van a abordar de ambas formas porque para ambashay una aplicación importante. Con los axiomas de Peano se entiende el Principiode Inducción y la aplicación en las demostraciones de fórmulas que son válidas paralos números naturales. Las propiedades de las operaciones entre números naturalesnos ayudará a entender el concepto de estructura algebraica que se abordará en elsegundo curso de álgebra.Estrictamente los números naturales no incluyen al 0.En estas notas lo vamos a

incluir por algunas razones técnicas.

3.1. Axiomas de Peano

1. 0 ∈ N2. Existe una función, llamada sucesor, ϕ : N→ N tal que

ϕ(n) = n+ 1

la función es inyectiva e Imϕ = N− {0}3. Si S ⊂ N es tal que satisface las siguientes condiciones

a) 0 ∈ S

b) n ∈ S =⇒ ϕ(n) ∈ Sentonces S = N.

Este último axioma se llama el Principio de Inducción y se aplica para demostrarque una afirmación es verdadera para todos los números naturales.

3.2. Propiedades de las operaciones entre natu-rales

Para los números naturales N hay dos operaciones, suma + y producto ×.Laspropiedades son las siguientes:

1. El conjunto de los números naturales es cerrado bajo la operación suma,esdecir si ∀a ∈ N,∀b ∈ N entonces a+ b ∈ N

9

Page 14: Algebra superior i   reyes

10 CAPÍTULO 3. LOS NÚMEROS NATURALES

2. La suma es asociativa, ∀a ∈ N,∀b ∈ N,∀c ∈ N se cumple que a + (b+ c) =(a+ b) + c.

3. Existe un número llamado cero, 0 tal que ∀a ∈ N, a+ 0 = a

4. La suma es conmutativa, es decir ∀a ∈ N,∀b ∈ N se cumple que a+ b = b+ a.

5. El conjunto de los números naturales es cerrado bajo la operación producto,es decir si ∀a ∈ N,∀b ∈ N entonces a× b ∈ N.

6. El producto es asociativo, ∀a ∈ N,∀b ∈ N,∀c ∈ N se cumple que a× (b× c) =(a× b)× c.

7. Existe un número llamado uno,1 tal que ∀a ∈ N, a× 1 = a.

8. El producto es conmutativo, es decir ∀a ∈ N,∀b ∈ N se cumple que a×b = b×a.9. La suma distribuye al producto, es decir ∀a ∈ N,∀b ∈ N,∀c ∈ N, a× (b+ c) =

a× b+ a× c.

Se van a demostrar algunas de las propiedades que ya se conocen para losnúmeros naturales. Esto tiene como propósito ejercitar la lógica.

Proposition 39 El elemento 0 es único.

Proof. Supongamos que existe z ∈ N tal que ∀a ∈ N, a+ z = a.Como 0 ∈ N,

0 + z = 00 = 0 + z Por la propiedad reflexiva de la igualdadz + 0 = z por el axioma 30 + z = z por el ax. 4 y la transitividad de la igualdad0 = z por transitividad entre renglón 2 y 4.

Exercise 40 Demuestren que el 1 es único.

Exercise 41 Justifica cada uno de los siguientes pasos en la demostración de laproposición a0 = 0.

0 + 0 = 0

a (0 + 0) = a0

a(0 + 0) = a0 + a0

a0 + a0 = a0

a0 = 0 + a0

a0 + a0 = 0 + a0

a0 = 0

3.3. Demostraciones por inducción

Se va a aplicar el Principio de Inducción para demostrar que algunas fórmulasson verdaderas para todos los números naturales.

Page 15: Algebra superior i   reyes

3.3. DEMOSTRACIONES POR INDUCCIÓN 11

Proposition 42 La fórmula

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

2

es verdadera para todos los números naturales.

Proof. Para aplicar el principio de inducción y demostrar que la fórmula es ver-dadera para todos los naturales se va a construir el conjunto S = {k ∈ N |la fórmula es verdadera} .Para aplicar el Principio de Inducción se tiene que probar que S satisface las doscondiciones. Al satisfacer S ambas condiciones se concluye que S = N.En primer lugar 0 ∈ S porque al sustituir 0 en la fórmula se obtiene la identidad0 = 0. Para avanzar mas se sustituye 1 en la fórmula y en este caso el lado izquierdotiene valor 1 y el derecho

1 (2)

2= 1

por lo tanto se tiene una identidad. De estas dos conclusiones se obtiene que 0, 1 ∈ S.Ahora se probará que si n ∈ S entonces n+ 1 ∈ S. Como n ∈ S esto implica que lafórmula

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

2

es verdadera. Se va a mostrar que n+ 1 ∈ S, es decir se va a probar que

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

2

pero al observar el lado izquierdo de esta expresión se pueden sustituir los n primerossumandos por la fórmula para nsumandos

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

2+ (n+ 1)

Al efectuar la suma de quebrados en el lado izquierdo de esta igualdad se tiene que

n (n+ 1)

2+ (n+ 1) =

n(n+ 1) + 2(n+ 1)

2

=n2 + 3n+ 2

2

=(n+ 1) (n+ 2)

2

Por lo tanto

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

2

Proposition 43 La fórmula

12 + 22 + 32 + . . .+ n2 =n (n+ 1) (2n+ 1)

6

es verdadera para todos los números naturales.

Proof. En este caso se define S = {k ∈ N |la fórmula es verdadera} .Se probará que 1 ∈ S,se sustituye n = 1 en la fórmula y se obtiene la identidad

12 =1(2)(3)

6

Page 16: Algebra superior i   reyes

12 CAPÍTULO 3. LOS NÚMEROS NATURALES

por lo tanto 1 ∈ S.Falta probar que si n ∈ S entonces (n + 1) ∈ S.Supongamos que n ∈ S eso

significa que la fórmula

12 + 22 + 32 + . . .+ n2 =n (n+ 1) (2n+ 1)

6

es verdadera para n. Para demostrar que n+ 1 ∈ S hay que probar que

12 + 22 + 32 + . . .+ n2 + (n+ 1)2 =(n+ 1) (n+ 2) (2(n+ 1) + 1)

6

Al observar el lado izquierdo de la igualdad se ve que la suma de los primeros ntérminos se pueden sustituir por la suma de los primeros n términos

12 + 22 + 32 + . . .+ n2 + (n+ 1)2 =n (n+ 1) (2n+ 1)

6+ (n+ 1)2

Efectuando la suma de quebradosn (n+ 1) (2n+ 1)+6 (n+ 1)2 = 2n3+9n2+13n+6

=n (n+ 1) (2n+ 1) + 6 (n+ 1)2

6

=(n+ 1)[n(2n+ 1) + 6n+ 6]

6

=(n+ 1)(2n2 + 7n+ 6)

6

=(n+ 1)(n+ 2)(2n+ 3)

6

por lo tanto

12 + 22 + 32 + . . .+ n2 + (n+ 1)2 =(n+ 1) (n+ 2) (2(n+ 1) + 1)

6

Como se cumplen ambas condiciones del Principio de Inducción esto implica queS = N.Por lo tanto la fórmula es verdadera para todo número natural.

Proposition 44 La fórmula

1 + 3 + . . .+ (2i− 1) + . . .+ (2n− 1) = n2.

es verdadera para todos los números naturales.

Proof. En este caso se define S = {k ∈ N |la fórmula es verdadera} .Se probará que 1 ∈ S,se sustituye n = 1 en la fórmula y se obtiene la identidad

1 = 12

por lo tanto 1 ∈ S.Falta probar que si n ∈ S entonces (n + 1) ∈ S.Supongamos que n ∈ S eso

significa que la fórmula

1 + 3 + . . .+ (2i− 1) + . . .+ (2n− 1) = n2

es verdadera para n. Para demostrar que n+ 1 ∈ S hay que probar que

1 + 3 + . . .+ (2i− 1) + . . .+ (2n− 1) + (2n+ 1) = (n+ 1)2

Page 17: Algebra superior i   reyes

3.3. DEMOSTRACIONES POR INDUCCIÓN 13

Al observar el lado izquierdo de la igualdad se ve que la suma de los primeros ntérminos se pueden sustituir por la suma de los primeros n términos

1 + 3 + . . .+ (2i− 1) + . . .+ (2n− 1) + (2n+ 1) = n2 + (2n+ 1)

Efectuando la suma

1 + 3 + . . .+ (2i− 1) + . . .+ (2n− 1) + (2n+ 1) = (n+ 1)2

Como se cumplen ambas condiciones del Principio de Inducción esto implica queS = N.Por lo tanto la fórmula es verdadera para todo número natural.Hay una forma alternativa para el principio de inducción que es útil para probar

que una fórmula o desigualdad se cumple a partir de cierto valor n > 1.

Theorem 45 Sea S ⊂ N. Sean n0, n1 ∈ N tales que n0 ≤ n1. Si S satisface lascondicionesa) n0, . . . , n1 ∈ S yb) n0, . . . , k ∈ S implica que k + 1 ∈ Sentonces n ∈ S si n ≥ n0.

Proof. Esta demostración se hace considerando S0 = {n ∈ N | n − n0 ∈ S}yaplicando el principio de inducción a S0.

Proposition 46 La desigualdad

n− 2 < n2 − n

12

es verdadera para todo número natural n > 10.

Proof. Sea S = {k ∈ N |k > 10 y tal que la desigualdad es verdadera} .El primer natural mayor que 10 es 11.Se probará que 11 ∈ S. Primero

n− 2 = 9

ahora

(11)2 − 1112

=121− 1112

=110

12≈ 9,1667 . . .

por lo tanto se cumple para n = 11.Supongamos que n ∈ S, i.e. la proposición es verdadera para n ≥ 11. Es decir

n− 2 < n2 − n

12

Se va a demostrar para (n+1) ∈ S.Para demostrar que la desigualdad es verdaderapara n+ 1 hay que demostrar que

(n+ 1)− 2 < (n+ 1)2 − (n+ 1)12

n− 1 < n2 + n

12

Page 18: Algebra superior i   reyes

14 CAPÍTULO 3. LOS NÚMEROS NATURALES

Para hacer la demostración escribir (n+ 1)− 2 = (n− 2) + 1y utilizar que n ∈ S

n− 1 = (n− 2) + 1 < n2 − n

12+ 1

pero 12− n ≤ 1,por lo tanto

n2 − n

12+ 1 =

n2 − n+ 12

12<

n2 + n

12

Por transitividad de <se tiene que

n− 1 < n2 + n

12

De donde (n+ 1) ∈ S.Por tanto S = N.

Exercise 47 Demostrar por inducción las siguientes proposiciones:

Proposition 48 La fórmula

1

1 · 2 +1

2 · 3 + · · ·+1

n (n+ 1)=

n

n+ 1

es verdadera para todo número natural.

Proposition 49 La fórmula

13 + 23 + · · ·+ n3 =n2 (n+ 1)2

4

es verdadera para todo número natural.

Proposition 50 La fórmula

12 + 32 + . . .+ (2n− 1)2 = n (2n− 1) (2n+ 1)3

es verdadera para todo número natural.

Proposition 51 La fórmula

1 · 3 + 2 · 4 + . . .+ n(n+ 2) =n (n+ 1) (2n+ 7)

6

es verdadera para todo número natural.

Proposition 52 La desigualdad2n < n!

para n > 3.es verdadera.

Proposition 53 La desigualdadn2 < 2n

para n > 4.es verdadera.

Page 19: Algebra superior i   reyes

3.4. DEFINICIONES INDUCTIVAS 15

3.4. Definiciones inductivas

Cuando se tiene una definición para cualquier número natural se utiliza la defini-ción por inducción o la definición recurrente.

Example 54 Por ejemplo se quiere definir xn donde x ∈ R y n ∈ N.

Solution 55 Se definen x1 = x, x2 = x · x, . . . , xn = xn−1 · x. Esto significa quepara calcular xn hay que calcular primero xn−1 y el resultado multiplicarlo por x.

Example 56 Se quiere definir Rn.

Solution 57 Se define R1 = R, R2 = R×R, . . . , Rn+1 = Rn ×R.

Example 58 Se quiere definir n!.

Solution 59 Se define 1! = 1, 2! = 1 · 2 = 2, . . . , n! = (n− 1)! · n.Para calcular 10!se tiene que conocer 9! y el resultado multiplicarlo por 10.

Example 60 Se quiere definir la sucesión de números an, conocida como la seriede Fibonacci,

1, 1, 2, 3, 5, . . .

Solution 61 Se define a0 = 1, a1 = 1, . . . , an+1 = an+ an−1. Para calcular a6 hayque conocer a5 y a4.Se calculan

a2 = a0 + a1 = 1 + 1 = 2

a3 = a2 + a1 = 2 + 1 = 3

a4 = a3 + a2 = 3 + 2 = 5

a5 = a4 + a3 = 5 + 3 = 8

a6 = a5 + a4 = 5 + 8 = 13

Exercise 62 Definir inductivamente A1 ∪A2 ∪ · · · ∪An.

Exercise 63 Definir la asociatividad de la suma inductivamente.

3.5. Cardinalidad

Contar es comparar dos conjuntos. Los conjuntos pueden tener un número finitoo un número infinito de elementos.La noción básica de contar el número de elementos de un conjunto A consiste

en establecer una función biyectiva entre un subconjunto de los números naturalesy el conjunto A.Algebraicamente definimos esta forma de contar con encontrar f :A→ N.de tal forma que f sea inyectiva

Remark 64 Normalmente, cuando contamos, se toma como el primer valor de lafunción al 1 y se continúa sucesivamente con el sucesor.

El conjunto de los números naturales tiene un número infinito de elementos, alnúmero de naturales se le denomina ℵ0(alef cero) y es la cardinalidad de los númerosnaturales.Cuando existe una biyección g entre la Im f $ N y el conjunto {1, 2, . . . , n}

se dice que el conjunto es finito y al número de elementos de Im f se le llamacardinalidad de A.

Page 20: Algebra superior i   reyes

16 CAPÍTULO 3. LOS NÚMEROS NATURALES

Notation 65 Para un conjunto finito A la cardinalidad de A se denota por |A| oN (A) o #A o m(A).

Hay conjuntos como los números reales que tienen también un número infinitode elementos, pero que no se pueden contar con los números naturales. Es decirno existe forma de comparar al conjunto de los números naturales con el conjuntode los números reales. Dicho de otra forma no hay una función biyectiva entre losnúmeros naturales y los números reales.

Definition 66 Dos conjuntos tienen la misma cardinalidad si existe una biyecciónentre los dos conjuntos.

Theorem 67 Los números naturales N y los enteros Z tienen la misma cardinali-dad.

Proof. Para demostrar esto basta construir una biyección entre los naturales ylos enteros. Se define f : Z→ N como

f(z) =

½2z, si z > 0

2 |z|+ 1, si z ≤ 0

Esta función es una biyección porque si f(z1) = f(z2), hay cuatro posibilidades:(i) Si z1 > 0 y z2 > 0, 2z1 = 2z2 por lo tanto z1 = z2.(ii) Si z1es negativo y z2 < 0 f(z1) = −2z1 + 1 = −2z2 + 1, z1 = z2.

(iii) Si z1 > 0 y z2 < 0 entonces f(z1) = 2z1 y f(z2) = −2z2+1,pero uno es pary el otro impar por lo tanto no pueden ser iguales. Esto contradice la hipótesis.(iv) El último caso se descarta de manera semejante.Además para cualquier natural n existe z tal que f(z) = n,porque si n es par

existe el entero positivo q tal que 2q = n,si n es impar existe un entero positivo ptal que n = 2p+ 1, −p es negativo y f(−p) = n.Por lo tanto f es suprayectiva.También se puede demostrar que hay una biyección entre los números racionales

y los naturales.Basta arreglar los racionales como cociente de dos enteros en unarreglo de renglones y columnas poniendo el numerador el número de la columnay en el denominador el del renglón. Se cuentan recorriendo los elementos en diago-nal. Esta demostración no se hará formalmente pero se puede enunciar el siguienteteorema.

Theorem 68 Los números racionales Q tienen la misma cardinalidad que los nat-urales N.

Remark 69 Se observa que N $ Z, además Z = N ∪ N−. De aquí se podría deducirque la cardinalidad de Z es el doble que la cardinalidad de N pero vemos que es lamisma. Se concluye que la aritmética para los números finitos no se aplica para losinfinitos. Además aquella afirmación de que el todo es mayor que sus partes tampocose aplica en este caso.

La forma como podemos intuir que los números reales no tiene la misma car-dinalidad que los naturales es percatándonos que el intervalo [0, 1) tiene la mismacardinalidad que toda la recta real. Eso se visualiza fácilmente en la siguiente figu-ra, si se considera que la circunferencia es el intervalo [0, 1) y dejando fijo,el puntode intersección del eje Y y la circunferencia se trazan rectas. A cada punto de lacircunferencia le corresponde un punto en la recta real y viceversa:

Page 21: Algebra superior i   reyes

3.6. RELACIÓN DE ORDEN 17

A la cardinalidad de los números reales se le llama ℵ1(alef uno).

Exercise 70 Calcula la cardinalidad de los siguientes conjuntos:a) A = {6, 7, 8, 9}b) A = {a, b, . . . , w, x, y, z} , B = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0} , A×B. Nota: considerenun alfabeto de 26 letras.c) Z× Z

Exercise 71 Sea A = {1, 2, 3, 4} . Considerar al conjunto F de todas las funcionesinyectivas f : A→ A. Calcular la cardinalidad de F.

Exercise 72 Sea U = {a, b, . . . , w, x, y, z} y A = {a, b, c, d, e} , B = {c, d, e, f, g, h, i} , C ={x, y, z} Calcular la cardinalidad de los siguientes conjuntos:a) Ab) Bc) Cd) A ∪Be) A ∪ Cf) A ∩Bg) Ac

h) Ac ∩Bi) Bc ∩Ai) Comparando estos resultados ¿qué igualdades se pueden formar?

3.6. Relación de orden

Definition 73 Si m y n ∈ N se dice que m < n si existe s ∈ N tal que m+ s = n.

3.6.1. Propiedades del orden.

Sean k,m y n ∈ N.Entonces

1. Se cumple una de las siguientes tres cosas: m < n,m = n ó m > n. Estapropiedad se llama de tricotomía.

2. Si k < m y m < n entonces k < n.Transitividad.

3. Si k < m entonces k + n < m+ n.

4. Si k < m entonces k · n < m · n.

Page 22: Algebra superior i   reyes

18 CAPÍTULO 3. LOS NÚMEROS NATURALES

Cuando un conjunto como el conjunto de los números naturales satisface latricotomía se dice que es totalmente ordenado.

Exercise 74 Demostrar que si k + n < m+ n entonces k < m.

Exercise 75 Demostrar que kn < mn implica k < m.

3.7. Principio del buen orden

Para los números naturales se cumple el principio del buen orden. Este principioimplica al principio de inducción.El principio del buen orden dice que todo subconjunto S 6= ∅ de los números

naturales tiene un elemento m tal que m ≤ s ∀s ∈ S.Dicho de otra manera S ⊂ N,S 6= ∅contiene un elemento mínimo.Los números enteros no son bien ordenados porque el subconjunto {x ∈ Z |x < 0}

es diferente del vacío y no contiene un mínimo.

Proposition 76 El principio del buen orden se cumple para los números naturales.

Proof. PRIMERA DEMOSTRACIÓN(Sin utilizar explícitamente el Principiode Inducción)Ahora se demostrará el principio del buen orden. Para ello consideremos un

subconjunto S 6= ∅ de los números naturales.Si S es finito,supongamos que

S = {n1, n2, . . . , nk}

Por la propiedad de tricotomía, se puede escoger un elemento ni tal que ni ≤ nj∀j = 1, . . . , k. Por lo tanto S tiene un mínimo.Si S es infinito como es diferente del conjunto vacío entonces contiene un ele-

mento a. Sea S0 = {n ∈ S | n ≤ a} . El conjunto S0 contiene a lo más a los naturales1, 2, . . . , a. pero no necesariamente a todos. Como S0 es finito y a ∈ S0 entonces S0contiene un mínimo m. El mínimo m de S0 es elemento de S y m ≤ a. Ahora seprobará que m es un mínimo de S. Para ello considerar una n ∈ S. Por la definiciónde S0 hay dos posibilidades n ∈ S0 o n /∈ S0. Si n ∈ S0 entonces m ≤ n porque mes el mínimo de S0. Si n /∈ S0 entonces n > a,pero a ≥ m. Por lo tanto n > m. Encualquiera de los dos casos m es el mínimo de S.Proof. SEGUNDA DEMOSTRACIÓN(Utilizando el Principio de Inducción)Consideremos un subconjunto S 6= ∅ del conjunto N. Supongamos que S no tiene

mínimo. Sea S0 = {n ∈ N |n < a∀a ∈ S} . Primero que nada S0es un subconjunto deN y S0 ⊂ Sc porque si n ∈ S0, n < a para a ∈ S. Además S0satisface las condicionesdel principio de inducción:(i) 1 ∈ S0 porque 1 /∈ S. Si 1 ∈ S entonces S tendría un mínimo.(ii) Supongamos que n ∈ S0. Se va a demostrar que n + 1 ∈ S0. La demostraciónse hará por reducción al absurdo. Si n + 1 /∈ S0 entonces n + 1 ≥ a.para algunaa ∈ S De esta afirmación y de que n < a implica que n + 1 ≤ a se concluye quen+ 1 = a ∈ S.Por tanto n+1 es un mínimo de S. Lo que contradice que Sno tieneun mínimo. Por lo tanto n+ 1 ∈ S0.Por el principio de inducción esto significa que S0 = N. Por lo tanto, S = ∅. Esta

afirmación es una contradicción pues se había supuesto que S es diferente del vacío.

Proposition 77 El principio del buen orden implica el principio de inducción.

Page 23: Algebra superior i   reyes

3.8. FUNCIONES Y RELACIONES 19

Proof. Primero se demostrará que el principio del buen orden implica el prin-cipio de inducción. Para ello consideremos un conjunto S ⊂ N, S 6= ∅ tal que 1 ∈ Sy si n ∈ S entonces n+ 1 ∈ S. Sea S0 = Sc. Supongamos que S0 6= ∅. Como S0 ⊂ Nentonces S contiene un mínimo. Sea m el mínimo de S0. Esto implica que m−1 ∈ Sporque m− 1 < m. Pero por hipótesis si n = m− 1 ∈ S entonces n+1 = m ∈ S loque contradice que m ∈ S0. Por lo tanto S0 = ∅.De donde S = N.Remark 78 Un conjunto que satisface el principio del buen orden se llama bi-en ordenado. El conjunto de los números naturales es bien ordenado y totalmenteordenado.

Exercise 79 Encuentra subconjuntos de Q y R para los que no se cumpla el prin-cipio del buen orden.

3.8. Funciones y relaciones

3.8.1. Dominio y contradominio

Definition 80 Una relación es un subconjunto R cualquiera de un producto carte-siano A×B, .R ⊂ A×B.

Definition 81 Una función es una relación F de un producto cartesiano A × Btal que si (a1, b1) , (a2, b2) ∈ F entonces b1 6= b2 =⇒ a1 6= a2. Esto es equivalente adecir a1 = a2 =⇒ b1 = b2.

Example 82 Llamar I al intervalo [0, 1]. El subconjunto F de N×I dado por lasparejas

µn,1

n

¶es una función.

Exercise 83 Define una función de los enteros en los naturales tal que al 0 leasocie el 1,al 1 el 2,al −1 el 3,al 2 el 4, · · · . De ser posible escribe las parejas.

Exercise 84 Define la función dada por la regla f(x) =1

xcon x ∈ R.

Exercise 85 Dado el conjunto F = {(x, y) | x ∈ R y y ∈ R, sea tal que (x− 2)2 +y2 = 36},determina el producto cartesiano al que pertenece y determina si es o nofunción. Justifica tu respuesta.

Definition 86 Al conjunto A se le llama el dominio de la función F y al conjuntoB se le llama el codominio o contradominio de la función.

Notation 87 A = Dom (F ), B = Codom(F ).

Exercise 88 Determina, si es posible, el dominio de las funciones en los tres ejer-cicios anteriores.

Definition 89 Al subconjunto de B para el cual existe un elemento a ∈ A tal que(a, b) ∈ F se le llama la imagen de F.

Notation 90 ImF = {b ∈ B | ∃a ∈ A tal que (a, b) ∈ F}Exercise 91 Determina, si es posible, la imagen de los ejercicios que correspondena la definición de función.

Definition 92 Se define la gráfica de la función F como el subconjunto de A×Btal que b ∈ ImF.

Page 24: Algebra superior i   reyes

20 CAPÍTULO 3. LOS NÚMEROS NATURALES

Notation 93 Graf(F ) = {(a, b) | a ∈ A y b ∈ ImF}

Remark 94 Utilizando la notación usual de funciones la imagen de una funciónson los elementos de b ∈ B tales que existe a ∈ A tal que f (a) = b.

Remark 95 La gráfica de la función es el conjunto de puntos (a, f (a)) ∈ A×B.

Remark 96 Dos funciones F y G son iguales si tienen el mismo dominio, el mismocodominio y F = G.

Exercise 97 Determina, si es posible, la gráfica de las funciones del inciso dedefinición.

Exercise 98 Dadas F ⊂ R×R y G ⊂ R×R+ dadas por las parejas (x, x2) ¿soniguales? Justifica tu respuesta.

Exercise 99 Dadas las funciones F ⊂ (R− {2}) × R y G ⊂ R×R la primera

dada por las parejasµx,

x2 − 4x− 2

¶y la segunda por (x, x+ 2) justifica porque son

funciones diferentes.

3.9. Clasificación de funciones

Las funciones se clasifican:

Por su regla de asociación en inyectivas o no inyectivas.

Por la comparación entre su imagen y codominio como en suprayectivas y nosuprayectivas.

Definition 100 Una función F es inyectiva si cada vez que (a1, b1) , (a2, b2) ∈ F yb2 = b1 entonces a1 = a2.

Remark 101 A las funciones inyectivas también se les llama uno a uno y biunívo-cas.

Remark 102 Otra forma de expresar que una función es inyectiva es decir que sia1 6= a2 entonces b1 6= b2.

Remark 103 En la notación usual del cálculo (a1, b1) ∈ F si f (a1) = b1.

Definition 104 Una función F ⊂ A×B es suprayectiva si ImF = B.

Remark 105 A las funciones suprayectivas se les llama sobres.

Example 106 Una función no inyectiva y no suprayectiva es F ⊂ R×R definidapor las parejas

¡x, x2

¢.

Example 107 Una función inyectiva y no suprayectiva es F ⊂ R+×R definida porlas parejas (x,

√x).

Page 25: Algebra superior i   reyes

3.10. COMPOSICIÓN DE FUNCIONES 21

Example 108 Una función no inyectiva y suprayectiva es F ⊂ R×R definida porlas parejas (x, x3 − 2x2 − 5x+ 6). Esta función tiene como gráfica la siguiente

52.50-2.5-5

50

0

-50

-100

x

y

x

y

Example 109 Una función inyectiva y suprayectiva es F ⊂ R×R definida por lasparejas (x, 2x).

Exercise 110 Da un ejemplo de cada una de las cuatro posibilidades de funciones.En cada caso justifica tus respuestas y da de forma explicita el dominio, codominio,calcula la imagen y la gráfica.

3.10. Composición de funcionesDefinition 111 Dadas dos funciones F ⊂ A×B y G ⊂ B×C se define la funcióncomposición como la función en A × C formada por el conjunto de puntos (a, c)tales que exista b ∈ B tal que (a, b) ∈ F y (b, c) ∈ G.

Notation 112 G ◦ F = {(a, c) | ∃b ∈ B tal que (a, b) ∈ F y (b, c) ∈ G}.Notation 113 La función 1A ⊂ A×A se define como 1A(a) = a ∀a ∈ A y se llamala función identidad de A.

Example 114 Sean F ⊂ R×R y G ⊂ R×R+ dadas por las parejas (x, 2x+ 5) y¡x, x4

¢.La composición es un subconjunto de R×R4 tales que (x, (2x+ 5)4)

Example 115 Sean F ⊂ R×R y G ⊂ R+ × R− dadas por (x, x2), (x,−√x)respectivamente. La función G◦F ⊂ R×R− esta dada por las parejas

³x,−p|x|´ .

Exercise 116 Calcula el dominio, codominio, parejas, imagen y gráfica de cadauna de las siguientes composiciones:1. Sean F, G ⊂ Z× Z definidas por las parejas (x, x−1) ∈ F y (x, 3x) ∈ G. CalculaG ◦ F.2. Para las mismas funciones del primer inciso calcula F ◦G.3. Si H ⊂ Z× Z esta definida por

(x, 0) si x es par

(x, 1) si x es impar

Calcula H ◦G y G ◦H.

Theorem 117 Sean F ⊂ A×B y G ⊂ B × C dos funciones1. Si F y G son inyectivas entonces G ◦ F es inyectiva.2. Si F y G son suprayectivas entonces G ◦ F es suprayectiva.

Page 26: Algebra superior i   reyes

22 CAPÍTULO 3. LOS NÚMEROS NATURALES

Proof. Se demostrará la primera parte. Para ello supongamos que (g ◦f) (a1) =(g ◦ f) (a2) .Esto implica que

g(f(a1)) = g(f(a2))

Como Ges inyectiva entonces

f(a1) = f(a2)

Como F es inyectiva esto implica que a1 = a2.Por lo tanto la composición es inyec-tiva.Para demostrar la segunda parte se demostrará que C = Im(G ◦ F ). Como

Im(G ◦ F ) ⊂ C basta demostrar que C ⊂ Im(G ◦ F ). Sea c ∈ C. Como G es sobreentonces existe b ∈ B tal que g(b) = c (otra forma de expresar que (b, c) ∈ G ).Como F es sobre, para b ∈ B existe a ∈ A tal que f(a) = b. Por lo tanto

c = g(f(a)).De donde c ∈ Im(G ◦ F ).

Theorem 118 La composición de funciones es asociativa.

Proof. Supongamos que se tienen tres funciones f : A → B, g : B → C yh : C → D tales que se pueden hacer las composiciones g◦f, h◦g y las composicionesh◦(g◦f) y (h ◦ g)◦f. El que se puedan hacer las primeras dos composiciones significaque Im f = B, Im g = C, el que se puedan hacer las otras dos composiciones significaque Im(g ◦ f) = Dom(h) = C y que Im f = Dom (h ◦ g) = A.

Ahora bien el Dom(h ◦ (g ◦ f)) = A y el Dom( (h ◦ g) ◦ f) = A. El Codom((h ◦ g) ◦ f) = Codom(h ◦ (g ◦ f)) = D.

Además para toda a ∈ A se tiene que

(h ◦ (g ◦ f))(a) = (h(g ◦ f))(a)= h(g(f(a)))

Por otro lado

((h ◦ g) ◦ f)(a) = (h ◦ g)(f(a))= h(g(f(a)))

Por lo tanto, por transitividad

(h ◦ (g ◦ f))(a) = ((h ◦ g) ◦ f)(a) ∀a ∈ A

De estas tres afirmaciones se concluye la igualdad de funciones.

Exercise 119 Para las funciones del ejercicio anterior calculen h ◦ g ◦ f. ¿Porquése escribe sin paréntesis?

Exercise 120 Dadas f : R+ → R por f(x) = ln(x) y g : R→ R+, por g(x) =exentonces calcular el dominio, contradominio y la regla de g ◦f y f ◦ g. Demostrarque ambas composiciones son biyectivas.

Exercise 121 Dada f : R − {0} → R− {0} por f(x) =1

x,calcular el dominio,

codominio y regla de f ◦ f. Demostrar que la composición es biyectiva.

Page 27: Algebra superior i   reyes

3.11. FUNCIONES INVERSAS 23

3.11. Funciones inversasDefinition 122 Dada una función F ⊂ A×B se define la inversa de F a la funciónG ⊂ B ×A,si existe tal que G ◦ F = 1A y F ◦G = 1B.Notation 123 G se denota por F−1.Se dice que F es invertible.

Example 124 La función inversa de f : Z→2Z definida por f (a) = 2a es f−1(b) =b

2donde 2Z = {2a | a ∈ Z}.

Example 125 La función inversa de f : [0,π

2]→ [0, 1] definida por f(x) = sen(x)

es f−1(y) = arcsen(y).

Exercise 126 Encontrar, si es posible la función inversa de las siguientes fun-ciones, en cada caso justificar la respuesta:1. f : R→ R, f(x) = x3

2. f : R+ → R−, f(x) = −√x3. f : R→ R, f(x) = x6.4. f : {1, 2, 3, 4}→ {1, 2, 3, 4} dada por la tabla

a f(a)1 22 13 44 3

Theorem 127 Si una función F ⊂ A×B es invertible entonces la inversa es única.

Proof. Suponer que existe h : B → A tal que h ◦ f = 1A y f ◦ h = 1B.Parademostrar que h y f−1 son la misma función primero se observa que las dos funcionestienen como dominio a B y como contradominio a A.Finalmente se calcula h(b).

h(b) = (1A ◦ h)(b)pero 1A = f−1 ◦ f al sustituir

h(b) = ((f−1 ◦ f) ◦ h)(b)por asociatividad

h(b) = (f−1 ◦ (f ◦ h))(b)Como (f ◦ h)(b) = 1B(b) = b por hipótesis entonces

h(b) = f−1(b) ∀b ∈ B.

De donde se concluye que las funciones h y f−1son iguales. Por lo tanto la funcióninversa de f es única.

Theorem 128 Una función F es invertible si y sólo si es inyectiva y suprayectiva.

Proof. Primero se demostrará que si es invertible entonces es inyectiva y suprayec-tiva.Supongamos que f : A→ B es invertible. Entonces existe f−1 : B → A.tal que

f ◦ f−1 = 1B y f−1 ◦ f = 1A.Para demostrar que f es inyectiva supongamos que f (a1) = f (a2) . Como existe

f−1,que es función, entonces f−1(f(a1)) = f−1(f(a2)).Por la definición de f−1 estoimplica que a1 = a2. Por lo tanto fes inyectiva.

Page 28: Algebra superior i   reyes

24 CAPÍTULO 3. LOS NÚMEROS NATURALES

Para demostrar que f es suprayectiva consideremos b ∈ B. Como f−1 es unafunción entonces calculamos f−1 (b) = a. Como f

¡f−1 (b)

¢= f(a) = b entonces ya

se encontró una a ∈ A tal que f(a) = b para cualquier b ∈ B. Por lo tanto f essuprayectiva.Ahora se demostrará que si f es inyectiva y suprayectiva entonces es invertible.Sea g : B → A la función definida como sigue:

g(b) = a

si a ∈ A es tal que f(a) = b. Esa a ∈ A existe para toda b ∈ B porque f essuprayectiva.Además g es una función porque si b1 = b2entonces existen a1y a2 ∈ Atales que f(a1) = b1y f (a2) = b2. La hipótesis se escribe como

f(a1) = f(a2)

como f es inyectiva esto implica que

a1 = a2

que implica queg (b1) = g (b2)

por lo tanto g es una función tal que g ◦ f = 1B y f ◦ g = 1A.Como se demostroantes que la inversa es única entonces g = f−1.

Theorem 129 Sean A y B dos conjuntos finitos con el mismo número de elementosy F una función en A×B. Entonces las siguientes afirmaciones son equivalentes(a) F es inyectiva.(b) F es suprayectiva.(c) F es invertible.

Proof. Basta demostrar que (a)⇔(b) porque (c)⇔(a) y (b).Supongamos que F es suprayectiva pero no es inyectiva. Como no es inyectiva

esto implica que existen a1y a2, a1 6= a2 tales que f(a1) = f(a2). Esto implica queel conjunto A tiene mas elementos que Im f. Pero Im f = B . Esto contradice lahipótesis de que los conjuntos A y B tienen el mismo número de elementos. Por lotanto f es inyectiva.Supongamos que f es inyectiva pero no es suprayectiva. Como no es suprayectiva

entonces Im f à B. Entonces existe b ∈ B tal que b /∈ Im f.Por ser f inyectiva elnúmero de elementos de Im f es igual al número de elementos de A. Esta conclusióncontradice la hipótesis de que A y B tienen el mismo número de elementos. Por lotanto f es suprayectiva.

Exercise 130 Dada una función f : A→ B se define la preimagen de un subcon-junto B1 ⊂ B como el subconjunto de A tal que f(a) ∈ B1 y se denota por f−1(B1).Para la función f : R→ R, dada por (x, x2) calculen f−1([0, 4]).

Page 29: Algebra superior i   reyes

Capítulo 4

Relaciones binarias

4.1. DefiniciónDefinition 131 Una relación se llama binaria sobre el conjunto A cuando se tratade una relación R ⊂ A×A.

Example 132 Si A = R una relación binaria es la igualdad definida por el sub-conjunto R = {(x, y) | x, y ∈ R y x = y}Example 133 Si A = N una relación binaria es el menor o igual definido por elsubconjunto M = {(a, b) | a, b ∈ N y a ≤ b}Example 134 Si A = Z× Z una relación binaria entre parejas de enteros es quedos parejas (a, b) y (c, d) están en relación si

a

b=

c

d.

Example 135 Si A = N×N una relación binaria entre parejas de naturales es quedos parejas (n1,m1) y (n2,m2) están en relación si n1 −m1 = n2 −m2.

Exercise 136 Determina sobre que conjunto se define la siguiente relación binaria:{(a, b) | a, b ∈ Z y a divide a b}y describe la forma que tienen las parejas que estanen la relación.

Exercise 137 Sea A = {a, b, c, d, e}. Al conjunto de todos los subconjuntos forma-dos por los elementos de A se le llama conjunto potencia de A.y se le denota porP (A). Determina si la contención de conjuntos es una relación binaria en P (A).

4.2. Relaciones de equivalenciaDefinition 138 Una relación binaria R sobre A es de equivalencia si satisface lassiguientes propiedades:1. (a, a) ∈ R∀a ∈ A. Esta propiedad se llama reflexiva.2. Si (a, b) ∈ R entonces (b, a) ∈ R.Propiedad simétrica.3. Si (a, b) ∈ R y (b, c) ∈ R entonces (a, c) ∈ R. Propiedad transitiva.

Notation 139 También se escribe aRb si (a, b) ∈ R.

Example 140 La igualdad en los números reales es una relación de equivalencia.R = {(a, a) | a ∈ R} ⊂ R×R. Es una relación de equivalencia porque un númeroreal es igual a si mismo por lo tanto R cumple la propiedad reflexiva. También secumple la propiedad simétrica porque si a = b entonces b = a y la transitiva, sia = b y b = c entonces a = c.

25

Page 30: Algebra superior i   reyes

26 CAPÍTULO 4. RELACIONES BINARIAS

Example 141 Consideremos el conjunto A = N×N. y se define una relación Rsobre A de tal forma que (n1,m1) m (n2,m2) si y sólo si n1 +m2 = n2 +m1. Paraprobar que es una relación de equivalencia hay que demostrar que cumple con lastres condiciones.Para demostrar que (n,m) m (n,m) hay que corroborar que n +m = n +m paracualesquiera dos naturales n y m. Pero esto es cierto ya que la igualdad es reflexiva.La reflexividad se sigue inmediatamente de la reflexividad de la igualdad entre nat-urales ya que si (n1,m1) m (n2,m2) esto implica que n1 +m2 = n2 +m1.Como laigualdad entre naturales es reflexiva entonces n2 + m1 = n1 + m2. Esta igualdadsignifica que (n2,m2) m (n1,m1).La transitividad se cumple ya que si (n1,m1) m (n2,m2) y (n2,m2) m (n3,m3) estoimplica que n1+m2 = n2+m1y que n2+m3 = n3+m2 respectivamente. Al sumarambas igualdades se obtiene

(n1 +m2) + (n2 +m3) = (n2 +m1) + (n3 +m2)

Aplicando la asociatividad de la suma de naturales y la cancelación se tiene que

n1 +m3 = m1 + n3

como la suma de naturales es conmutativa entonces

n1 +m3 = n3 +m1

Por lo tanto R es una relación de equivalencia en dondeR = {((n1,m1) , (n2,m2)) ∈ A×A | n2 +m1 = n1 +m2} .Example 142 Consideremos el conjunto A = Z× Z y se define la relación Rsobre A de tal forma que (a, b) ≈ (c, d) si y sólo si ad = bc. Esta relación esde equivalencia.

Theorem 143 Una relación de equivalencia R sobre A parte en conjuntos ajenosa A.

Proof. Se va a demostrar que A = ∪Ra donde Ra = {x ∈ A | aRx} . Parademostrar la igualdad de dos conjuntos hay que demostrar las dos contenciones.La contención ∪Ra ⊂ A siempre es verdadera ya que todos los subconjuntos Ra ⊂A,por lo tanto su unión también. Para demostrar la otra contención se consideraa ∈ A. Como para toda a ∈ A se tiene que aRa entonces el conjunto Ra contiene almenos un elemento, a.Ahora se va a demostrar que Ra∩Rb = ∅ si (a, b) /∈ R o que Ra∩Rb = Ra = Rb

si (a, b) ∈ R.Supongamos que (a, b) /∈ R.y supongamos que existe x ∈ Ra∩Rb. Estoimplica que xRa y que xRb. Por reflexividad y transitividad esto implica que aRblo que contradice la hipótesis acerca de que (a, b) /∈ R. Por lo tanto Ra y Rb sonajenos si (a, b) /∈ R.

Definition 144 Al conjunto Ra = {x ∈ A | xRa} se le llama la clase de equiva-lencia del elemento a de A. Al elegir un elemento de la clase de equivalencia Ra sedice que se toma un representante de la clase.

Example 145 En el plano cartesiano R2 considere los puntos. Se define un vectorcomo el representante de la clase de equivalencia de parejas de puntos cuyas difer-encias son iguales. El representante que se elige es el vector que sale del origen ytermina en el punto.

Example 146 En el plano euclidiano se dice que dos segmentos son congruentescuando tienen la misma longitud. Esta relación es de equivalencia.

Page 31: Algebra superior i   reyes

4.2. RELACIONES DE EQUIVALENCIA 27

Exercise 147 Describir las clases de equivalencia del espacio vectorial representa-do en R2.Demostrar que un vector es un representante de una clase de equivalencia

Exercise 148 Demuestra que la semejanza de triángulos definida cuando los treslados correspondientes son proporcionales es una relación de equivalencia.

Exercise 149 Demostrar que la relación definida en el ejemplo(101) es una relaciónde equivalencia.

Exercise 150 Demostrar que la relación binaria sobre R no es una relación deequivalencia.

Page 32: Algebra superior i   reyes

28 CAPÍTULO 4. RELACIONES BINARIAS

Page 33: Algebra superior i   reyes

Capítulo 5

Matemáticas discretas

5.1. Relaciones entre conjuntos finitos

Las relaciones entre conjuntos finitos tienen una gran cantidad de aplicaciones.Por ejemplo se aplican en el diseño de bases de datos, en la optimización de tiempospara actividades complejas, en el diseño de lenguajes de computación, en encontrarcaminos cortos u óptimos, en el diseño de redes de carreteras, de ductos de agua ocualquier otro fluído y en muchas otras cosas.

El primer concepto para entender la multiplicidad de aplicaciones es el pasoentre diversas representaciones de las relaciones. La primera, que ya fue estudiadaanteriormente es la representación de una relación como un conjunto. Hay querecordar que una relación R es un subconjunto de un producto cartesiano de dosconjuntos A y B. Utilizando la notación usual R ⊂ A×B.

Recordar también que una relación se llama binaria cuando A = B. En este casoademás se agregará que N(A) <∞, i.e. A es un conjunto finito.

5.1.1. Gráfica dirigida.

Representación geométrica de una relación.

Una relación binaria sobre un conjunto finito A se puede representar gráfica-mente como un conjunto de vértices o puntos que serán los elementos de A y flechasde un elemento a ∈ A en el elemento b ∈ A si (a, b) ∈ R.

Por otro lado existen las definiciones de gráfica (grafo) y gráfica dirigida, digrá-fica(digrafo) que se desarrollo a partir de un problema planteado por Euler.

Definition 151 Una gráfica (grafo) G consiste de dos conjuntos V, los vértices dela gráfica y E las aristas de la gráfica que se representan con parejas de puntos.

Example 152 Dada la relación binaria R sobre A = {a, b, c} dondeR = {(a, b) , (b, b) , (c, b) , (c, a)} la gráfica dirigida asociada a la relación esV = A = {a, b, c} y E = {(a, b) , (b, b) , (c, b) , (c, a)}, el dibujo asociado a la gráficaes de mucha utilidad. A continuación se muestra.

29

Page 34: Algebra superior i   reyes

30 CAPÍTULO 5. MATEMÁTICAS DISCRETAS

Figura 5.1:

Example 153 Diagrama de Hasse o representación gráfica de una relación de or-den. Una relación binaria de contención de entre conjuntos se representa con unagráfica sin flechas escribiendo el conjunto menor en la parte inferior. Por ejemplopara el conjunto potencia del conjunto A = {a, b.c} se toman todos los subconjuntosde A : ∅, {a} , {b} , {c} , {a, b} , {a, c} , {b, c} , A. y se colocan en una gráfica como lasiguiente.

Hay algunas definiciones y lenguaje que se utiliza en teoría de gráficas que nosvan a se útiles para resolver problemas de optimización, la aplicación del algoritmo

Page 35: Algebra superior i   reyes

5.1. RELACIONES ENTRE CONJUNTOS FINITOS 31

de Dijkstra. A continuación se presentan.

Definition 154 Camino o trayectoria Un camino es una sucesión de vértices yaristas que van de un vértice llamado inicial a un vértice llamado final.

Example 155 En el ejemplo de la gráfica un camino es a, (a, b), b, (b, b)b. Un caminose puede denotar por sus vértices solamente. En este ejemplo abb.

Definition 156 Ciclo Un ciclo es un camino que inicia y termina en el mismovértice. También se llama camino cerrado.

Definition 157 Lazo Un lazo es un ciclo que contiene una sola arista.

Definition 158 Camino simple Un camino es simple cuando no pasa dos veces porel mismo vértice.

En teoría de gráficas en ocasiones la dirección de una arista no es importante. Enese caso se utiliza una gráfica. El ejemplo clásico es el de los puentes de Könisbergplanteado por Euler. Este problema consiste en encontrar una manera de caminarentre dos islas sin pasar dos veces por el mismo punto y recorrer todos los puentesen la ciudad de Königsberg.

La gráfica para el problema es la siguiente:

Page 36: Algebra superior i   reyes

32 CAPÍTULO 5. MATEMÁTICAS DISCRETAS

Otra representación gráfica de una relación

Una relación también se puede representar por un conjunto de puntos en unplano cartesiano A×B donde el conjunto finito A se coloca horizontal y el conjuntoB se coloca vertical.

Example 159 Dada la relación binaria R sobre A = {a, b, c} donde R = {(a, b) , (b, b) , (c, b) , (c, a)}la gráfica cartesiana es:

Exercise 160 Dadas las siguientes relaciones trazar las gráficas dirigida y carte-siana.a) A = {a, b, c, d, e} y B = {1, 2, 3, 4, 5, 6} ,R = {(a, 1) , (b, 3) , (b, 4) , (c, 5) , (d, 2) , (d, 6) , (e, 3) , (e, 5) , (e, 6)}b) A = {1, 2, 3, 4, 5, 6} y la relación binariaR = {(1, 2) , (1, 3) , (2, 5) , (2, 4) , (3, 1) , (3, 3) , (3, 5) , (4, 6) , (5, 2) , (5, 5) , (6, 4) , (6, 6)} .

Exercise 161 Dadas las siguientes relaciones en forma gráfica encontrar el con-junto del producto cartesiano y la otra representación gráfica.

Page 37: Algebra superior i   reyes

5.1. RELACIONES ENTRE CONJUNTOS FINITOS 33

a)

b)

Exercise 162 Hacer una gráfica que refleje que en un torneo de fútbol en dondeestán inscritos 5 equipos y cada equipo va a jugar contra dos equipos. ¿Cómo sirveesta representación para asignarles días consecutivos de juego a los partidos de talmanera que ningún equipo juegue dos días consecutivos?

Exercise 163 Trazar la gráfica dirigida de la relación binaria “divide a” sobreA = {1, 2, . . . 12} .

Exercise 164 ¿Cómo se ve la gráfica dirigida de una relación que es(a) reflexiva?(b) simétrica?(c) transitiva?

Page 38: Algebra superior i   reyes

34 CAPÍTULO 5. MATEMÁTICAS DISCRETAS

5.2. Representación matricial de una relación.

5.2.1. Definiciones del álgebra matricial en general

Una matriz es un arreglo demn números aij enm renglones y n columnas dondeel índice i corresponde al renglón i y el índice j corresponde a la columna j. Si losnúmeros pertenecen al conjunto de los números reales se dice que es una matrizsobre R.Una matriz es

A =

a11 a12 · · · a1na21 a22 · · · a2n· · ·am1 am2 · · · amn

Notation 165 A = (aij)m×n .

Example 166 Una matriz sobre los racionales es1 −1 0

1

3−2 0 5 17

82 −5 −1

El elemento del segundo renglón y tercera columna a23 = 5.

Definition 167 Si la matriz tiene m renglones y n columnas se dice que es deorden m× n, se lee m por n.

Example 168 La matriz del ejemplo es 3× 4, se lee tres por cuatro.Definition 169 Si m = n entonces se dice que la matriz es cuadrada.

Definition 170 Al conjunto de los elementos aii se le llama diagonal principal dela matriz.

Definition 171 La matriz cuadrada de orden n tal que

aij =

½1 si i = j0 si i 6= j

se le denota por In.

Example 172 Para n = 4

I4 =

1 0 0 00 1 0 00 0 1 00 0 0 1

Definition 173 Dada una matriz A de orden m×n se define la matriz traspuestade A como la matriz B que tiene como renglones las columnas de A.

Notation 174 B = At o B = Atr o B = tras(A).

Remark 175 Si A es de orden m× n entonces At es de orden n×m.

Remark 176 Si A = (aij)m×n entonces At = (aji)n×m .

Definition 177 Si A = At entonces se dice que A es una matriz simétrica.

Page 39: Algebra superior i   reyes

5.2. REPRESENTACIÓN MATRICIAL DE UNA RELACIÓN. 35

Producto de matrices

Dadas dos matrices Am×n y Bn×r se define la matriz producto C de orden m×ra la matriz formada por los elementos

cij = ai1b1j + ai2b2j + . . .+ ainbnj

donde i = 1, . . . ,m y j = 1, . . . , r.

Example 178 Sean las matrices

A =

2 −34 6−1 3

B =

µ8−7

¶dos matrices. Para poder efectuar el producto AB hay que verificar que el númerode columnas de la primera matriz, A sea igual al número de renglones de la segundamatriz B. En este caso este número es 2 por tanto si es posible hacer el producto,se obtiene una matriz de orden 3× 1. 2 −3

4 6−1 3

µ 8−7

¶=

2(8) + (−3)(−7)4(8) + 6(−7)(−1)8 + 3(−7)

=

37−10−29

5.2.2. Relaciones

La forma de representar una relación R entre dos conjuntos finitos A y B es en unarreglo matricial en donde se ponen como renglones los elementos del primer conjun-to A y como columnas los elementos del segundo conjunto B, A = {a1, a2, . . . , am}y B = {b1, b2, . . . , bn} Cuando un elemento (ai, bj) ∈ R se coloca un 1 en el renglóni y la columna j. En los lugares donde no hay un tal elememento se pone un 0.

Example 179 Para la relación R del producto cartesiano entre A = {a, b, c, d, e} yB = {1, 2, 3, 4, 5, 6} tal que R = {(a, 1) , (b, 3) , (b, 4) , (c, 5) , (d, 2) , (d, 6) , (e, 3) , (e, 5) , (e, 6)}se representa con la matriz

MR =

1 2 3 4 5 6abcde

1 0 0 0 0 00 0 1 1 0 00 0 0 0 1 00 1 0 0 0 10 0 1 0 1 1

A esta matriz se le llama matriz de adyacencia ya que al representarla gráfica-

mente cada 1 corresponde a una arista de la gráfica.

Page 40: Algebra superior i   reyes

36 CAPÍTULO 5. MATEMÁTICAS DISCRETAS

Para una relación binaria sobre un conjunto A queda como en el siguiente:

Example 180 Si A = {1, 2, 3, 4} y la relación dada como conjunto esR = {(1, 1) , (1, 3) , (1, 4) , (2, 1) , (2, 4) , (3, 4) , (4, 1)} entonces la matriz es

MR =

1 0 1 11 0 0 10 0 0 11 0 0 0

y la gráfica

Las matrices de adyacencia se utilizan para representar una relación en la computa-dora. Aún más las operaciones usuales entre relaciones se pueden realizar con lasoperaciones usuales entre matrices y las reglas del álgebra booleana. En la siguientesección se da la correspondencia entre operaciones entre matrices y operacionesentre relaciones.

Page 41: Algebra superior i   reyes

5.2. REPRESENTACIÓN MATRICIAL DE UNA RELACIÓN. 37

Exercise 181 Dadas las siguientes relaciones encontrar las otras tres representa-cionesa) A = {a, b, c, d, e, f, g}, R una relación binaria sobre A definida porR = {(a, b) , (a, d) , (a, f) , (a, g) , (b, a) , (b, b) , (b, f) , (b, g) , (c, e) , (d, e) , (d, g) , (e, f) , (f, g) , (g, c)} .b) A = {1, 2, 3}y una relación binaria definida por la matriz

MR =

1 1 11 1 11 1 1

c)

d)

5.2.3. Operaciones entre relaciones:

Una función es un caso particular de relación. Es posible pensar en las mismasoperaciones para las relaciones que las que hay entre funciones. Dos de ellas soncomponer las relaciones y encontrar la inversa de una relación. Las otras dos opera-ciones que se exploran en estas notas son una consecuencia de ver a las relacionescomo conjuntos.

Page 42: Algebra superior i   reyes

38 CAPÍTULO 5. MATEMÁTICAS DISCRETAS

Composición

La composición de relaciones R1 ⊂ A×B y R2 ⊂ B × C es la relación

R1 ◦R2 = {(a, c) | ∃b tal que ((a, b) ∈ R1) ∧ (b, c) ∈ R2}

Remark 182 La notación utilizada es diferente a la de funciones porque al llevarla relación a una matriz el orden de multiplicación es MR1MR2 . El + se sustituyepor la operación booleana ∨ (o) y × por la operación booleana ∧ (y). Las reglas son

1 + 1 = 1 = 1 + 0 = 0 + 1

0 + 0 = 0

1× 1 = 11× 0 = 0× 1 = 0× 0 = 0

Algunos autores utilizan el mismo orden que para funciones i.e. R2 ◦R1.

Example 183 La relación R1 “toma clase de” es un subconjunto del productocartesiano {estudiantes del Itam} × {cursos del Itam} . La relación R2 es “tieneclase en” es un subconjunto del producto cartesiano {cursos del Itam}×{salones del Itam} .La composición es la relación R1 ◦ R2 “tiene clase en” que es un subconjunto delproducto cartesiano {estudiantes del Itam} × {salones del Itam} .

Definition 184 Dada la relación binaria R sobre A se define por inducción lapotencia de R R2 = R ◦R y Rn = Rn−1 ◦R.

Exercise 185 Sea R la relación “padre de”.¿Cuál es la relación R ◦R?

Exercise 186 Sea R1 = {(0, a) , (0, c) , (1, a) , (1, c) , (2, b)} ⊂ {0, 1, 2, 3} × {a, b, c}yR2 = {(a, d) , (a, e) , (a, f) , (b, c) , (c, f)} ⊂ {a, b, c} × {d, e, f} . Calcular R1 ◦ R2.Escribir las matrices asociadas a R1, R2 y a R1 ◦R2, MR1, MR2 .y MR1◦R2 .Efectuar el producto de matrices MR1

MR2sustituyendo + por la operación booleana

∨ (o) y × por la operación booleana ∧ (y) Comparar con la matriz asociada a lacomposición.

Inversión.

Si R es una relación de A × B entonces R−1 es la relación de B × A tal que(b, a) ∈ R−1 si (a, b) ∈ R. La matriz asociada a R−1 es la traspuesta de MR. Lagráfica dirigida asociada a R−1 es la misma gráfica que R con las flechas en sentidoopuesto.

Exercise 187 Dada la relación binaria R sobre A = {0, 1, 2, 3} por la matriz

MR =

0 1 1 01 0 1 11 1 0 00 1 0 1

Calcular la matriz de R ◦R,trazar las gráficas para R y para R2.Escribir el subconjuto del producto cartesiano A×A.

Page 43: Algebra superior i   reyes

5.2. REPRESENTACIÓN MATRICIAL DE UNA RELACIÓN. 39

Complemento de una relación.

Dada una relación R ⊂ A × B se define el complemento de R considerando aA×B como el universo.Se denota Rc

Exercise 188 Calcular el complemento de la relación binaria R sobre A = {0, 1, 2, 3}dada por{(0, 1) , (0, 2) , (1, 0) , (1, 2) , (1, 3) , (2, 0) , (2, 1) , (3, 1) , (3, 3)} . Escribir la relación ysu complemento en forma matricial. ¿Qué operación hay que hacer sobre MR paraobtener la matriz del complemento?

Unión o Suma booleana

Dadas dos relaciones R y S de A×B se define la suma booleana R⊕S como launión de los subconjutos del producto cartesiano.i.e.

R⊕ S = R ∪ S

Exercise 189 Describir como se obtiene la matriz de R⊕S a partir de las matricesde R y S.

5.2.4. Propiedades de las relaciones y estructura de las ma-trices

En capítulos anteriores se dieron como ejemplos diferentes tipos de relaciones ya cada una se le dió un nombre de acuerdo a las propiedades que tiene. Por ejemplouna relación binaria es de equivalencia si es: reflexiva, simétrica y transitiva.¿Cómose traduce cada una de estas propiedades de la relación para la representaciónmatricial?

Proposition 190 Dado un conjunto A una relación binaria R sobre A tiene unamatriz asociada MR que tiene el mismo número de renglones que de columnas, i.e.MR es cuadrada.

Una relación R es reflexiva si aRa ∀a ∈ R

Proposition 191 Si R es reflexiva .entonces la matriz asociada a esta relacióntiene 1́s en la diagonal principal. Dicho de otra manera si MR = (mij) y R esreflexiva entonces mii = 1. Inversamente si mii = 1 entonces R es reflexiva.

Una relación R es simétrica si aRb implica bRa ∀a, b ∈ A.

Proposition 192 La relación R es simétrica si y sólo sí mij = mji, i.e.MR =M tR,

i.e. MR es simétrica.

Una relación R es transitiva si aRb y bRc implica que aRc ∀a, b, c ∈ A.

Proposition 193 La relación R es transitiva si y sólo sí la matriz asociada MR

es tal que mij = 1 y mjk = 1 implica que mik = 1 ∀i, j, k.

Proposition 194 Si M2R =MR entonces R es transitiva.

Una relación de orden como ≤ en el conjunto de los números enteros es unarelación binaria sobre el mismo conjunto pero no es de equivalencia. Esta relacióntiene la propiedad de que a ≤ b y b ≤ a implica a = b.A esta propiedad se le llamaantisimétrica.

Page 44: Algebra superior i   reyes

40 CAPÍTULO 5. MATEMÁTICAS DISCRETAS

Definition 195 Dado un conjunto A y R una relación binaria sobre A se dice queR es antisimétrica si aRb y bRa implica a = b.

Definition 196 Sean M = (mij) y N = (nij) ambas de orden m× n.Entonces sedice que M ≤ N si mij ≤ nij para i = 1, . . . ,m; j = 1, . . . ,m.

Con esta definición se van a reescribir las proposiciones anteriores como:

Proposition 197 Dado un conjunto A, finito de cardinalidad n, R una relaciónbinaria sobre A y MR la matriz asociada entonces(a) R es reflexiva ⇔ In ≤MR

(b) R es simétrica ⇔ MR =M tR

(c) R es transitiva ⇔M2R ≤MR

(d) R es antisimétrica ⇔ MR ∩M tR ≤ In

Transitividad

La transitividad es una propiedad de las gráficas dirigidas que es interesanteporque al realizar composición de relaciones binarias se obtiene el número de aristasque hay que recorrer entre dos elementos cualesquiera y se obtiene una arista entreel elemento inicial y el último. Una aplicación de este algoritmo se utiliza en ladetección de inconsistencia de datos en las bases de datos relacionales. Este errornormalmente ocurre cuando un usuario modifica los datos que no están protegidos.La forma matricial de encontrar la cerradura transitiva de una relación R es

haciendo composiciones sucesivas (potencias de la matriz MR) de la misma hastaque Mn

R =Mn+1R para después tomar la disyunción de las matrices obtenidas.

MR∗ =MR ∨MR2 ∨ · · ·

Este último paso se entiende mejor si se piensa a la relación R en la representacióncomo subconjunto del producto cartesiano y se ve queMR2 ≤MR y que la digráficaasociada a MR2 contiene a los caminos con al menos 3 vértices.El algoritmo de Warshall, basado en la representación de digráfica de la relación,

simplifica este proceso.

Algoritmo de Warshall

Recordar la definición de camino o trayectoria en una digráfica:

Definition 198 Camino o trayectoria Un camino es una sucesión de vértices yaristas que van de un vértice llamado inicial a un vértice llamado final.

Definition 199 Si a, v1, v2, . . . , vn, b es un camino en una digráfica R, con a 6= v1y b 6= vn, n > 2 entonces los vértices v1, v2, . . . , vn se llaman vértices interiores deeste camino.

Definition 200 Dada la relación R se define T la matriz de alcance de R a lamatriz tal que tij = 1 si y sólo sí existe un camino de vi a vj .

El algoritmo de Warshall consiste en ir construyendo matrices de adyacenciaMR =W0,W1, . . . ,Wn = T.

Notation 201 Al elemento en el renglón i y la columna j de la matriz Wk lodenotaremos por Wk[i, j].

Page 45: Algebra superior i   reyes

5.2. REPRESENTACIÓN MATRICIAL DE UNA RELACIÓN. 41

Se van a construir las matrices inductivamente:W1[i, j] = 1 si y sólo sí hay un camino de vi a vj tal que el subconjunto {v1} es

un conjunto de vértices interiores del camino.W2[i, j] = 1 si y sólo sí hay un camino de vi a vj tal que el subconjunto {v1, v2}

es un conjunto de vértices interiores del camino.

Wk[i, j] = 1 si y sólo sí hay un camino de vi a vj tal que el subconjunto{v1, . . . , vk} es un conjunto de vértices interiores del camino.Al escribir las matrices se procede como sigue:

Paso1: Se toma MR =Wo

Paso 2: Para construir W1 se copian los 1́s de W0.

Paso3: Se toma la columna 1y se hace una lista de todos los renglones r1, r2, . . . , rsen los que la entrada sea 1.

Paso 4: Se toma el renglón 1 y se hace una lista de todas las columnas c1, c2, . . . , csen los que la entrada sea 1.

Paso 5: Escribir un 1 en la posición ricj si no aparece en W0.

Paso 6: Se procede a construir W2 a partir de W1,ahora tomando la columna 2 yel renglón 2.

Se construye Wk a partir de Wk−1 y se toma la columna k y el renglón k.

El proceso termina cuando k = orden de la matriz.

Example 202 Considerar la relación binaria R con la siguiente matriz asociada

MR =

0 1 0 01 0 1 00 0 0 10 0 0 0

Encontrar su cerradura transiitiva.

Solution 203 El primer paso es llamar W0 a MR.Para construir W1 primero se ponen los 1́s en donde aparecen en W0

11 1

1

Se toma la primera columna. En el renglon 2 hay un 1.Se toma el primer renglón. En la columna 2 hay un 1.Entonces en el lugar renglón2 columna 2 se agrega un 1.

W1 =

1

1 1 11

Se continua el proceso pero ahora se toma la columna 2. En los renglones 1 y 2 hayun 1.

Page 46: Algebra superior i   reyes

42 CAPÍTULO 5. MATEMÁTICAS DISCRETAS

En el renglón 2,en las columnas 1, 2 y 3 hay un 1.Si no existen hay que agregar 1́s en los lugares (1, 1), (1, 2) , (1, 3) , (2, 1) , (2, 2) , (2, 3)y esto es W2

W2 =

1 1 11 1 1

1

Para construir W3 se toma la columna 3 de W2. Hay 1́s en los renglones 1, 2.En el renglón 3, hay 1́s en la columna 4. Para construir W3 hay que agregar 1́s enlos lugares (1, 4) , (2, 4) .

W3 =

1 1 1 11 1 1 1

1

Para construir W4,en la columna 4, hay 1́s en los renglones 1, 2, 3 y en el renglón4 no hay 1́s. Entonces W3 =W4.Porlo tanto

T =

1 1 1 11 1 1 10 0 0 10 0 0 0

Exercise 204 Construir la cerradura transitiva utilizando el algoritmo de Warshallde la relación binaria R dada por la matriz y dibujar las digráficas asociadas a R ya T.a)

MR =

0 1 0 01 0 1 01 0 0 10 1 0 0

b)

MR =

0 1 01 1 00 0 1

Exercise 205 Para la relación del inciso (b) del ejercicio anterior construir Tcomo

T = I3 ∨MR ∨ . . .Contar el número de operaciones que se tienen que realizar para obtener el resultadoy comparar con los pasos del ejercicio anter

Page 47: Algebra superior i   reyes

Capítulo 6

Conteo

El problema de conteo es tan antiguo como el inicio del conocimiento humano.Los números se inventaron para contar. Sin embargo, el problema moderno de con-teo va más allá de la escritura y utiliza el conocimiento de la teoría de conjuntoscomo base para contar elementos de un conjunto de posibilidades que no se puedenenumerar por la cardinalidad tan grande. Es de este tipo de problemas de los quelos cursos de álgebra se ocupan en la actualidad. La teoría de probabilidad, la es-tadística.y la computación del siglo XX nos obligan a conocer las nuevas técnicas deconteo abstracto y general. Los libros de Matemáticas discretas que se han escritopara enseñar estas técnicas a los futuros ingenieros y actuarios son una muestra delgran avance que han tenido estas técnicas durante los últimos siglos. Como siemprees en el curso de álgebra donde se explican los métodos generales y proporcionanlas habilidades de contar antes de entrar en los problemas de aplicación dentro dela probabilidad y la computación.

6.1. Principios básicosPara precisar los conceptos a los que se van a hacer referencia primero se va a

distinguir un fenómeno determinístico de uno probabilístico. Un fenómeno deter-minístico es aquel del que siempre se esta seguro de cual va a ser el resultado. Porejemplo, si se suelta un objeto a cierta distancia del piso se esta seguro que éste va aestar sujeto a la fuerza de gravedad y va a llegar al piso. El fenómeno probabilísticoes aquel que tiene muchas posibilidades de resultados. Por ejemplo, si se compra unbillete de lotería no se sabe cual va a ser el número premiado. En resumen se puededecir:

Definition 206 Un fenómeno probabilístico o evento es un proceso físico que tieneun número de posibles resultados.

Example 207 De una colección de objetos tomar uno para colocarlo en una caja.

Example 208 Dado un número n de objetos colocar cierto número en m cajas.

Example 209 Asignar oficina a un cierto número de profesores.

Example 210 Llenar una boleta de carreras de caballos con un posible resultadopara los dos primeros lugares.

En este capítulo se abordarán algunas técnicas para contar el número de posiblesresultados del fenómeno probabilístico.En los problemas simples de conteo siempre están presentes las operaciones de

suma y producto. Se iniciará con problemas simples de suma.

43

Page 48: Algebra superior i   reyes

44 CAPÍTULO 6. CONTEO

6.1.1. Suma y resta para contar

Se iniciará por una aplicación simple de la teoría de conjuntos y los diagramasde Venn. Suponer que dado un universo U y dos conjuntos A y B ⊂ U ajenos,es decir A ∩ B = ∅. Se denotará por N(A) a la cardinalidad del conjunto A. Lasiguiente igualdad es verdadera

N (A ∪B) = N (A) +N (B)

Se demuestran, con teoría de conjuntos, los siguientes resultados:

Proposition 211 Dado un universo U y dos conjuntos cualesquiera de ese univer-so, A y B entonces los conjuntos A−B,A ∩B y B −A son ajenos por parejas.

Proposition 212 Dado un universo U y dos conjuntos cualesquiera de ese univer-so, A y B entonces A = (A−B) ∪ (A ∩B) .

Proposition 213 Dado un universo U y dos conjuntos cualesquiera de ese univer-so, A y B entonces A ∪B = (A−B) ∪ (A ∩B) ∪ (B −A)

.

A

A int B

B

A partir de estos tres resultados y del primero enunciado es posible demostrar

Theorem 214 Dado un universo U y dos conjuntos cualesquiera de ese universo,A y B entonces

N (A ∪B) = N (A) +N (B)−N (A ∩B)

Proof. Por la segunda proposición

A = (A−B) ∪ (A ∩B)∅ = (A−B) ∩ (A ∩B)

entoncesN (A) = N (A−B) +N (A ∩B)

Page 49: Algebra superior i   reyes

6.1. PRINCIPIOS BÁSICOS 45

al despejarN (A−B) = N (A)−N (A ∩B)

AnálogamenteN (B −A) = N (B)−N (A ∩B)

Por la tercera proposición y el resultado inicial

N (A ∪B) = N (A−B) +N (A ∩B) +N(B −A)

Al sustituir las últimas igualdades

N (A ∪B) = N(A)−N (A ∩B) +N (A ∩B) +N(B)−N (A ∩B)N(A ∪B) = N(A) +N(B)−N(A ∩B)

Exercise 215 Demostrar las tres proposiciones de teoría de conjuntos.

Exercise 216 ¿Cuántos conjuntos ajenos hay en un universo cuando se trata detres conjuntos que no son ajenos entre sí?

Exercise 217 Esribir el resultado para tres conjuntos. Es decir calcular N (A ∪B ∪ C) .Exercise 218 ¿Cuántos conjuntos ajenos se establecen en un universo cuando haycuatro conjuntos que no son ajenos entre sí? ¿Cuántos cuando hay n conjuntos noajenos entre sí?

Example 219 Un representante del personal académico de una Universidad se vaa escoger de entre los profesores que pertenecen al departamento de Filosofía queson 40 y los que pertenecen al departamento de Física que son 35.

Solution 220 El primer evento es elegir del conjunto A, que es el conjunto depersonas que pertenecen al departamento de Filosofía y el segundo evento es elegirdel conjunto B, que es el conjunto de los que pertenecen al departamento de Física.Entonces N(A) = 40 y N(B) = 35, como A ∩ B = ∅ por lo tanto N(A ∪ B) =N(A) +N(B) = 40 + 35 = 75.

Example 221 En un grupo de 50 estudiantes de computación se tiene que 25 estánestudiando C++, 30 estudian Visual Basic y 10 estudian ambos.¿Cuántos estudianun lenguaje de computación?

Solution 222 En primer lugar se identifican los conjuntos. Sea U el universo elconjunto de los 50 estudiantes de computación. El conjunto A los que estudianC++ y el conjunto B los que estudian Visual Basic. La pregunta es ¿cuál es lacardinalidad de A ∪B? El otro dato es que N (A ∩B) = 10.Una forma directa de resolver el problema con diagramas de Venn es escribir en laintersección 10, en el conjunto A hay 25 entonces en A−B hay 15. Análogamente,en el conjunto B hay 30 entonces en B − A hay 20. Al sumar los tres números larespuesta es 45. Todavía se puede agregar que 5 no estudian lenguaje alguno.La forma algebraica es aplicar la fórmula

N(A ∪B) = N(A) +N(B)−N(A ∩B)N(A ∪B) = 25 + 30− 10 = 45

Example 223 En una encuesta a 120 pasajeros de una aerolínea se obtuvieronlas siguientes respuestas.A 48 les gusta el vino con sus alimentos, a 78 les gustanbebidas preparadas y a 66 té helado. Además a 36 les gustan cualesquiera dos de lasbebidas y a 24 cualquiera de las tres.¿A cuántos pasajeros solamente les gusta el té?¿A cuántos pasajeros les gustan exactamente dos de las tres bebidas?

Page 50: Algebra superior i   reyes

46 CAPÍTULO 6. CONTEO

Solution 224 Se define como A al conjunto de pasajeros que les gusta el vino, Bal conjunto de pasajeros que les gutan las bebidas preparadas y C al que les gusta elté helado. Primero con diagramas de VennN (A) = 48, N (B) = 78 y N (C) = 66.Se inicia en A ∩ B ∩ C. Allí hay 24 personas. Hay tres partes que corrsponden aexactamente dos de las preferencias y hay 36 personas entre todas, por lo tanto hay12 personas en cada una. Si se suman las personas que están en A se deduce quecualquiera que bebe vino también le gustan las bebidas preparadas o el té helado.Solamente hay 30 personas a las que solamente les gustan las bebidas preparadasy 66 − 48 = 18 a las que solamente les gusta el té helado. Al hacer la suma detodos los conjuntos ajenos resulta 24 + 3 (12) + 18 + 30 = 108. Como en total eran120 pasajeros hay 12 que no pertenecen a estos conjuntos. Se obtuvo la informacióncompleta de como están distribuidos los pasajeros. La pregunta es ¿A cuántos lesgusta el té helado solamente? La respuesta es 30. y a la pregunta ¿A cuántos lesgustan exactamente dos bebidas? es 36 = 3 (12) .La respuesta algebraica

N (A ∪B ∪ C) = N (A) +N (B) +N (C)− [N (A ∩B) +N (A ∩ C) +N (B ∩ C)] +N (A ∩B ∩ C)108 = 48 + 78 + 66− 3(36) + 24

Además la respuesta a ¿cuántos les gusta el té helado? es

N (C − (A ∪B))Remark 225 Observar que estos problemas son de tres tipos diferentes. El primeroque se abordó es un proceso dinámico de algo que se va a realizar a futuro, el segundoes un evento presente y el tercero es descripción de algo pasado. En los tres casos seaplica la suma y resta para contar. En los tres casos el evento se puede representarpor conjuntos ajenos.

Summary 226 Si el evento se puede describir por conjuntos ajenos ya sea queocurrieron en el pasado, que sea la situación actual o que van a ocurrir en el futuro,

Page 51: Algebra superior i   reyes

6.2. PRINCIPIO DE INCLUSIÓNY EXCLUSIÓN PARADOS Y TRES CONJUNTOS47

pero todo en una sola etapa entonces el número de posibilidades se calcula como lasuma de las cardinalidades de los conjuntos ajenos.

En los siguientes ejercicios primero identificar los conjuntos ajenos para aplicarla regla de la suma.

Exercise 227 Un estudiante tiene dinero para comprar solamente un libro de textoen una librería. Las dos materias de las que encuentra textos son computación yálgebra. Encuentra 40 títulos de álgebra y 50 de computación. ¿De cuántas maneraspuede elegir el texto?

Exercise 228 Un profesor le va a prestar un libro a un alumno para que aprenda aprogramar. El profesor tiene el mismo número de libros de C++, de Visual Basic,Maple y MathLab, 5 de cada uno. Solamente le va a prestar un libro. ¿De cuántasformas lo puede hacer?

Exercise 229 Un distribuidor de computadoras tiene 100 PC´s en el almacén. Deesas 25 son Pentium II, 40 tienen CD, 10 tienen monitor de 25 pulgadas y CD,55 tienen monitor de 35 pulgadas, 15 tienen Pentium II y CD y 5 tienen PentiumII con monitor de 35 pulgadas sin CD. ¿Cuántas son Pentium II que tienen CD ymonitor de 25 pulgadas?¿Cuántas tiene CD, tienen monitor de 35 pulgadas y noson Pentium II?¿Cuántas tienen CD o monitor de 25 pulgadas y no son PentiumII?

Exercise 230 En una universidad hay 512 estudiantes de computación y todostiene computadora. De éstos 281 tienen además impresora, 167 tienen internet, 98tienen CD y 75 tienen impresora y CD.¿ Cuántos de los estudiantes tienen internety no tienen impresora ni CD?

Exercise 231 Una compuerta lógica AND de un chip tiene tres conectores: dosentradas(inputs) y una salida (output). Estos conectores pueden tener tres fallasposibles:F1: la primera entrada se traba en 0.F2:la segunda entrada se traba en 0.F3: la salida se traba en 1.Para una muestra de 100 de estas compuertas sean los conjuntos A,B y C lossubconjuntos con la falla F1,F2 y F3 respectivamente. Hay 23 con la falla F1, 26con F2 y 30 con F3. Hay 7 que tienen las fallas F1 y F2, 8 con las fallas F1 y F3 y10 con las fallas F2 y F3. Ademas hay 3 que tienen las tres fallas.¿Cuántas de lascompuertas tienen algún defecto?

Exercise 232 El administrador de una universidad reporta que hay 1500 profe-sores. De éstos 1260 son hombres, 1080 ganan más de $300, 000 al año, 780 tienenmás de 35 años, 560 son hombres mayores de 35 años, 710 tienen más de 35 años yganan más de $300, 000 al año, 600 son hombre que ganan más de $300, 000 al año.¿Son correctas estas cantidades? Si la respuesta es no justificar. Si la respuesta essi ¿cuántas mújeres ganan más de $300, 000 al año y tienen menos de 35 años?

6.2. Principio de inclusión y exclusión para dos ytres conjuntos

Complemento de un conjunto

Dado un conjunto universal U con cardinalidad N (U) y unconjunto A ⊂ U setiene la relación

N(A) +N(Ac) = N(U)

Page 52: Algebra superior i   reyes

48 CAPÍTULO 6. CONTEO

Este hecho se utilizó para resolver algunos de los ejercicios anteriores. El empleode este resultado combinado con las leyes de DeMorgan permite resolver algunosproblemas más.Las leyes de DeMorgan para conjuntos se enuncian

(A ∪B)c = Ac ∩Bc

(A ∩B)c = Ac ∪Bc

entonces al aplicar el resultado a la cardinalidad

N (Ac ∩Bc) = N ((A ∪B)c)que al aplicar la igualdad del complemento

N ((A ∪B)c) = N (U)−N (A ∪B)que finalmente es

N (Ac ∩Bc) = N (U)−N (A ∪B)Además

N(A ∪B) = N(A) +N(B)−N(A ∩B)al sustituir se obtiene

N (Ac ∩Bc) = N(U)− [N(A) +N(B)−N(A ∩B)]N (Ac ∩Bc) = N(U)− [N(A) +N(B)] +N(A ∩B)

Al aplicar las mismas fórmulas a tres conjuntos primero se obtiene

N (A ∪B ∪ C) = [N (A) +N (B) +N (C)]− [N (A ∩B) +N (A ∩ C) +N (B ∩ C)]+N (A ∩B ∩C)

por lo tanto al aplicar la ley de DeMorgan para el complemento de la unión .

N (Ac ∩Bc ∩ Cc) = N (U)− [N (A) +N (B) +N (C)]

+ [N (A ∩B) +N (A ∩ C) +N (B ∩ C)]−N (A ∩B ∩ C)Example 233 Número de enteros que no son divididos por ciertos primos. Calcularel número de enteros entre 1 y 100 que no sean divisibles por 2, 3 y 5.

Solution 234 Entonces A1 es el conjunto de los enteros entre 1 y 100 que sondivisibles por 2, A2 es el conjunto de los que son divisibles por 3 y A3 los que sondivisibles por 5. Para resolver el problema es necesario calcular

N (Ac1 ∩Ac

2 ∩Ac3)

Al aplicar la fórmula del principio de inclusión exclusión

N (Ac1 ∩Ac

2 ∩Ac3) = N(U)− [N(A1) +N (A2) +N (A3)]

+ [N (A1 ∩A2) +N (A1 ∩A3) +N (A2 ∩A3)]−N (A1 ∩A2 ∩A3)

Como N(U) = 100 y

N (A1) =100

2= 50

N (A2) =

¹100

3

º= 33

N (A3) =100

5= 20

Page 53: Algebra superior i   reyes

6.2. PRINCIPIO DE INCLUSIÓNY EXCLUSIÓN PARADOS Y TRES CONJUNTOS49

además

N (A1 ∩A2) =¹100

6

º= 16

N (A1 ∩A3) = 100

10= 10

N (A2 ∩A3) =¹100

15

º= 6

y

N (A1 ∩A2 ∩A3) =¹100

30

º= 3

Por lo tanto

N (Ac1 ∩Ac

2 ∩Ac3) = 100− [50 + 33 + 20] + [10 + 16 + 6]− 3 = 26

son los enteros entre 1 y 100 que no son divisibles por 2, 3 y 5.

Exercise 235 Determinar el número de números enteros positivos n, 1 ≤ n ≤ 3000que no son divisibles por 3, 5 y 7.

Exercise 236 Una persona va a comprar un automóvil de entre 15 que hay en latienda. Le dan la siguiente información(a) Hay 6 que tienen aire acondicionado.(b) Hay 6 que tienen quemacocos.(c) Hay 6 que tienen CD con tocador de cinco discos.(d) Hay 1 que tiene aire acondicionado y quemacocos.(e) Hay 1 que tiene quemacocos y tocador CD de 5 discos.(f) Hay 2 que tienen aire acondicionado y tocador de 5 discos.(g) No hay uno que tenga las tres cosas.¿Cuántos tienen exactamente una de las tres cosas?¿Cuántos no tienen ninguna de las tres cosas?

6.2.1. Producto y división para contar

Cuando el evento se puede dividir en al menos dos tiempos diferentes entoncesse utiliza el producto. Por ejemplo

Example 237 Se van a colocar en dos cajas 10 pelotas diferentes. El primer tiempoes colocar una pelota en la primera caja. Esto se puede hacer de 10 formas diferentes.El segundo tiempo es colocar otra pelota en la segunda caja. Como ya nada más nosquedan 9 pelotas entonces hay 9 posibilidades. En total hay 10×9 = 90 posibilidadesde colocar las pelotas en dos cajas.

Example 238 Para una obra de teatro hay 6 hombres y 8 mujeres que aspiranal papel principal de una pareja.¿De cuántas formas se puede elegir a la parejaprincipal? La solución es 6×8 = 48. La elección de la pareja se hace en dos tiemposdiferentes. Primero se elige al hombre y después a la mujer.

Example 239 Dado un producto de dos factores (x− 1) (x+ 3) ¿cuántas formasposibles hay para los signos de los factores? Para el primer factor hay dos posibil-idades, positivo y negativo y similarmente para el segundo factor. En total hay 4formas posibles para los signos de estos dos factores.

Page 54: Algebra superior i   reyes

50 CAPÍTULO 6. CONTEO

Example 240 Ahora para el producto de tres factores diferentes hay 8 posibilidadespara los signos. Si nada mas interesa saber cuando el producto es negativo se dividepor 2 y quedan 4 posibilidades.

Exercise 241 Una fábrica de automóviles produce 4 marcas diferentes, en 12 col-ores, con 3 tamaños de motor y 2 tipos diferentes de transmisión. ¿Cuántos difer-entes tipos de automóvil se pueden producir?

Exercise 242 Del menú del día de un restaurante se puede escoger una sopa deentre 3 posibles, un plato intermedio de 4 posibles, un plato fuerte de entre 5 posiblesy un postre de entre 3 posibles. ¿ Cuántas combinaciones de platillos hay en el menúdel restaurante?

Exercise 243 En una taqueria se pueden pedir los tacos al pastor con o sin cebolla,con o sin cilantro, con o sin piña y con o sin salsa. ¿De cuántas formas se puedenordenar los tacos?

Exercise 244 ¿Cuántos casos posibles hay que considerar para resolver la desigual-

dad(x+ 5) (x− 3) (x− 6)

(x+ 2) (x− 8) ≥ 0?

Exercise 245 Para ir de la Ciudad de México a Guadalajara se pasa por Irapu-ato. Para ir de México a Irapuato hay 2 caminos posibles, para ir de Irapuato aGuadalajara hay 6 alternativas. ¿De cuántas maneras se puede viajar de la Ciudadde México a Guadalajara?

Exercise 246 En el ejercicio anterior hay además dos rutas directas que no pasanpor Irapuato. ¿De cuántas maneras se puede ir de la Ciudad de México a Guadala-jara considerando estas nuevas rutas?

Ordenaciones o permutaciones de n elementos

Dados n objetos diferentes ¿De cuántas formas se pueden ordenar? A cada unade las formas como se ordenan los n elementos se le llama permutación porquese obtiene de la anterior permutando algunos elementos. El nombre de ordenaciónviene de que cada posibilidad tiene un orden diferente. Si son n elementos entoncesel primer lugar se puede llenar de n formas diferentes, el segundo de n− 1 formasdiferentes, así sucesivamente hasta el n -ésimo lugar de 1 forma. El resultado nosda

n (n− 1) . . . 2 (1)

Definition 247 Para simplificar a este producto n (n− 1) . . . 2 (1) se le llama nfactorial y se denota por n!.Por conveniencia se define 0! = 1.

Exercise 248 Haz una lista completa de las permutaciones de 3 símbolos difer-entes.

Exercise 249 ¿Cuántas permutaciones de 8 símbolos diferentes hay?

Ordenaciones de n elementos en grupos de r

Este problema se puede plantear de dos formas:

Case 250 (1) Hay n símbolos diferentes y se van a llenar r lugares. ¿De cuántasformas es posible llenar los r lugares?

Page 55: Algebra superior i   reyes

6.2. PRINCIPIO DE INCLUSIÓNY EXCLUSIÓN PARADOS Y TRES CONJUNTOS51

Solution 251 El primer lugar se puede llenar de n formas diferentes, el segundose puede llenar de n−1 formas diferentes, hasta el r-ésimo lugar se puede llenar den− (r − 1) formas diferentes entonces en total hay n (n− 1) . . . (n− r + 1) formasdiferentes de llenar los r lugares. Algebraicamente el producto es igual a

n (n− 1) . . . (n− r + 1) =n!

(n− r)!

Notation 252 Como cada uno de los resultados posibles tiene un orden diferenteentonces al número de resultados posibles se les llama ordenaciones de n elementostomados en grupos de r y se denota por

Orn = O (n, r)

Algunos autores le llaman a cada una de las posibilidades de un grupo de los robjetos una permutación y lo denotan por P (n, r).

Case 253 (2) Otra forma de ver el mismo problema es considerar que hay n lugaresen donde se van a colocar r simbolos diferentes.

Solution 254 El primer símbolo se puede colocar en n lugares, una vez colocadoel primer símbolo quedan (n− 1) lugares donde se puede colocar el segundo símbolo,así sucesivamente hasta cuando se va a colocar el símbolo r -ésimo hay [n− (r − 1)]lugares posibles donde es posible colocarlo- Es decir hay

n (n− 1) . . . (n− r + 1)

formas diferentes de colocar r símbolos en los n lugares.

Exercise 255 Se van a escoger 5 personas de un grupo de30 para ocupar los cargosde la mesa directiva de la Sociedad de Alumnos. En el orden en que se elijan van aocupar los diferentes cargos.¿De cuántas formas se pueden escoger?

Exercise 256 ¿De cuántas formas se pueden ordenar las letras de la palabra mur-ciélago?

Combinaciones de n elementos en grupos de r

Una forma de ver las combinaciones es cuando se van a escoger n elementos engrupos de r pero el orden no es importante entonces se habla de combinaciones de nobjetos tomados de r en r. Por ejemplo de un grupo de 36 alumnos se van a elegir 5para explicar un problema. El primer lugar se puede ocupar de 36 formas diferentes,el segundo de 35, asi sucesivamente, el quinto lugar se puede ocupar de 32 formas.Pero como no importa si la persona A fue escogida en el primer lugar o en el últimoentonces hay que dividir por el número de permutaciones de 5 elementos,

36 35 34 33 32

5!

que algebraicamente es igual a36!

(36− 5)!5!que se denota por µ

36

5

¶En general µ

n

r

¶=

n!

(n− r)!r!

Page 56: Algebra superior i   reyes

52 CAPÍTULO 6. CONTEO

Otra forma de ver el problema es suponer que se tienen n lugares y se van allenar con dos objetos diferentes. Del primer objeto se van a tomar r objetos y delsegundo (n− r) . Como son n lugares hay n! posibles posiciones, además como r y(n− r) son iguales hay que dividir por r! (n− r)!.µ

n

r

¶=

n!

(n− r)!r!

Si se recuerda este es el coeficiente del sumando r del binomio de Newton (a+ b)nporque

cada término va a tener n factores con n− r del símbolo a y r factores que son elsímbolo b.

(a+ b)n= an +

µn

1

¶an−1b+ . . .+

µn

n− 1¶abn−1 + bn

Exercise 257 Un estudiante presenta un examen con 10 preguntas pero el profesorle indica que solamente escoja 7 de las 10. ¿De cuántas maneras puede escoger laspreguntas?

Exercise 258 De los primeros dos años de secundaria se va a formar un equipo devolibol con 9 participantes. En primero de secundaria hay 28 personas y en segundo25. ¿De cuántas maneras diferentes se puede integrar el equipo?

Exercise 259 Un mazo de barajas consta de 52 cartas, 13 cartas desde el as hastael rey, en cuatro palos diferentes: tréboles ♣, corazones rojos ♥, espadas o corazonesnegros ♠ y rombos ¨. Cada carta del mazo es diferente. El problema es ¿de cuántasformas se pueden elegir tres cartas del mazo de tal forma que no importe el orden?

Exercise 260 Una persona va a invitar a 11 personas de un grupo de 20. ¿Decuántas maneras diferentes puede hacer los grupos para invitar a las 11 personas?

Exercise 261 ¿Cuántos subconjuntos de 4 elementos se pueden formar a partir deun conjunto con 12 elementos?

Exercise 262 De un mazo de 52 cartas ¿de cuántas formas se pueden elegir 5cartas de tal forma que no haya cartas de corazones rojos ♥? (Recordar que hay 13cartas del mismo palo).

Exercise 263 ¿Cuántos términos hay en el binomio de Newton (a+b)10 que tengana4b6?

Ordenaciones con repetición

Con reemplazo Suponer que se tienen que escribir todas las cadenas de 10 letrastomando las letras del alfabeto con 26 símbolos diferentes. Aquí se va a suponer queel número de veces que se puede escoger cada letra es ilimitado, otra forma de verloes pensar que el símbolo que se va utilizando se reemplaza para la siguiente elección.Como hay 10 lugares cada lugar se puede llenar de 26 formas diferentes entonceshay 2610 formas diferentes para escribir cadenas de 10 letras.En general si se quieren llenar r lugares con n símbolos diferentes donde el

número de cada símbolo es ilimitado entonces el número de posibilidades es

nr

Example 264 Un byte es un conjunto de ocho posiciones en donde cada posicióno recibe un pulso eléctrico 1 o no lo recibe 0.¿ Cuántos bytes diferentes se puedenformar?

Page 57: Algebra superior i   reyes

6.2. PRINCIPIO DE INCLUSIÓNY EXCLUSIÓN PARADOS Y TRES CONJUNTOS53

Solution 265 Este problema se puede abordar considerando 8 lugares en donde encada lugar se puede llenar con un 0 o un 1. Entonces la respuesta es 28 = 256.

Exercise 266 ¿Cuántas ordenaciones de 3 lugares se pueden hacer con las 5 vo-cales?

Exercise 267 En la clave Morse que se utilizaba para el telégrafo solamente sepodían transmitir dos tipos de señal: un pulso corto que se interpretaba como puntoy un pulso largo que se interpretaba como raya. ¿Cuántas letras diferentes de 3pulsos se pueden formar? ¿Cuántos pulsos mínimo se necesitan para tener unasecuencia diferente para cada una de las 26 letras del alfabeto?

Exercise 268 ¿Cuántas funciones hay entre los conjuntos A = {a1, a2, . . . , am} yB = {b1, b2, . . . , bn}?

Sin reemplazo Suponer ahora que el número de símbolos es limitado, es decirlos símbolos no se van reemplazando. Por ejemplo que solamente se pueden utilizarlas letras de la palabra ladrillo. ¿De cuántas formas se pueden ordenar las letrasde esta palabra? Esta palabra tiene 8 lugares. Si todas las letras fueran diferenteshabría 8! maneras de ordenarlas. Como hay 3 eles entonces hay que dividir 8! por3!. Hay

8!

3!= 6720

formas de ordenar las letras de la palabra ladrillo.Cuando hay que llenar n lugares con s símbolos diferentes repetidos n1, n2, . . . , ns

veces entonces hay n! permutaciones que hay que dividir por el producto n1!×n2!×. . .× ns! entonces

n!

n1!× n2!× . . .× ns!

Example 269 Un maestro de educación física tiene que elegir 4 equipos de 9 ju-gadores cada uno de un grupo de 36 alumnos. ¿De cuántas formas se pueden elegirlos cuatro equipos?

Solution 270 Este problema se puede imaginar que a cada persona del grupo se leva a asignar un símbolo del 1 al 4. Cada uno de los 4 símbolos se repite 9 veces.Hay 36 lugares por lo tanto hay

36!

9!9!9!9!

formas diferentes de hacer los equipos.Este problema también se puede pensar como una aplicación del producto de com-binaciones. En la siguiente sección se abordará de esa manera.

Exercise 271 ¿Cuál es el coeficiente de x2y3z4 en el desarrollo (x+ y + z)9? ¿Có-mo es en general el coeficiente de un sumando de (x1 + x2 + . . .+ xs)

n?

Exercise 272 En un grupo de 25 alumnos se van a hacer 5 equipos de 5 personaspara un laboratorio. ¿De cuántas formas se pueden hacer los equipos?

Exercise 273 ¿Cuántas ordenaciones hay de las letras de la palabra Parangaricu-tirimícuaro?

Page 58: Algebra superior i   reyes

54 CAPÍTULO 6. CONTEO

Combinaciones con repetición o Distribuciones

Suponer que se van a colocar n+ 1 unos y r ceros en línea con la condición deque debe haber 1 uno en cada uno de los extremos de la línea. ¿De cuántas manerasse pueden ordenar los restantes unos y ceros?En primer lugar hay (n+ 1) + r − 2 lugares posibles porque dos de los lugares

quedan fijos con un 1. Si los objetos fueran diferentes habría

((n+ 1) + r − 2)! = (n+ r − 1)!ordenaciones. Como de esos hay n− 1 unos iguales y r ceros iguales entonces hay

(n+ r − 1)!(n− 1)!r!

posibles formas de ordenar (n+ 1) unos y r ceros.Otra forma de abordar el problema es contar el número de formas que se pueden

escoger de cuatro símbolos A,B,C,D, tres de ellos, sin importas el orden. Porejemplo, es lo mismo la terna A;A;B que la terna A;B;A que B;A;A. Una formasería enumerar todas las posibilidades.

A,A,A A,A,B A,A,C A,A,D aparece AAA,B,B A,B,C A,B,D aparece ABA,C,C A,C,D A,D,D aparece AC o ADB,B,B B,B,C B,B,D aparece BBB,C,C B,C,D B,D,D aparece BCC,C,C C,C,D C,D,D aparece CC o CDD,D,D aparece DD

por lo tanto hay 20 combinaciones con repetición de cuatro elementos tomados detres en tres.Otra forma de contar las combinaciones con repetición de 4 objetos tomados en

grupos de 3 es imaginar a los cuatro objetos como categorías separadas con algúnmarcador, por ejemplo el marcador | . Por ejemplo, la distribucióncategoría 1 categoría 2 categoría 3 categoría 4

| xx | | x 2 de categoría 2 y 1 cat 4

En este caso hay un máximo de 4 categorías y 3 marcadores. Como solamente sevan a tomar tres objetos de las cuatro categorías entonces se van a llenar 6 lugarescon dos objetos diferentes, un elemento de la categoría o un marcador, es decir

6× 5× 43!

=

µ6

3

¶=

µ4 + 3− 1

3

¶= 20

Definition 274 Una combinación con repetición de un conjunto X = {x1, . . . , xn}den elementos diferentes tomados de r en r es una selección {xi1 , . . . , xir} de r ele-mentos, sin importar el orden, tal que cada xij se puede repetir r veces y xij ∈ X.El número de combinaciones con repetición de n elementos tomados en grupos der es µ

n+ r − 1r

¶=

(n+ r − 1)![(n+ r − 1)− r]!r!

=(n+ r − 1)!(n− 1)!r!

=(n+ r − 1)!

(n− 1)! [(n+ r − 1)− (n− 1)]! =µn+ r − 1n− 1

¶Example 275 A un lugar donde venden hamburguesas, hot dogs y pizzas llegansiete personas.¿De cuántas formas diferentes pueden ordenar?

Page 59: Algebra superior i   reyes

6.2. PRINCIPIO DE INCLUSIÓNY EXCLUSIÓN PARADOS Y TRES CONJUNTOS55

Solution 276 Hay tres categorías diferentes para llenar 7 lugares. Entonces hay3 + 7− 1 lugares que se van a llenar en grupos de r = 7 y n = 2 elementos iguales,µ

3 + 7− 17

¶=

9!

7!2!

Example 277 Una persona va a tener 20 invitados y les va a ofrecer 4 bebidasdiferentes. ¿De cuántas formas pueden distribuirse las bebidas?

Solution 278 En este caso hay n = 4 categorías que se van a distribuir en gruposde r = 20 entonces hayµ

4 + 20− 120

¶=

23!

20!3!=23× 22× 21

3× 2 = 1771

Example 279 ¿Cuántas soluciones enteras no negativas tiene la ecuación x1 +x2 + x3 + x4 = 25?

Solution 280 En este problema se puede pensar que cada variable xi es una cate-goría entonces n = 4 y se van distribuir en grupos de r = 25. Entonces hayµ

4 + 25− 125

¶=28× 27× 26

3× 2 = 3276

soluciones.

Example 281 ¿Cuántas soluciones enteras no negativas tiene la ecuación x1 +x2 + x3 + x4 = 25 con la restricción de que xi ≥ 2?Solution 282 En cada categoría van dos objetos al menos, entonces nos restanr = 25− 8 = 17 objetos que distribuir en n = 4 categorías. Entonces hayµ

4 + 17− 117

¶=20× 19× 18

2× 3 = 540

soluciones enteras mayores o iguales a 2.

Example 283 ¿Cuántás soluciones enteras no negativas hay para la desigualdadx1 + x2 + . . .+ x6 < 10?

Solution 284 Para abordar el problema considerar una variable extra x7 > 0 ytranformar el problema a resolver x1 + x2 + . . . + x6 + x7 = 10 con xi ≥ 0 para1 ≤ i ≤ 6, x7 > 0. Este último problema es equivalente a encontrar el número desoluciones enteras no negativas de

y1 + y2 + . . .+ y6 + y7 = 9

con yi ≥ 0 al hacer xi = yi,para 1 ≤ i ≤ 6, y y7 = x7 − 1. La solución es¡7+9−19

¢=

5005.

Exercise 285 ¿De cuántas formas se pueden distribuir 10 canicas idénticas en 6cajas diferentes?

Exercise 286 ¿De cuántas formas se pueden distribuir 10 monedas idénticas entre5 niños?

Exercise 287 ¿De cuántas formas se pueden distribuir 10 monedas idénticas entre5 niños si cada niño obtriene al menos una moneda?

Page 60: Algebra superior i   reyes

56 CAPÍTULO 6. CONTEO

Exercise 288 ¿De cuántas formas se pueden distribuir 10 monedas idénticas entre5 niños si el mayor obtiene al menos dos monedas?

Exercise 289 ¿De cuántas formas se pueden distribuir 15 monedas idénticas entre5 niños si al más pequeño solamente le tocarán una o dos?

Exercise 290 ¿De cuántas formas se pueden seleccionar 20 monedas de cuatrocontenedores que tienen monedas con monedas de $1, $2, $5 $10? Cada contenedortiene monedas de la misma clase.

Exercise 291 Calcular el número de soluciones enteras de x1 + x2+ x3+ x4 = 32dondea) xi ≥ 0, 1 ≤ i ≤ 4 b) xi > 0, 1 ≤ i ≤ 4c) x1, x2 ≥ 5, x3, x4 ≥ 7 d) xi ≥ −2, 1 ≤i ≤ 4Exercise 292 Calcular el número de soluciones enteras no negativas de x1+ x2+x3 + x4 + x5 < 40 dondea) xi ≥ 0,para 1 ≤ i ≤ 5, b) xi ≥ −3,para1 ≤ i ≤ 5.Exercise 293 ¿Cuántos términos diferentes, de la forma an1bn2 hay en el desar-rollo de (a + b)nconsiderando que dos términos diferentes corresponden a una de-scomposición de n en dos sumandos, n1 + n2 = n con 0 ≤ ni ≤ n, i = 1, 2?

Exercise 294 ¿Cuantos términos diferentes hay en el desarrollo de (a+ b+ c)10?

6.2.2. Integración de los principios de suma y producto

Es claro que hay problemas que requieren del uso de una mezcla de los principiosde suma y producto. En esta sección se van a resolver ejemplos con esta mezcla deprincipios.

Example 295 Dado un conjunto de n elementos ¿cuántos subconjuntos se puedenformar?

Solution 296 El número de subconjuntos con 1 elemento se calcula como¡n1

¢, el

número de subconjuntos de 2 elementos es¡n2

¢, , el número de subconjuntos de k

elementos es¡nk

¢. El número de subconjuntos de 0 elementos es

¡n0

¢. Entonces hay

nXi=0

µn

i

¶= (1 + 1)n = 2n

Example 297 Un estudiante en un examen tiene que responder 7 de las 10 pre-guntas, pero deben ser al menos 3 de las primeras 5.

Solution 298 Hay tres casos a considerar.1) El primer caso es que el estudiante responda exactamente 3 preguntas de lasprimeras 5 y 4 de las restantes 5. En este caso hayµ

5

3

¶µ5

4

¶=5× 42

× 51= 50

formas posibles de contestar el examen.2) El segundo caso es que responda 4 preguntas de las primeras 5 y 3 de las restantes.µ

5

4

¶µ5

3

¶= 50

Page 61: Algebra superior i   reyes

6.2. PRINCIPIO DE INCLUSIÓNY EXCLUSIÓN PARADOS Y TRES CONJUNTOS57

3) Finalmente, la última posibilidad es que responda las primeras 5 preguntas yescoja 2 de las 5 restantes µ

5

5

¶µ5

2

¶=5× 4× 32× 3 = 10

El número total de posibilidades es la suma de los tres casos

50 + 50 + 10 = 110

Example 299 ¿De cuántas formas se pueden elegir 5 cartas de un mazo de 52 detal forma que haya al menos un corazón rojo ♥?

Solution 300 Hay dos formas de resolver este problema. La primera es contandolas formas que hay para elegir 1 corazón rojo, más las formas que hay para elegir2 corazones rojos, más · · · , sumar hasta las formas de elegir que las 5 cartas seancorazón rojo. Las cartas que quedan quitando los 13 corazones rojos son 39. Entoncesµ

13

1

¶µ39

4

¶+

µ13

2

¶µ39

3

¶+

µ13

3

¶µ39

2

¶+

µ13

4

¶µ39

1

¶+

µ13

5

¶µ39

0

¶son todas las formas posibles de elegir al menos una que sea un corazón rojo, da untotal de 2, 023, 203 posibilidades.La otra forma de resolver el problema es al total de posibilidades de elegir 5 cartasdel mazo de 52 restarle el número de posibilidades de que no contenga un corazónrojo. µ

52

5

¶−µ39

5

¶= 2, 023, 203

Example 301 Determinar el número de formas como se puede descomponer unnúmero entero positivo n como suma de enteros en donde el orden es importante.Por ejemplo el número 3 se puede escribir como: 3, 1 + 2, 2 + 1, 1 + 1 + 1.Hay 4formas como se puede descomponer un número. Para contar sin enumerar todas lasposibilidades empecemos con n = 6.

Solution 302 El primer caso es con un sumando 6 y para ese nada mas hay unaforma de descomponerlo.Para dos sumandos n1 + n2 = 6 con n1, n2 > 0 . Al reescribir esta condición conlas variables x1, x2 de tal forma que n1 = x1 + 1, n2 = x2 + 1 entonces

n1 + n2 = x1 + 1 + x2 + 1 = 6

x1 + x2 = 6− 2 = 4x1 + x2 = 4, x1, x2 ≥ 0

Hay µ2 + 4− 1

4

¶=

µ5

4

¶formas de descomponer 6 en dos sumandos.Para tres sumandos µ

3 + 3− 13

¶=

µ5

3

¶Para cuatro sumandos µ

4 + 2− 12

¶=

µ5

2

Page 62: Algebra superior i   reyes

58 CAPÍTULO 6. CONTEO

Para cinco sumandos µ5 + 1− 1

1

¶=

µ5

1

¶Para 6 sumandos solamente hay una forma. Al sumar

1 +

µ5

4

¶+

µ5

3

¶+

µ5

2

¶+

µ5

1

¶+ 1 = 25

es el número de formas como se puede descomponer en sumandos el 6. En generalel número n se puede descomponer en 2n−1 formas como suma de enteros positivos.

Exercise 303 De un examen de 12 preguntas un estudiante debe elegir 8 preguntasal menos 5 de las primeras 7 preguntas ¿de cuántas formas puede hacerlo?

Exercise 304 Para un juego de canasta se juntan dos mazos de 52 cartas y seagregan dos cartas llamadas jokers (juglares). A cada jugador se le dan 13 cartas.¿De cuántas formas se le pueden dar a un jugador las cartas de tal forma quecontenga al menos 5 tréboles ♣?

Exercise 305 En computación se define una cadena c como una sucesión de sím-bolos tomados de un conjunto S de símbolos diferentes. La longitud de una cadenaes el número de elementos de la sucesión. ¿Cuántas cadenas de longitud 5 se puedenformar con 3 símbolos diferentes?

6.2.3. Miscelánea de problemas

Exercise 306 ¿Cuántas ordenaciones diferentes de las letras de la palabra resolverhay?

Exercise 307 ¿De cuántas formas se pueden sentar 6 personas en una mesa cir-cular?

Exercise 308 Diana tiene que elegir 5 revistas de 12 que tiene.¿De cuántas formaspuede hacerlo?

Exercise 309 Un comité de 8 personas será elegido entre 15 hombres y 15 mujeres.¿De cuántas formas se puede hacer la elección?

Exercise 310 En el comité del problema anterior debe haber 4 hombres y 4 mujeres.

Exercise 311 En el comité del problema 4 debe haber un número par de mujeres.

Exercise 312 En el comité del problema 4 debe haber al menos dos hombres.

Exercise 313 Al ordenar la comida en la cafetería se pueden ordenar dos de tressopas y tres de ocho verduras.¿De cuántas formas puede ordenar una persona sucomida?

Exercise 314 Una persona llega a una fiesta y encuentra que hay 20 personas. Sila persona que llega saluda a todos de mano ¿a cuántas personas saluda de mano?

Exercise 315 ¿De cuántas formas se pueden repartir 10 bolas idénticas en cuatrorecipientes diferentes de modo quea) ningún rescipiente quede vacío?b) en el cuarto recipiente haya un número par de bolas?

Page 63: Algebra superior i   reyes

6.2. PRINCIPIO DE INCLUSIÓNY EXCLUSIÓN PARADOS Y TRES CONJUNTOS59

Exercise 316 ¿De cuántas formas es posible recorrer el plano del punto (1, 1) al(8, 9) si cada movimiento es de cualquiera de los siguientes dos tipos

h : (x, y)→ (x+ 1, y)

v : (x, y)→ (x, y + 1)?

Exercise 317 En la fabricación de automóviles pueden aparecer tres tipos de de-fectos mayores y ocho tipos de defectos menores. ¿De cuántas formas se puedenpresentar los defectos?

Exercise 318 ¿Cuántos sumandos diferentes hay en el desarrollo de (a+ b + c +d)12?

Exercise 319 ¿Cuántos sumandos diferentes hay en el desarrollo de (x1 + x2 +. . .+ xn)

m?

Exercise 320 Una relación es un subconjunto de un producto cartesiano A×B, siN(A) = 3 y N(B) = 4 ¿Cuántas relaciones hay en A×B?

Exercise 321 Para el caso en que N(A) = m y N(B) = n ¿cuántas relaciones hayde A en B? ¿Cuántas funciones hay de A en B?

Page 64: Algebra superior i   reyes

60 CAPÍTULO 6. CONTEO

Page 65: Algebra superior i   reyes

Capítulo 7

Los números enteros.

7.1. El anillo de los números enterosUna parte importante del álgebra moderna es el estudio de las estructuras al-

gebraicas. Los números enteros con sus operaciones tienen una estructura llamadaanillo conmutativo con 1.En este momento es importante agrupar y ordenar laspropiedades de las operaciones para utilizarlas.

7.2. Propiedades de las operaciones entre enteros.Para los números enteros Z hay dos operaciones, suma + y producto ×.Las

propiedades son las siguientes:

1. El conjunto de los números enteros es cerrado bajo la operación suma,es decirsi ∀a ∈ Z,∀b ∈ Z entonces a+ b ∈ Z

2. La suma es asociativa, ∀a ∈ Z,∀b ∈ Z,∀c ∈ Z se cumple que a + (b+ c) =(a+ b) + c.

3. Existe un número llamado cero, 0 tal que ∀a ∈ Z, a+ 0 = a

4. Para todo número entero a existe un entero −a llamado el inverso aditivo dea tal que a+ (−a) = 0.

5. La suma es conmutativa, es decir ∀a ∈ Z,∀b ∈ Z se cumple que a+ b = b+ a.

6. El conjunto de los números enteros es cerrado bajo la operación producto, esdecir si ∀a ∈ Z,∀b ∈ Z entonces a× b ∈ Z.

7. El producto es asociativo, ∀a ∈ Z,∀b ∈ Z,∀c ∈ Z se cumple que a× (b× c) =(a× b)× c.

8. Existe un número llamado uno,1 tal que ∀a ∈ Z, a× 1 = a.

9. El producto es conmutativo, es decir ∀a ∈ Z,∀b ∈ Z se cumple que a×b = b×a.10. La suma distribuye al producto, es decir ∀a ∈ Z,∀b ∈ Z,∀c ∈ Z, a× (b+ c) =

a× b+ a× c.

Al igual que para los números naturales se pueden demostrar una serie depropiedades que son utilizadas en la resolución de ecuaciones con números enteros.

Proposition 322 El 0 en los enteros es único.

61

Page 66: Algebra superior i   reyes

62 CAPÍTULO 7. LOS NÚMEROS ENTEROS.

Proposition 323 El 1 en los enteros es único.

Proposition 324 Ley de la cancelación: Si a+ b = c+ b entonces a = c.

Proposition 325 −(−a) = a

Proposition 326 El inverso aditivo es único.

Proposition 327 ∀a ∈ Z , a0 = 0.Proposition 328 (−a)(−b) = ab

Proof.

[ab+ a (−b)] + (−a) (−b) = ab+ [a (−b) + (−a) (−b)]= ab+ [a+ (−a)] (−b)= ab+ 0 (−b)= ab

Por otro lado

[ab+ a (−b)] + (−a) (−b) = a [b+ (−b)] + (−a) (−b)= a0 + (−a)(−b)= 0 + (−a)(−b)= (−a)(−b)

Por transitividadab = (−a)(−b)

Theorem 329 La ley de la cancelación para la multiplicación de enteros es equiv-alente a demostrar que si ab = 0entonces a = 0 ó b = 0.

Proof. Primero probaremos que la ley de la cancelación implica que si ab =0entonces a = 0 ó b = 0.Supongamos que ab = 0. Esto implica que

ab = 0 = a0

como la ley de la cancelación se cumple entonces b = 0.Inversamente, si a 6= 0 y ab = ac entonces ab− ac = 0

a(b− c) = 0

como a 6= 0 entonces b− c = 0, por lo tanto b = c.

Exercise 330 Demuestra las proposiciones enunciadas para los números enteros.

7.3. Divisibilidad.En la antigüedad se medían distancias con cuerdas con nudos. La longitud de

algo era por ejemplo tres nudos. Cuando se tenía un problema en concreto se tratabade medir con el menor número posible de nudos. Si una longitud cabía un númeroentero de veces en otra se podía cambiar de unidad para medir tomando la másgrande y si se tenía que medir parte de una unidad si la longitud era un divisor dela original entonces se podía tomar la parte como nueva unidad para medir. Por estarazón toda la teoría de divisibilidad en los enteros esta relacionada con la geometría.

Page 67: Algebra superior i   reyes

7.3. DIVISIBILIDAD 63

Definition 331 Dados dos números a y b ∈ Z se dice que a divide a b si existeq ∈ Z tal que aq = b.

Notation 332 a divide a b se denota por a | b. También se dice que b es un múltiplode a.

Remark 333 La divisibilidad es una relación binaria sobre Z pero no es de equiv-alencia ya que no es simétrica.

Las propiedades de la relación binaria | son:

1. Si a | b entonces |a| ≤ |b| .2. Si a | b y b | c entonces a | c.3. Si a | b y a | c entonces a | b+ c

4. Si a | b entonces ac | bc.5. Si a | b y b | a entonces a = b o a = −b

Exercise 334 Encuentra todos los divisores de 60. Investiga cuál era la base delsistema de numeración babilonio. Justifica porqué utilizaban esta base pensando enque básicamente era utilizada para medir ángulos y longitudes.

Exercise 335 Demuestra las propiedades para la relación binaria | .

Exercise 336 Da un ejemplo donde a | bc y a - b y a - c.

7.3.1. Algoritmo de la división

Theorem 337 Dados dos números enteros a y b, b 6= 0, existen números q, r ∈ Ztales que

a = bq + r

con 0 ≤ r < |b| .

Proof. Dados a, b ∈ Z,sea S = {s ∈ N |s = a− bq} . El conjunto S es un sub-conjunto de N. Además S 6= ∅ porque como b 6= 0 entonces |b| ≥ 1. En este casohay dos posibilidades:(i)si b ≥ 1 entonces b |a| ≥ |a|

a− b(− |a|) = a+ b |a| ≥ a+ |a| ≥ 0

De donde a− b(− |a|) ∈ S.(ii) Si b ≤ −1 entonces −b ≥ 1. De donde

|a| (−b) ≥ |a|−b |a| ≥ |a|

Por lo tantoa− b |a| ≥ a+ |a| ≥ 0

de donde a− b |a| ∈ S.De estas dos posibilidades se concluye que S 6= ∅. Por el principio del buen orden

S contiene un mínimo. Sea r ∈ S el mínimo de S. Como r ∈ S entonces r = a− bqpara alguna q ∈ Z y r ≥ 0. Falta demostrar que r < |b| .Como b 6= 0, |b| ≥ 1. Otra vez hay dos posibilidades

Page 68: Algebra superior i   reyes

64 CAPÍTULO 7. LOS NÚMEROS ENTEROS.

(i) Si b > 0 entonces b ≥ 1.De aquí se deduce quea− b(q + 1) = a− bq − b = r − b < r

Por lo tanto a− b(q + 1) /∈ S porque r es el mínimo en S. Pero S contiene a todoslos enteros positivos de la forma a − bx. Por lo tanto a − b(q + 1) es negativo. Deaqui se deduce que

r = a− bq

= a− bq − b+ b

= a− b(q + 1) + b

< b = |b|∴ r < |b|

(ii) Si b < 0 entonces b ≤ −1.a− b(q − 1) = a− bq + b = r + b < r

De la misma forma que antes, de aqui se deduce que a − b(q − 1) /∈ S.y que a −b(q − 1) < 0.Por tanto

r = a− bq

= a− bq + b− b

= a− b(q − 1)− b

= a− b(q − 1) + |b|< |b|

r < |b|De ambos caso se deduce que r < |b| .Ahora se demostrará que q y r son únicos. Supongamos que existen q0 y r0tales

que

a = bq0 + r0

= bq + r

con 0 ≤ r0 < |b| y 0 ≤ r < |b| . De esta igualdad se deduce quebq − bq0 = r0 − r

b(q − q0) = r0 − r (7.1)

Por lo tanto |b| | |r0 − r| .Como 0 ≤ r < |b| entonces al multiplicar por −1 esta desigualdad queda

− |b| < −r ≤ 0Al sumar esta última desigualdad y 0 ≤ r0 < |b| se obtiene

− |b| < r0 − r < |b|De donde

0 ≤ |r0 − r| < |b|Sustituyendo |r0 − r| por |b| |q − q0| se obtiene

|b| |q − q0| < |b|Por lo tanto

0 ≤ |q − q0| < 1Como q y q0 son números enteros entonces q − q0 = 0.De donde q = q0 y finalmenter = r0.

Page 69: Algebra superior i   reyes

7.3. DIVISIBILIDAD 65

Exercise 338 Encuentra q y r para 57 y 25.Expresa 57 como 25q + r.

Exercise 339 Si a < b ¿cuáles son los valores de q y r en a = bq + r, 0 ≤ r < |b|?

Exercise 340 A los divisores de 1 en Z se les llama unidades. Demuestra que lasúnicas unidades en Z son ±1.

Definition 341 Dados dos números enteros a y b se dice que d es el máximo comúndivisor (m.c.d.) de a y b si(i) d > 0, d | a y d | b.(ii) Si existe d0 tal que d0 | a y d0 | b entonces d0 | d.

Notation 342 Si d es el m.c.d. de a y b, se escribe d = (a, b).

Lemma 343 Si d = (b, r) entonces d = (a, b),donde a = bq + r.

Proof. Si d = (b, r) entonces existen s1y s2 ∈ Z tales que ds1 = b y ds2 = r.Sustituyendo en la igualdad

a = bq + r

a = ds1q + ds2

= d(s1q + s2)

De donde d divide a a. Por lo tanto, como ddivide a b si d0 = (a, b) entonces d | d0,porque d0es el máximo.Análogamente, como d0 | a y d0 | b entonces d0 | r. Como d = (b, r) entonces

d0 | d. De ambas conclusiones se deduce que d = d0.

7.3.2. Algoritmo de Euclides

Theorem 344 Algoritmo de Euclides. Dados dos números enteros a y b, rn+1 elúltimo residuo diferente de 0 en el proceso

a = bq + r, 0 ≤ r < |b|b = rq1 + r1 0 ≤ r1 < r

r = r1q2 + r2 0 ≤ r2 < r1

r1 = r2q3 + r3 0 ≤ r3 < r2

· · ·rn−1 = rnqn+1 + rn+1 0 ≤ rn+1 < rn

rn = rn+1qn+2

es el m.c.d. de a y b.

Proof. Comorn = rn+1qn+2

entonces (rn, rn+1) = rn+1.Por el lema

(rn, rn+1) = (rn, rn−1)

Si continuamos aplicando el lema

rn = (rn, rn+1) = (rn, rn−1) = . . . = (b, r) = (a, b)

Page 70: Algebra superior i   reyes

66 CAPÍTULO 7. LOS NÚMEROS ENTEROS.

Remark 345 Si d = (a, b) entonces d > 0.

Definition 346 Dados dos números enteros a y b, a una expresión de la formama+ nb, con m y n enteros, se llama combinación lineal de a y b.

Notation 347 Si r = ma+ nb entonces se denotará por r es c. . de a y b.

Lemma 348 En el algoritmo de la división de a y b,donde

a = bq + r 0 ≤ r < |b|r el residuo es una combinación lineal de a y b.

Proof. La demostración es trivial ya que r = a+ b (−q) .Lemma 349 Si rn+1 es c. . de rn y rn−1 y rn es c. .de rn−1 y rn−2 entonces rn+1es c. . de rn−1 y rn−2.

Proof. Como rn−1 = rnqn+1 + rn+1 entonces rn+1 es combinación lineal de rny rn−1.

rn+1 = rn−1 + rn (−qn+1)Análogamente rn es combinación lineal de rn−1y rn−2.

rn = rn−2 + rn−1 (−qn)Sustituyendo esta última igualdad en la anterior

rn+1 = rn−1 + (rn−2 + rn−1 (−qn)) (−qn+1)= rn−1 (1 + qnqn+1) + rn−2 (−qn+1)

De donde rn es combinación lineal de rn−1 y rn−2.

Theorem 350 Si d = (a, b) entonces d es la mínima combinación lineal de a y b.

Proof. Utilizando sucesivamente el último lema se concluye que rn+1 = d =(a, b) es combinación lineal de a y b.Para probar que d es la mínima combinación lineal de a y b suponer que existe

otra combinación lineal de a y b.

d0 = ma+ nb

Por la definición de d, d | a y d | b. Entonces existen q1 y q2 tales que dq1 = a ydq2 = b. Sustituyendo

d0 = mdq1 + ndq2

= d (mq1 + nq2)

Por tanto d | d0.De donde 0 ≤ d ≤ |d0| .Exercise 351 Encuentra el m.c.d. de 315 y 28. Exprésalo como combinación linealde los números.

Exercise 352 Demuestra que si (a, c) = 1, a | m y c | m entonces ac | m.

Exercise 353 Demuestra que si a > 0 entonces (ab, ac) = a(b, c).

Definition 354 Dos números enteros a y b son primos relativos si (a, b) = 1.

Page 71: Algebra superior i   reyes

7.3. DIVISIBILIDAD 67

Theorem 355 Si d = (a, b) y d = ma+ nb entonces (m,n) = 1.

Proof. Como d = (a, b) , d | a y d | b. Entonces existen q1 y q2 tales que dq1 = ay dq2 = b. Sustituyendo

d = mdq1 + ndq2

= d(mq1 + nq2)

1 = mq1 + nq2

Como 1 es el mínimo entero positivo entonces (m,n) = 1.

Exercise 356 Demuestra que si (a,m) = (b,m) = 1 entonces (ab,m) = 1

Exercise 357 Demuestra que si (a, c) = d, a | b y c | b entonces ac | bd.

Definition 358 Dados dos números enteros a y b, a un número m > 0 se le llamamínimo común múltiplo(m.c.m.) de a y b si(i) a | m y b | m.(ii) si a | m0 y b | m0 entonces m | m0.

Notation 359 Al m.c.m. m de a y b se le denota por m = [a, b].

Theorem 360 Si (a, b) = 1 entonces [a, b] = ab.

Proof. Sea m = [a, b]. Como ab es un múltiplo común de a y de b, m | ab. Portanto m ≤ ab.

Si (a, b) = 1 entonces existen m y n ∈ Z tales que

1 = ra+ sb.

Comom = [a, b] entonces existen q1 y q2 tales que aq1 = m y bq2 = m. Al multiplicarpor m la igualdad y sustituirla de forma cruzada

m = mra+msb

= bq2ra+ aq1sb

Agrupando y factorizando

m = ab(rq2 + sq1)

Por tanto ab | m. De donde ab ≤ m.De ambas conclusiones se obtiene quem = [a, b].

Theorem 361 Si a, b ∈ Z entonces [a, b](a, b) = ab.

Remark 362 Este último teorema nos permite calcular el m.c.m. de dos númerosutilizando el algoritmo de Euclides.

Exercise 363 Calcular el m.c.m. dea) 365 y 280.b) 1001 y 144..

Page 72: Algebra superior i   reyes

68 CAPÍTULO 7. LOS NÚMEROS ENTEROS.

7.4. Números primos

.

Definition 364 Un número entero positivo p 6= 1 es primo si sus únicos divisoresson ±1 y ±p.

Theorem 365 Si p es primo y p | ab entonces p | a ó p | b.

Proof. Suponer que p | ab y que p - a. Se probará que p | b.Como p divide ab entonces existe q ∈ Z tal que pq = ab. Como p - a y p es

primo entonces (a, p) = 1; ya que si d = (a, p) entonces d | a y d | p pero los únicosdivisores positivos de p son 1 y p,pero p - a.Por tanto d = 1.Como (a, p) = 1 entonces existen r, s ∈ Z tales que

1 = ar + ps

Multiplicando por b esta igualdad

b = abr + ps

Sustituyendo ab = pq en la últim igualdad

b = pqr + ps

= p(qr + s)

De donde se concluye que p | b.

Corollary 366 Si c | ab y (c, a) = 1 entonces c | b.

Proposition 367 Si p es primo entonces√p no es racional.

Proof. Suponer que√p es racional. Esto quiere decir que existen a, b ∈ Z con

(a, b) = 1 y tales que√p =

a

b

al elevar al cuadrado

p =a2

b2

pb2 = a2

Esta última igualdad implica que p | a2. Por el teorema p | a. Esto implica quepq = a. Sustituyendo en la última igualdad

pb2 = (pq)2 = p2q2

Al simplificar

b2 = pq2

De donde p | b2.Otra vez por el teorema p | b. Esto es una contradicción porque sehabía supuesto que (a, b) = 1.Por lo tanto

√p no es racional.

Page 73: Algebra superior i   reyes

7.5. TEOREMA DE FACTORIZACIÓN ÚNICA 69

7.5. Teorema de factorización únicaTheorem 368 Fundamental de la aritmética o de factorización única. Todo númeroentero a se puede descomponer de forma única, salvo el orden, como producto denúmeros primos.

Proof. Si a es primo entonces ya no hay nada que demostrar. Si a no es primoentonces

a = bc

donde b, c < a. Se utilizará el principio de inducción en su segunda forma.(incompleta)

Theorem 369 Todo número compuesto a > 0 es divisible por un primo p ≤ √a.

Proof. Como a es compuesto entonces a = bc con b > 1 y c > 1. Es posiblesuponer que b ≤ c por la tricotomía.Supongamos que b >

√a.

Como c ≥ b entonces c ≥ b >√a. Por lo tanto c >

√a.

De c >√a y b >

√a se tiene que bc >

√a√a = a,lo que contradice que a = bc.

Por lo tanto b ≤ √a

Exercise 370 Encontrar la descomposición en primos de los siguientes enteros:(i) 1001(ii) −847(iii) 923(iv) 60(v) Describir un procedimiento para encontrar el divisor primo más grande cuandonos dan un número entero.

Exercise 371 Dados los números enteros positivos se define la media geométricade a y b al número

√ab. En la figura demuestra que el segmento PQ tiene longitud√

ab

El segmento AB. es el diámetro de la circunferencia. El punto P es el puntosobre la circunferenica ,|AQ| = a, |QB| = b

Demostrar que la media aritmética de a y b,a+ b

2es mayor o igual que su media

geométrica.

Page 74: Algebra superior i   reyes

70 CAPÍTULO 7. LOS NÚMEROS ENTEROS.

Page 75: Algebra superior i   reyes

Capítulo 8

Congruencias

8.1. Definición

Definition 372 Se define la relación binaria en Z, dos números enteros son con-gruentes módulo m, m > 0 y se escribe a ≡ b mod(m) si m | b− a.

Theorem 373 La relación binaria sobre Z,≡ mod(m) es una relación de equiva-lencia.

Proof. La relación es reflexiva porque a ≡ a mod(m) porque m0 = a− a = 0.

La relación es simétrica porque si m | b−a entonces existe q tal que mq = b−a.De donde m(−q) = a− b y por tanto b ≡ a mod(m).

La relación es transitiva ya que si a ≡ bmod(m) y b ≡ cmod(m) entonces existenq1 y q2 tales que mq1 = b− a y mq2 = c− b. Al sumar ambas igualdades

mq1 +mq2 = (b− a) + (c− b)

m(q1 − q2) = c− a

Por lo tanto a ≡ cmod(m).

Como ≡ mod(m) satisface las tres propiedades que definen a una relación deequivalencia entonces es una relación de equivalencia.Como ≡ mod(m) es una relación de equivalencia sobre Z entonces parte en clases

ajenas a Z. Para tener una idea de como son las clases de equivalencia respecto aesta relación hay que considerar que al dividir un número entero por m ∈ Z esposible obtener m residuos diferentes: 0, 1, . . . , (m− 1).

Example 374 Considerar m = 4,los residuos posibles son 0, 1, 2, 3. Al tomar unnúmero entero, por ejemplo 97 y dividirlo por 4 se obtiene

97 = 4(24) + 1

Esto implica que 97 ≡ 1mod(4).

Proposition 375 Dos números enteros a, b son congruentes mod(m) si y sólo sitienen el mismo residuo al dividirse por m. i.e.

a = mq1 + r 0 ≤ r < m

b = mq2 + r 0 ≤ r < m

71

Page 76: Algebra superior i   reyes

72 CAPÍTULO 8. CONGRUENCIAS

Proof. Primero se mostrará que si son congruentes entonces dejan el mismoresiduo. a ≡ bmod(m). Por el algoritmo de la división existe números enterosq1, r1, q2, r2 tales que

a = mq1 + r1 0 ≤ r1 < m

b = mq2 + r2 0 ≤ r2 < m

Esto implica que

a ≡ r1mod(m)

b ≡ r2mod(m)

como a ≡ b mod(m),por transitividad de la relación de equivalencia

r1 ≡ r2mod(m)

Como 0 ≤ r1, r2 < m esto implica que r1 − r2 = m0 = 0, .de donde r1 = r2.Inversamente, ahora suponer que a y bdejan el mismo residuo r al dividirse por

m. Por lo tanto

a ≡ rmod(m)

b ≡ rmod(m)

Por transitividada ≡ bmod(m)

Remark 376 Una clase de equivalencia respecto a ≡ mod(m) esta formada portodos los enteros que dejan el mismo residuo. Definir

0 = {z ∈ Z | z = mq para alguna q ∈ Z}1 = {z ∈ Z | z = mq + 1 para alguna q ∈ Z}· · ·

m− 1 = {z ∈ Z | z = mq + (m− 1) para alguna q ∈ Z}Definition 377 Se define Zn =

©0, 1, . . . , n− 1ª como el conjunto de clases de

equivalencia módulo n.

Example 378 Param = 4 las clases de equivalencia son 0 = {múltiplos de 4} , 1, 2, 3.Lasoperaciones entre clases de equivalencia queda definida en las siguientes dos tablas

+ 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 3 0 1 2

× 1 2 31 1 2 32 2 0 23 3 2 1

Exercise 379 Construir las tablas de las operaciones de Z5,Z9.

Exercise 380 Demostrar que Zn con las propiedades de + y × definidas para lasclases de equivalencia tiene las mismas propiedades que los números enteros. Esdecir (Zn,+,×) es un anillo conmutativo con 1.Exercise 381 Para Z6 encuentra los divisores propios de 0.

Page 77: Algebra superior i   reyes

8.2. PROPIEDADES 73

8.2. PropiedadesTheorem 382 La relación de equivalencia ≡mod(m) tiene las siguientes propiedades(i) a ≡ b mod(m) ⇒ a+ c ≡ b+ cmod(m)∀c ∈ Z.(ii) a ≡ bmod(m)⇒ ac ≡ bc mod(m)∀c ∈ Z(iii) a ≡ bmod(m) y c ≡ dmod(m)⇒ a+ c ≡ b+ dmod(m)(iv) a ≡ bmod(m) y c ≡ dmod(m)⇒ ac ≡ bdmod(m)(v) a ≡ b mod(m) ⇒ an ≡ bnmod(m)

Proof. Las propiedades (i) y (ii) son inmediatas de la definición de ≡ mod(m)ya que si m | b− a entonces m | (b+ c)− (a+ c) y m | bc− ac.La propiedad (iii) es verdadera porque si m | b− a y m | d− c entonces existen

q1 y q2 tales que

mq1 = b− a

mq2 = d− c

Sumando ambas igualdades, factorizando y agrupando

m(q1 − q2) = (b+ d)− (a+ c)

Para demostrar la propiedad (iv), como m | b− a y m | d− c entonces

mq1 = b− a

mq2 = d− c

Ahora bien

bd− ac = (b− a)(d− c) + bc+ ad− 2ac= (b− a)(d− c) + c(b− a) + a(d− c)

= mq1mq2 + cmq1 + amq2

= m(mq1q2 + cq1 + aq2)

Por lo tantom | bd− ac

De dondeac ≡ bdmod(m)

Proposition 383 La congruencia ax ≡ 1mod(m) tiene solución si y sólo si (a,m) =1.

Proof. Si la congruencia tiene solución entonces m | 1 − ax. Es decir, existe qtal que

mq = 1− ax

De dondemq + ax = 1

Por lo tanto (a,m) = 1.Si (a,m) = 1 entonces

1 = mr + as

de dondemr = 1− as

Por lo tanto as ≡ 1mod(m).

Page 78: Algebra superior i   reyes

74 CAPÍTULO 8. CONGRUENCIAS

Corollary 384 Si p es primo entonces en Zp todos los elementos tienen inversomultiplicativo.

Corollary 385 La congruencia ax ≡ bmod(m) tiene solución si y sólo si (a,m) =1.

Exercise 386 En Z6 encontrar los elementos que tienen inverso multiplicativo.

8.3. Teorema chino del residuoEl teorema chino del residuo es un teorema que se originó en las conversiones

de un calendario lunar a uno solar. Este problema se resolvió en diferentes culturaspero en vista de que los chinos manejan hasta la época actual ambos calendariosentonces se le dió el nombre.Suponer que se quiere encontrar un valor de x tal que

x ≡ b1mod(m1)

x ≡ b2mod(m2)

· · ·x ≡ bsmod(ms)

La respuesta es que es posible encontrar una x que satisfaga todas las relaciones simi y mj son primos relativos ∀i 6= j tales que i, j ∈ {1, 2, . . . , s} .Theorem 387 El sistema de congruencias

x ≡ b1mod(m1)

x ≡ b2mod(m2)

· · ·x ≡ bsmod(ms)

tiene solución única congruente mod(m1m2 · · ·ms) si (mi,mj) = 1 ∀i 6= j tales quei, j ∈ {1, 2, . . . , s} .Proof. Se define Mt como m1m2 . . .ms = Mtmt ∀t ∈ {1, 2, . . . , s} . Sea M 0

t

tal que MtM0t ≡ 1mod(mt). Entonces MtM

0tbt ≡ btmod(mt). El número x0 =

M1M01b1+. . .+MsM

0sbs es congruente con bi mod(mi). Sea y ≡ x0mod(m1m2 · · ·ms).

Exercise 388 Resolver el siguiente sistema de congruencias

x ≡ 2(mod3)

x ≡ 3(mod5)

x ≡ 2(mod7)

Exercise 389 Un problema de calendarios. Un mes lunar tiene aproximadamente29,5 días. Si se tiene luna llena un lunes al atardecer ¿ Cuántos meses después setendrá luna llena un miércoles a la misma hora aproximadamente?

Exercise 390 Demostrar que si p es primo y a, b son enteros entonces (a+ b)p ≡ap + bpmod(p)

Exercise 391 Generalizar el resultado anterior a n sumandos diferentes. Final-mente hacer a1 = a2 = · · · = an = 1 y enunciar el teorema. Este último teorema,ligeramente modificado, se llama el pequeño teorema de Fermat.

Page 79: Algebra superior i   reyes

Capítulo 9

Bibliografía

Beaumont, Ross A. and Pierce, Richard S. The Algebraic Foundations ofMathematics. Addison-Wesley Publishing Company, Inc. 1963 USA.

Birkhoff, Garrett; Mac Lane, Saunders. A survey of Modern Algebra. FourthEdition. Macmillan Publishing Co Inc. New York. Collier Macmillan Publish-ers. 1977 USA.

Cohn, P.M. Algebra, Volume 1 Second Edition. John Wiley & Sons.1995.

Cohen, Arjeh M.; Cuypers, Hans; Sterk, Hans. Algebra Interactive! LearningAlgebra in an exciting way. Springer Verlag Berlin Heidelberg, 1999.

Epp, Susan. Discrete Mathematics with Applications. Second Edition. PWS.ITP An International Thomson Publishing Company 1995.

Fletcher, Peter; Hoyle, Hughes; Patty, Wayne. Foundations of Discrete Math-ematics. PWS-Kent Publishing Company 1991.

Gardner, Martin. A Gardner´s Workout. Training the Mind and Entertainingthe Spirit. AK Peters Ltd. 2001. Canada.

Grimaldi, Ralph P., Matemáticas discretas y combinatoria. Editorial AddisonWesley Longman, Tercera Edición. México 1998.

Liu,Chung Laung. Elements of Discrete Mathematics.Second Edition. Mc GrawHill International Editions.1985.

Niven, Iván; Zuckerman, Herbert S., Montgomery, Hugh L. An Introductionto the Theory of Numbers.John Wiley & Sons Fifth Edition. USA 1991.

Vinográdov, Iván Matvéevich. Fundamentos de la Teoría de Números. Edito-rial Mir Moscú. 1977.

75

Page 80: Algebra superior i   reyes

Índice alfabético

Algoritmo de EuclidesEnteros, 69

axiomas, 3, 4axiomas de Peano, 11

buen ordennaturales, 20

caminotrayectoria, 35, 44

camino simple, 35cardinalidad

conjunto, 17ciclo

camino cerrado, 35clase de equivalencia

relacion de equivalencia, 28combinacion lineal

enteros, 70complemento de un conjunto, 8complemento de una relacin, 43composición de funciones, 23composición de relaciones, 42congruencia

enteros, 75conjetura, 4conjunto, 4conjunto universal

universo, 8conjunto vacío, 8conjuntos, 7corolario, 4

definición inductiva, 17demostración, 3demostración por inducción

por inducción, 12Descartes, 3Diagrama de Hasse

Hasse, 34divisibilidad, 66dominio de una función, 21

elemento, 7enteros modulo n, 76

Euclides, 3

función, 21función inversa, 25función inyectiva

uno a unobiunívoca, 22

función suprayectivasobre, 22

Fundamental de la aritmeticaFactorizacion unicaenteros, 73

Gráfica, 33

igualdad de conjuntos, 7imagen de una función, 21intersección de conjuntos, 8inversa de una relación

inversión, 42inverso del inverso

enteros, 66

lazo, 35lema, 4ley de la cancelacion

enteros, 66Leyes de De Morgan, 9leyes de los signos

enteros, 66

método axiomático, 3Matriz de adyacencia, 39matriz de alcance, 44maximo comun divisor, 69minimo comun multiplo

enteros, 71

número primo, 72números enteros, 65números naturales, 11

Operaciones entre relaciones, 41orden

naturales, 19

76

Page 81: Algebra superior i   reyes

ÍNDICE ALFABÉTICO 77

Pitágoras, 3potencia de una relación, 42primos relativos

enteros, 70Principio de inducción

Axiomas de Peano, 11producto cartesiano, 9Propiedades de la congruencia, 77

relación, 21Relación binaria, 27relación de equivalencia, 27

sistema de congruenciasteorema chino del residuo, 78

subconjunto, 7suma booleana de relaciones, 43

Tales de Mileto, 3teorema, 4teorema chino del residuo

congruencias, 78

unión de conjuntos, 8unicidad del 0

enteros, 65unicidad del 1

enteros, 66unicidad del inverso multiplicativo

enteros, 66unidades

enteros, 69

vértices interiores de un camino, 44