ALGEBRA I
UNIDAD N°4:
COORDINABILIDAD O EQUIPOTENCIA DE CONJUNTOS- PRINCIPIO DE
INDUCCIÓN- COMBINATORIA
INTRODUCCIÓN
Se pueden contar los elementos de un conjunto finito y decir cuántos hay. Por ejemplo, A = {1; 2; 3}
tiene tres elementos y B = {p N : p primo ^ p ≤ 20} tiene 8 elementos. De hecho, si se nos preguntase qué se
entiende por conjunto finito, probablemente responderíamos que es aquel cuyos elementos pueden ser contados.
Sin embargo, no es en principio fácil decir cuántos elementos tienen N; Z; Q o R; todos ellos son conjuntos
infinitos, pues no podemos contar sus elementos, y en un primer análisis un tanto ingenuo parece que las
inclusiones estrictas N Z Q R, indican que N es el más pequeño y R el más grande. El actual tratamiento de los
conjuntos infinitos es obra del matemático alemán George Cantor (1845-1918), quien a fines del siglo pasado
logró sistematizar las ideas desordenadas que giraban en torno a este tema desde varios siglos antes y avanzar en
el análisis de resultados insospechados hasta entonces. La preocupación por definir el infinito es muy antigua,
manteniéndose a lo largo del tiempo la noción de lo mucho, lo que no puede ser contado como su equivalente
natural. Antiguamente se entendía como una especie de tope, más allá del cual no podía haber nada. Lo que fue
variando de una civilización a otra es la ubicación de ese tope. A medida que la posibilidad de contar progresaba,
el infinito se corría. Así fueron encontrados números cada vez mayores, hasta que se comprendió que no puede
haber límite al pensamiento humano. Es célebre la paradoja de Zenón según la cual Aquiles nunca podría
alcanzar a una tortuga. Cantor, pese a la indiscutible autoridad de Gauss se dedicó al tema, poniendo de
manifiesto una gran intuición creativa y mucha energía para perseverar dado que muchos de sus contemporáneos
discutían fuertemente su trabajo. Mostraremos, entonces, cómo pueden definirse y estudiarse las magnitudes
infinitamente grandes siguiendo sus ideas. Descubriremos a lo largo del tratamiento que en este tema se
evidencia fuertemente una de las principales características de la Matemática: en ella, más que en cualquier otra
ciencia, reina la libre creación. No es un accidente que en el nacimiento de la Teoría de conjuntos (1883) se
acuñara la expresión: La verdadera esencia de la Matemática es su libertad
También desarrollaremos en esta unidad el método más utilizado en la matemática: Método de
Inducción, para demostrar resultados generales que dependen en algún sentido de los números naturales. Y por
último, desarrollaremos la teoría Combinatoria
CONJUNTOS COORDINABLES
Definición: Se dice que los conjuntos A y B tienen igual potencia, que son coordinables o que son conjuntos
coordinables, si existe una biyección entre ellos, lo que se expresa A B.
En símbolos:
Observación:
Esta relación satisface las siguientes propiedades:
PROF. NÉLIDA ARRIETA 54
ALGEBRA I
1) Reflexividad: Todo conjunto es coordinable a sí mismo, ya que la función identidad es una biyección de A en
A
2) Simetría: Si un conjunto es coordinable a otro, entonces éste es coordinable con el primero, ya que si f : A B
es una biyección, entonces también lo es f-1 : B A;
3) Transitividad: Si un conjunto es coordinable con otro, y éste es coordinable con un tercero, entonces el
primero es coordinable con el tercero.
(Demostración en clase)
De lo anterior podemos decir que la relación es de equivalencia, y por un resultado anterior, existe una
partición en clases de equivalencia, las cuales reciben el nombre de cardinales
Definición: Dado A, llamamos cardinal de A a la clase de equivalencia [A] respecto de la relación de
equipotencia. Se representa por |A|,
Se tiene entonces: |A|=|B|
En particular Si A= | , es decir denotamos con cero el número cardinal del conjunto vacío.
Si A= | 1;
Si A= | 2, etc
1. Conjuntos Finitos E Infinitos
Llamaremos intervalo natural inicial al conjunto de los n primeros números naturales, es decir:
Definición: Un conjunto A se dice finito si y solo si es vacío o coordinable a un intervalo natural inicial
Es decir:
Definición: Un conjunto es infinito si y solo si no es finito.
Observaciones: 1) Si A es un conjunto finito y B está estrictamente incluido en A, entonces no existe ninguna
biyección entre
A y B; esto es, un conjunto finito no es coordinable a ninguna de sus partes propias (sin demostración).
2) Según lo anterior, si un conjunto A se puede poner en correspondencia biyectiva con alguna de sus partes
propias, entonces A no puede ser finito; en tal caso, se dirá que A es infinito.
Ejemplos: 1) El conjunto N de los números naturales es infinito pues podemos establecer una biyección entre N
y el conjunto P = {2n/ n N} de los números pares, que está contenido estrictamente en N; una tal biyección es,
por ejemplo:
f: N P; definida por f(n) = 2n
2) El conjunto R de los números reales es infinito pues se puede poner en correspondencia con el intervalo (-1;
1), por ejemplo, que está estrictamente incluido en R, ya que la función
f : (-1; 1) R; definida por f(x) = es biyectiva
PROF. NÉLIDA ARRIETA 55
ALGEBRA I
Los anteriores ejemplos ponen de manifiesto que N y R son conjuntos infinitos. Los cardinales de estos
conjuntos son, de entre los no finitos, los de mayor interés.
1.1. Caracterización de los conjuntos infinitos
Un conjunto A es infinito si y solo si se verifica cualquiera de las siguientes condiciones:
• Algún subconjunto de A es coordinable con N.
• El conjunto A es coordinable con alguna de sus partes propias
Definición: Se dice que A es un conjunto infinito numerable si es coordinable con N.
Es decir
Observación:1) Al cardinal de N, el conjunto de los números naturales, se lo denota por (alef cero).
2) Para indicar que un conjunto puede ser finito o coordinable a N, suele decirse que es a lo sumo numerable
3) El conjunto R de los números reales es infinito, pero R no es infinito numerable. Se dice que R y todos los
conjuntos coordinables con R tienen la potencia del continuo; el cardinal de R se denota por (alef uno)
Ejemplos: 1) El conjunto Z, de los números enteros, es infinito numerable, ya que la siguiente función es una
biyección:
2) El conjunto Q, de los números racionales, es numerable, pues se puede probar que Q+ ={q Q : q > 0} puede
distribuirse como:
... ... ... ...
3) El conjunto C, de los números complejos, tiene la potencia del continuo. Esta afirmación equivale a esta otra:
el intervalo real (0; 1) es coordinable al producto cartesiano (0; 1)x(0; 1), ya que R es coordinable a (0; 1), C es
coordinable a RxR, y este conjunto los es, pues, a (0; 1)x(0; 1).
Todo se reduce a encontrar una función como:
f: (0; 1)x(0; 1) (0; 1); f(x; y) = 0, a1 b1 a2 b2… donde que es biyectiva
Observaciones:
1) De acuerdo con lo dicho anteriormente, si A es un conjunto infinito numerable, entonces existe alguna
biyección
Llamando an = f(n), el conjunto A se puede escribir como: A =
Recíprocamente, todo conjunto de la forma (con para i j) es infinito numerable ya que
: f(n) = an es una biyección.
PROF. NÉLIDA ARRIETA 56
ALGEBRA I
Podemos resumir lo anterior diciendo que un conjunto A es infinito numerable si y sólo si es posible numerar sus
elementos recurriendo a los números naturales o, también, si y sólo si, los elementos de A pueden ponerse en
forma de sucesión indefinida
2) Dados dos conjuntos A y B, se escribirá |A|≤ |B| si A es coordinable con una parte de B.
3) Los conjuntos finitos tienen menor cardinal que el de N y la potencia del continuo es superior a la potencia de
los numerables, es decir |R| > |N|, o sea > .
3) Dados dos conjuntos A y B, la relación |A|≤ |B| significa que existe una aplicación inyectiva de A en B. Si
|A|≤ |B| ^ |A|≠ |B| . Esto ocurrirá pues hay una aplicación inyectiva de A en B y ninguna biyectiva.
4) No existe ningún conjunto infinito con potencia inferior a la de N, ya que todo conjunto infinito incluye a un
conjunto infinito numerable.
5) No se conoce ningún conjunto A tal que |N| < |A| < |R|. Se ha probado que la proposición “existe un
conjunto A tal que |N| < |A| < |R|" es indecidible (ni se puede demostrar, ni se puede refutar). Se llama hipótesis
del continuo al axioma que establece que no existe ningún cardinal estrictamente comprendido entre N y R.
6) Dado un cardinal cualquiera, siempre existe otro cardinal mayor que él, como prueba el Teorema de Cantor,
que asegura que para cualquier conjunto A, |A| < |P(A)|, donde P(A) es el conjunto de partes o conjunto potencia
de A.
Es entonces posible obtener una infinidad de conjuntos de cardinal infinito y ordenarlos. Llamando al cardinal
del conjunto de partes de R, al de las partes de las partes. . ., tenemos:
< < <...< <...
Estos cardinales se llaman Cardinales Transfinitos.
Enunciaremos a continuación algunos teoremas fundamentales, que se refieren a la numerabilidad.
Teorema 1. Todo conjunto infinito, tiene, al menos un subconjunto numerable.
Teorema 2. Todo subconjunto de un conjunto numerable es numerable.
Teorema 3. La unión de todos los conjuntos disjuntos numerables de una familia numerable es numerable.
Teorema 4. El conjunto de los números racionales Q es numerable.
PRINCIPIO DE INDUCCION COMPLETA
INTRODUCCION
El método deductivo, muy usado en matemática, obedece a la siguiente idea: “A partir de un cierto
conjuntos de axiomas aceptados sin demostración y de reglas lógicas no contradictorias, se deducen otros
enunciados llamados teoremas combinando los axiomas y respetando en cada etapa las reglas lógicas". Otro
método para demostrar resultados generales que dependen en algún sentido de los números naturales es conocido
con el nombre de Inducción Matemática.
Esta dependencia de los números naturales significa: se sabe que una determinada afirmación es
verdadera para algunos casos particulares y surge la pregunta. ¿Dicha afirmación sigue siendo verdadera para los
infinitos números naturales restante?
Existen muchas afirmaciones que sólo son válidas para un número finito de casos y en consecuencia son
falsas para un número infinitos de situaciones. Sin embargo, podemos encontrar proposiciones (afirmaciones)
PROF. NÉLIDA ARRIETA 57
ALGEBRA I
que son verdaderas sólo a partir de un cierto número natural n0, de ser asi, la técnica que se desarrollaremos se
llama Inducción Incompleta. Para demostrar que una proposición p(n); n M N, es verdadera es necesario
comprobar la validez de ella para todos los elementos del conjunto M. En el caso en que M= N, diremos que es
una Inducción Completa.
Si se requiere demostrar la falsedad de una cierta proposición p(n); n M N es suficiente indicar un
elemento particular m M de manera que p(m) sea falsa. (Construcción de un contra ejemplo).
Principio de inducción completa
Una proposición p(n) es verdadera para todos los valores de la variable n si se cumplen las siguientes
condiciones:
Paso 1.- La proposición p(n) es verdadera para n = 1, o bien, p (1) es verdadera.
Paso 2.- Hipótesis de Inducción. Se supone que p(k) es verdadera , donde k es un número natural cualesquiera.
Paso 3.- Tésis de Inducción. Se demuestra que p(k + 1) es verdadera, o bien, p(k) verdadera ) p(k + 1)
verdadera:
La técnica de Inducción Matemática consiste en los tres pasos anteriores. Si se necesita demostrar la validez de
una proposición p(n) para todos los valores naturales n, entonces es suficiente que se cumplan: Paso 1, Paso 2 y
Paso 3.
Intuitivamente la idea anterior se conoce con el nombre de “Efecto Dominó". Si imaginamos una la
infinita de fichas de dominó: dispuestas verticalmente y suficientemente próximas una cualquiera de la siguiente,
entonces si el volteamiento de la primera ficha provoca el volteamiento de la segunda ficha, por el Principio de
Inducción Matemática la fila completa es volteada.
El principio de inducción completa de una forma gráfica.
PRINCIPIO DE BUEN ORDEN
Todo conjunto no vacío de números naturales tiene un menor elemento.
PROF. NÉLIDA ARRIETA 58
ALGEBRA I
Decimos que N es un conjunto Bien Ordenado. Intuitivamente, este sencillo principio nos dice que
siempre puedo encontrar el más pequeño número natural tal que … donde la línea de puntos puede ser llenada
por cualquier propiedad (siempre que exista al menos un número natural que verifique dicha propiedad).
Como consecuencia de esto, por ejemplo, podemos probar que todo número natural n tiene un (único)
sucesor, o sea, el número que le sigue en el orden natural. (Esto ya lo sabemos: el sucesor de n es n + 1). Para
demostrarlo, basta considerar el conjunto no vacío de los números naturales estrictamente mayores que n y
aplicar el Principio de Buen Orden. El menor elemento de ese conjunto es el sucesor de n.
Cabe hacer notar que este menor elemento de un conjunto no vacío A cuya existencia garantiza el
Principio es único ya que si hubiera dos, digamos a y b, entonces a≤ b, ya que a es el menor elemento de A y b
A. Similarmente, b≤ a, por lo tanto a = b. Tampoco está de más recalcar que, a diferencia del ínfimo de un
conjunto, que puede no pertenecer a él, el menor elemento de A pertenece a A.
La segunda propiedad importante de los números naturales es:
TEOREMA DE INDUCCION COMPLETA
Sea P un conjunto de números naturales tal que:
i) 1 P,
ii) si k P entonces k + 1 P.
Entonces P = N:
Demostración: Sea P un conjunto de números naturales tal que verifica las hipótesis i) y ii)
Tesis: P=N
Es suficiente ver que N P y para esto basta demostrar que el subconjunto A de números naturales no
pertenecientes a P es vacío.
Supongamos que A es no vacío. En virtud del Principio de Buen Orden, A tiene un menor elemento “a” . a no
puede ser 1 ya que por hipótesis, 1 P. Luego a>1, y en consecuencia a-1>0 lo que es una contradicción. Esta
contradicción proviene de suponer que A es no vacío. Luego N P y como por hipótesis P , resulta que N P
1.2. PRINCIPIO DE INDUCCION COMPLETA
Sea una proposición P(n), donde n N. Si ocurre que P(1) es verdadera, y, además, de la verdad de P(h) se
deduce la verdad de P(h+1) entonces P(n) es verdadera para todo n.
Demostración: Hipótesis: 1) P(1) es verdadera
2) P(h) P(h+1)
Tesis: ( ): P(n) es verdadera
El subconjunto P de números naturales para los cuales P(n) es verdadera, contiene al 1, y al siguiente de h
siempre que contenga a h. luego por el teorema de inducción completa P=N. Es decir, P(n) es verdadera para
todo n N
Nota: La técnica de Inducción Matemática consiste en: Si se necesita demostrar la validez de una proposición
p(n) para todos los valores naturales n, entonces es suficiente que se cumpla la verdad de las dos proposiciones
de la hipótesis del principio de inducción.
PROF. NÉLIDA ARRIETA 59
ALGEBRA I
Ejemplo: Demostrar que la suma de los n primeros números naturales es igual a
Demostración: Queremos probar que
i) Demostremos que la propiedad se verifica para n=1
ii) Demostremos la verdad de la implicación de la hipótesis del principio de inducción completa, es decir:
P(h) P(h+1)
Hipotesis Inductiva: P(h):
Tesis: P(h+1) es verdadera
Demostremos que:
P(h+1): ,
Por la Hipótesis Inductiva resulta:
De donde resulta que la propiedad anterior es verdadera para h+1 y por lo tanto es válida para todo n N.
Observación: Existen dos variantes útiles sobre el Principio de Inducción Completa que deben ser considerados:
En la primera variante, la proposición por demostrar involucra los naturales no menores a un natural fijo n 0, en
este caso el Principio de Inducción quedaría como sigue:
Si p(n) es verdadera para n0 y si p(m+ 1) es verdadera para todo natural m n0 para la cual p(m) es
verdadera, entonces p(n) es verdadera para todo natural n n0
La segunda variante se aplica de preferencia en el caso cuando p(m + 1) no puede ser fácilmente deducible de
p(m), pero su validez depende de p(k) para cualquier k < m. Si p(1) es verdadera y si p(m + 1) es verdadera
para todo m 1 para la cual todas las proposiciones p(1); p(2); p(3);…; p(m) son verdaderas , entonces p(n)
es verdadera para n 1. Para ilustrar el uso de estas variantes, consideremos los siguientes ejemplos:
Ejemplos: 1) Determine para que valores de n N es verdadera la desigualdad:
Al examinar los valores de n = 1; 2; 3; 4; 5; 6 nos damos cuenta que la desigualdad es incorrecta, pero si es
verdadera para n = 7, por lo que podemos intentar demostrar por el método de Induccion Incompleta que para
todos los valores de n 7, la desigualdad es verdadera.
i) Si n = 7, obtenemos:
27 = 128 > 72 + 4 . 7 + 5 = 82
O sea, cuando n = 7 la desigualdad es correcta
ii) (Hipótesis Inductiva) Se supone que la desigualdad es verdadera para un cierto valor de n = k, o sea,
PROF. NÉLIDA ARRIETA 60
ALGEBRA I
2)
3)
1.3. Propiedades De La Sumatoria
A continuación se dan las principales propiedades de la sumatoria:
1)
2)
3)
4)
5)
Ejemplos: Demuestre por inducción completa que la suma de los n primeros números naturales impares es n 2
En términos de sumatoria:
En efecto:
i) P(1):
ii) Hipótesis Inductiva: P(h):
Tesis: P(h+1):
Por la propiedad 5) de sumatoria:
Por la Hipótesis Inductiva
LA FUNCIÓN FACTORIAL
La función definida por : se conoce como FUNCIÓN
FACTORIAL
Y se simboliza con en lugar de f ,
y se escribe para indicar f(h).
PROF. NÉLIDA ARRIETA 62
ALGEBRA I
Teniendo en cuenta lo anterior podemos definir a la función factorial por:
Nota: la expresión se lee factorial de h
Propiedad: El factorial de un número natural es igual al producto de los primeros números naturales,
esto es:
Ejercicio: Demostrar la propiedad anterior por el principio de inducción completa
Observaciones:
1) La función factorial no es inyectiva puesto que
2) La función factorial no es sobreyectiva, pues existen números naturales que no se identifican con el factorial
de ninguno, tal es el caso del 7 que carece de preimagen en
NÚMEROS COMBINATORIOS
Dados m, n N, m n. Se define el número combinatorio o coeficiente binómico al número:
Se lee: “m sobre n”
Los elementos de un número combinatorio se llaman numerador y denominador
Ejemplo:
Con esta notación, se definen los siguientes números combinatorios:
1)
2)
3)
4)
5)
Propiedades fundamentales de los números combinatorios
1)
2)
Demostración: EJERCICIO
PROF. NÉLIDA ARRIETA 63
ALGEBRA I
2k > k2 + 4k + 5
Finalmente a partir de la hipótesis inductiva, se desea probar la Tesis dada por
2(k+1) > (k + 1)2 + 4(k + 1) + 5:
Al multiplicar la desigualdad dada en la hipótesis inductiva por 2, obtenemos
2(k+1) > 2k2 + 8k + 10
Transformando el segundo miembro de esta desigualdad obtenemos
2(k+1) > (k + 1)2 + 4(k + 1) + 5 + k2 + 2k
Teniendo en cuenta que k2 + 2k > 0 para todo k 7, podemos deducir que:
2(k+1) > (k + 1)2 + 4(k + 1) + 5, obteniendo lo que se quería demostrar (Tesis).
2) Consideremos el siguiente ejemplo de divisibilidad:
Demostrar por inducción, que si n es un número impar, 7 n + 1 es divisible por 8.
Antes de aplicar inducción conviene hacer un cambio de índices. Sea n = 2i- 1:
Entonces si i = 1; 2; 3; … se tiene que n = 1; 3; 5; … y nuestro enunciado se transforma en:
72i-1 es divisible por 8, i N:
i) Para i = 1, 71 + 1 = 8 es divisible por 8, lo que es una proposición verdadera.
ii) Hipótesis inductiva: 72i-1+1 es divisible por 8:
Tesis: 72i+1 es divisible por 8:
Dado que nuestra única información es la hipótesis, debemos hacer que la expresión 7 2i-1 + 1 aparezca en el
desarrollo
72i+1 + 1 = 72(72i-1) + 1 = 72(72i-1 + 1) - 72 + 1 = 72(72i-1 + 1) - 48
y aquí ambos sumandos son divisibles por 8, luego 8 divide a 7 2i+1 +1. Luego resulta que 7 n + 1 es divisible por 8
para todo n impar.
EL SÍMBOLO SUMATORIA
En muchas situaciones se presenta la conveniencia de abreviar la notación de una suma cuyos términos
admiten cierta ley de formación. En este sentido es útil la introducción del símbolo de sumatoria:
El símbolo se llama Sigma en el alfabeto griego y en Español corresponde a la letra S.
Con el símbolo i2, se desea indicar la suma de los términos de la forma i 2 para varios valores enteros de
i. El rango para estos valores enteros se indica en la parte inferior y superior respectivamente de . Por ejemplo
en la forma:
Ejemplos:
1)
PROF. NÉLIDA ARRIETA 61
