Archivo del Autor: Julio César Soria Ramírez

Nota 21. Conteo, ordenaciones con repetición.

Por Julio César Soria Ramírez

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

Una vez que tenemos construidos los números naturales, su primera aplicación será el conteo, en esta nota analizaremos la situación conocida como ordenaciones con repetición de $n$ elementos tomados de $m$ en $m$ , que son todas las secuencias ordenadas de $m$ entradas, llenadas con los $n$ objetos de un determinado conjunto.

Definición

Sean $n, m \in N^{+}$ . Dado un conjunto finito $A = {a_{1}, \dots, a_{n}}$ con $n$ elementos, las ordenaciones con repetición de los elementos de $A$ tomados de $m$ en $m$ son las funciones de ${1, \dots, m}$ en $A$ . Al número de ordenaciones con repetición de los elementos de un conjunto de $n$ elementos tomados de $m$ en $m$ lo denotaremos por $O R_{n}^{m}$ .

$O R_{n}^{m} = # {f ∣ f : {1, \dots, m} \to A = {a_{1}, \dots, a_{n}}}$

Ejemplo.

Sea $A = {a, e, i, o, u}$ . Las ordenaciones con repetición de los elementos de $A$ tomados de dos en dos son las funciones de ${1, 2}$ en ${a, e, i, o, u}$ . Por ejemplo, una de esas ordenaciones es:

$1 ⟼ i$

$2 ⟼ a$

Recordemos que esta función se puede describir como:

$(\begin{matrix} 1 & 2 \\ i & a \end{matrix})$

Lo que determina a esta función es la palabra $i a$ que aparece en el segundo renglón. ¿Cuántas funciones hay de ${1, 2}$ en $A = {a, e, i, o, u}$ ?, o bien, ¿cuántas palabras podemos formar con dos letras usando sólo vocales?.

Hay 5 palabras que inician con $i$ : $i a$ , $i e$ , $i i$ , $i o$ , $i u$ .

Hay 5 palabras que inician con $a$ : $a a$ , $a e$ , $a i$ , $a o$ , $a u$ .

Hay 5 palabras que inician con $e$ : $e a$ , $e e$ , $e i$ , $e o$ , $e u$ .

Hay 5 palabras que inician con $o$ : $o a$ , $o e$ , $o i$ , $o o$ , $o u$ .

Hay 5 palabras que inician con $u$ : $u a$ , $u e$ , $u i$ , $u o$ , $u u$ .

Por cada vocal inicial tenemos $5$ palabras, así que en total tenemos $25$ palabras.

Podemos pensar a estas funciones o palabras como pares ordenados:

${(i, a), (i, e), (i, i), (i, o), (i, u), (a, a), (a, e), (a, i), (a, o), (a, u), \dots} = A \times A$

Por lo que: $# A \times A = # A \cdot # A = 5 \cdot 5 = 5^{2} = O R_{5}^{2}$

Acabamos de obtener que $O R_{5}^{2} = 5^{2}$ , veremos en el siguiente teorema que esto es válido en general y que $O R_{n}^{m} = n^{m}$ .

Teorema

Sean $n, m \in N^{+}$ , entonces $O R_{n}^{m} = n^{m}$ .

Demostración

Sea $A = {a_{1}, \dots, a_{n}}$ con $n$ elementos.

Por definición:

$O R_{n}^{m} = # {f ∣ f : {1, \dots, m} \to A = {a_{1}, \dots, a_{n}}}$ .

Veamos que $# {f ∣ f : {1, \dots, m} \to A = {a_{1}, \dots, a_{n}}} = # A^{m}$ dando una biyección entre ambos conjuntos (recuerda que $A^{m}$ es el producto cartesiano de $A$ consigo mismo $m$ veces).

Sea $φ : {f ∣ f : {1, \dots, m} \to A = {a_{1}, \dots, a_{n}}} \to A^{m}$ dada por:

$φ (f) = φ ((\begin{matrix} 1 & \dots & m \\ f (1) & \dots & f (m) \end{matrix})) = (f (1), \dots, f (m))$ .

La función $φ$ es inyectiva ya que si $f, g : {1, \dots, m} \to A$ son tales que $φ (f) = φ (g)$ , entonces $(f (1), \dots, f (m)) = (g (1), \dots, g (m))$ , y así $f (i) = g (i) \forall i \in {1, \dots, m}$ , de donde $f$ y $g$ tienen la misma regla de correspondencia, y como coinciden en dominio y codominio entonces $f = g$ . Por lo tanto $φ$ es inyectiva.

Además $φ$ es suprayectiva ya que si $(x_{1}, \dots, x_{m}) \in A^{m}$ , podemos considerar la función:

$f = (\begin{matrix} 1 & \dots & m \\ x_{1} & \dots & x_{n} \end{matrix})$ y es tal que

$φ (f) = φ ((\begin{matrix} 1 & \dots & m \\ x_{1} & \dots & x_{n} \end{matrix})) = (x_{1}, \dots, x_{m})$ .

Así, $φ$ es también suprayectiva, y por lo tanto biyectiva. Entonces:

$# {f ∣ f : {1, \dots, m} \to A = {a_{1}, \dots, a_{n}}} = # A^{m} .$

Recordemos que la notación antes establecida nos dice que $# {f ∣ f : {1, \dots, m} \to A = {a_{1}, \dots, a_{n}}} = O R_{n}^{m} .$

Por otro lado, por el principio generalizado del producto el número de elementos de $A^{m}$ es el número de elementos de $A$ multiplicado $m$ veces. Así, $# A^{m} = n^{m}$ . Concluimos finalmente que:

$O R_{n}^{m} = n^{m}$ .

Tarea moral

¿Cuántos números telefónicos hay con $8$ dígitos (del $0$ al $9$ ) que empiecen con $5$ ?
¿Cuántas placas hay que inicien con $3$ números (del $0$ al $9$ ) y terminen con $3$ letras (contando $27$ en el alfabeto)?
¿Cuántas palabras de $5$ letras se pueden formar con el alfabeto de $27$ letras?
Ve el siguiente video del profesor Luis Rincón.

Más adelante

En la siguiente nota continuaremos con el tema de conteo, esta vez para las ordenaciones sin repetición.

Enlaces relacionados

Página principal del curso.

Enlace a la nota anterior. Nota 20. Principio del producto, funciones entre conjuntos finitos.

Enlace a la nota siguiente. Nota 22. Conteo. Ordenaciones.

Nota 20. Principio del producto, funciones entre conjuntos finitos.

Por Julio César Soria Ramírez

Deja un comentario

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota deduciremos el resultado conocido como Principio del producto que nos garantiza que el número de elementos del producto cartesiano de dos conjuntos finitos (ver nota 6) es igual al producto del número de elementos de cada conjunto. Así mismo, probaremos que para una función entre conjuntos finitos de la misma cardinalidad, las nociones de ser inyectiva, suprayectiva o biyectiva son equivalentes.

Empecemos probando un lema que nos ayudará a probar el principio del producto.

Lema 1

Sean $A$ un conjunto finito y ${b}$ un conjunto unitario, entonces $A \times {b}$ es finito y $# (A \times {b}) = # A$ .

Demostración

Sean $A$ un conjunto finito y ${b}$ un conjunto unitario, con $n = # A$ y $f : {1, \dots, n} \to A$ una biyección.

Sea $g : A \to A \times {b}$ dada por $g (a) = (a, b)$ $\forall a \in A$ .

Observemos que la función $h : A \times {b} \to A$ dada por $h ((a, b)) = a \forall (a, b) \in A \times {b}$ es la inversa de g, pues:

$h \circ g (a) = h (g (a)) = h ((a, b)) = a \forall a \in A$ .

$g \circ h ((a, b)) = g (h ((a, b))) = g (a) = (a, b) \forall (a, b) \in A \times {b}$ .

Así, $g$ es invertible y por lo tanto biyectiva.

Como $f$ y $g$ son biyectivas, entonces $g \circ f : {1, \dots, n} \to A \times {b}$ es biyectiva.

Así, $# (A \times {b})$ es un conjunto finito con $# (A \times {b}) = n$ . Por lo tanto $# (A \times {b}) = # A$ .

Teorema. Principio del producto

Sean $A, B$ conjuntos finitos, entonces $A \times B$ es finito y $# (A \times B) = # A \cdot # B$ .

Demostración

Sean $A, B$ conjuntos finitos con $n = # A$ , $m = # B$ .

Entonces $B = {b_{1}, \dots, b_{m}}$ con $b_{i} \neq b_{j} \forall i, j .$

Observemos que $A \times B = (A \times {b_{1}}) \cup (A \times {b_{2}}) \cup \dots \cup (A \times {b_{m}})$ donde $(A \times {b_{i}}) \cap (A \times {b_{j}}) = \emptyset \forall i \neq j$ .

Por el principio generalizado de la suma visto en la nota anterior

$# (A \times B) = # (A \times {b_{1}}) + # (A \times {b_{2}}) + \dots + # (A \times {b_{m}}) .$

Por el lema previo $\forall i$ $# (A \times {b_{i}}) = # A$ , entonces tenemos que:

$# (A \times B) = m \cdot # A$ , y como $m = # B$ sustituyendo obtenemos que:

$# (A \times B) = # A \cdot # B .$

Nota

Este resultado se puede generalizar, si $A_{1}, \dots, A_{t}$ son conjuntos finitos, entonces $A_{1} \times \dots \times A_{t}$ es finito y $# (A_{1} \times \dots \times A_{t}) = # A_{1} \dots # A_{t}$ , y se conoce como el principio generalizado del producto.

Veamos ahora qué información podemos obtener acerca de la cardinalidad de dos conjuntos finitos, a partir de las características de alguna función definida entre ellos.

Lema 2

Sean $A, B$ conjuntos finitos

i) Si existe $f : A \to B$ inyectiva, entonces $# A = # I m f$ y $# A \leq # B$ .

ii) Si existe $f : A \to B$ suprayectiva, entonces $# A \geq # B$ .

Demostración de i)

Sean $A$ y $B$ conjuntos finitos.

Supongamos que existe $f : A \to B$ inyectiva.

Consideremos la función $F : A \to I m f$ tal que $F (a) = f (a) \forall a \in A$ .

Como $f$ es inyectiva $F$ también lo es, y por construcción $F$ es suprayectiva.

Así, $F$ es biyectiva y entonces $# A = # I m f$ .

Como $I m f \subseteq B$ y $B$ es finito, entonces $I m f$ también es finito y $# I m f \leq # B$ (ver la nota anterior), de donde $# A = # I m f \leq # B$ .

Demostración de ii)

Sean $A$ y $B$ conjuntos finitos.

Supongamos que existe $f : A \to B$ suprayectiva.

Sea $B = {b_{1}, \dots, b_{m}}$ con $m = # B$ y $b_{i} \neq b_{j} \forall i, j$ .

Como $f$ es suprayectiva, para cada $b_{i} \in B$ existe un elemento de $A$ que bajo $f$ va a dar a $b_{i}$ , elijamos uno de ellos, digamos $a_{i} \in A$ tal que $f (a_{i}) = b_{i}$ .

Definamos la función $g : B \to A$ con $g (b_{i}) = a_{i} \forall i \in {1, \dots, m} .$ Veamos que $g$ es inyectiva.

Si $i, j \in {1, \dots, m}$ son tales que $g (b_{i}) = g (b_{j})$ , entonces $a_{i} = g (b_{i}) = g (b_{j}) = a_{j}$ , de manera que $a_{i} = a_{j}$ y en consecuencia:

$b_{i} = f (a_{i}) = f (a_{j}) = b_{j},$

por lo cual $b_{i} = b_{j}$ , así $g$ es inyectiva.

Por el inciso $i)$ tenemos entonces que el dominio de $g$ tiene menor o igual número de elementos que su condominio, es decir $# B \leq # A$ .

Observaciones

Sea $A$ un conjunto finito. Si $A \neq \emptyset$ , entonces $# A \geq 1$ . De modo equivalente si $# A = 0$ entonces $A = \emptyset$ .
Sean $A, B$ conjuntos finitos con $A \subseteq B$ . Si $# A = # B$ , entonces $A = B$ .

Teorema

Sean $A, B$ conjuntos finitos con $# A = # B$ , $f : A \to B$ .

Las siguientes afirmaciones son equivalentes:

a) $f$ es inyectiva.

b) $f$ es suprayectiva.

c) $f$ es biyectiva.

Demostración

Sean $A, B$ conjuntos finitos con $# A = # B$ , $f : A \to B$ .

a) $⟹$ b)

Supongamos que $f$ es inyectiva.

Por demostrar que $f$ es suprayectiva.

Como $f$ es inyectiva, por el Lema 2 $# A = # I m f$ , tenemos entonces que

$# B = # A = # I m f$

Así, $I m f \subseteq B$ con $# I m f = # B$ , y por un ejercicio de la nota anterior sabemos que $I m f = B$ . Por lo tanto $f$ es suprayectiva.

b) $⟹$ a)

Supongamos que $f$ es suprayectiva, es decir que $I m f = B$ .

Por demostrar que $f$ es inyectiva.

Sea $n = # A = # B$ , $A = {a_{1}, \dots, a_{n}}$ con $a_{i} \neq a_{j} \forall i \neq j$ .

Como $I m f = B$ , entonces $# I m f = # B = n$ .

Supongamos por reducción al absurdo que $f$ no es inyectiva, entonces existen dos elementos de $A$ que bajo $f$ son iguales, sin pérdida de generalidad supongamos que $f (a_{n - 1}) = f (a_{n})$ , entonces:

$I m f = {f (a_{1}), \dots, f (a_{n - 1})}$

La función $h : {1, \dots, n - 1} \to I m f$ con $h (i) = f (a_{i}) \forall i$ sería entonces suprayectiva, así aplicando el lema 2 tenemos que:

$n - 1 = # {1, \dots, n - 1} \geq # I m f = # B = n$ , y entonces tendriamos que $n - 1 \geq n$ , pero eso es una contradicción y por lo tanto $f$ es inyectiva.

Hemos probado entonces que, bajo nuestras hipótesis, $f$ es inyectiva si y sólo si es suprayectiva, así que si se cumple a) se tiene también b) y entonces $f$ es biyectiva y se cumple c). Análogamente si se cumple b) se tiene también a) y entonces $f$ es biyectiva y se cumple c). Además, si se cumple c) se tiene que $f$ es biyectiva y por lo tanto es inyectiva y suprayectiva, así que se cumplen a) y b).

Por lo tanto las condiciones a), b) y c) son equivalentes.

Tarea moral

1. Sean $A$ y $B$ conjuntos finitos. Demuestra o da un contraejemplo:

i) Si $# A \leq # B$ y $f$ es una función $f : A \to B$ , entonces $f$ es inyectiva.

ii) Si $# A \geq # B$ y $f$ es una función $f : A \to B$ , entonces $f$ es suprayectiva.

iii) Si $# A = # B$ y $f$ es una función $f : A \to B$ , entonces $f$ es biyectiva.

2. Considera que para acceder a una aplicación se requiere una contraseña de tres dígitos que pueden ser $0, 1, 2, 3, 4, 5, 6, 7, 8$ o $9$ .
i) Describe a cada contraseña como una terna ordenada y al conjunto de contraseñas como un producto cartesiano
ii) ¿Cuántas contraseñas posibles hay?
iii) Si ahora la contraseña puede ser de tres o de cuatro dígitos ¿cuántas contraseñas habrá?

3. Ve el siguiente vídeo para que conozcas otro importante principio de conteo, el principio del palomar.

Más adelante

En las siguientes notas haremos énfasis en el estudio de las técnicas de conteo. Estudiaremos las ordenaciones, las ordenaciones con repetición y las combinaciones.

Enlaces relacionados

Página principal del curso.

Enlace a la nota anterior. Nota 19. Conjuntos equivalentes y cardinalidad.

Enlace a la nota siguiente. Nota 21. Conteo, ordenaciones con repetición.

Nota 19. Conjuntos equipotentes y cardinalidad

Por Julio César Soria Ramírez

Deja un comentario

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En ésta y la siguiente nota formalizaremos la noción intuitiva que tenemos acerca del tamaño de los conjuntos. Para ello usaremos las funciones. Diremos que dos conjuntos son equipotentes si existe una función biyectiva entre ellos y estableceremos qué significa que un conjunto sea finito. Probaremos el principio de la suma que nos habla de el número de elementos de la unión de dos conjuntos finitos y ajenos, con este resultado demostraremos un importante corolario que nos habla del número de elementos de la unión de dos conjuntos finitos cuando los conjuntos no son necesariamente ajenos.

Definición

Sean $A$ y $B$ conjuntos. Decimos que $A$ tiene la misma cardinalidad que $B$ o que $A$ es equipotente con $B$ si existe una función biyectiva de $A$ en $B$ y lo denotaremos por:

$A \sim B$

Ejemplos.

1. $A = {1, 2, 3, 4}$ , $B = {1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}}$ son equipotentes ya que $f : A \to B$ con $f (n) = \frac{1}{n}$ $\forall n \in A$ es una función biyectiva.

2. $N = {0, 1, 2, 3, \dots}$ y $N^{+} = {1, 2, 3, \dots}$ .

¿Son $N$ y $N^{+}$ conjuntos equipotentes?, ¿ $N \sim N^{+}$ ?

La función $f : N \to N^{+}$ dada por $f (n) = n + 1$ $\forall n \in N$ es inyectiva, pues si $n, m \in N$ son tales que $f (n) = f (m),$ entonces $n + 1 = m + 1$ y así $n = m$ .

Además es suprayectiva pues si $n \in N^{+}$ con $n \neq 0$ , sabemos por un ejercicio de la nota 16 que $n = m^{+} = m + 1$ para alguna $m \in N$ , entonces $f (m) = m + 1 = n$ con $m \in N$ .

Concluimos que $N \sim N^{+}$ .

3. Sea $P = {n \in N ∣ n e s p a r} = {2 m ∣ m \in N}$

¿Los naturales son equipotentes a $P$ ?

La función $f : N \to P$ dada por $f (m) = 2 m$ $\forall m \in N$ es una biyección así $N \sim P .$

Tarea moral, demuéstralo.

4. ¿Qué dices de los números naturales y los enteros?, ¿ $N \sim Z$ ?

Considera la siguiente función $f : N \to Z$ :

$f (n) = {\begin{array}{lcc} \frac{n}{2} & s i & n e s p a r \\ \frac{- n + 1}{2} & s i & n e s i m p a r \end{array}$

$f$ es biyectiva, así $N \sim Z$ .

Tarea moral, demuéstralo.

5. El intervalo $(- \frac{π}{2}, \frac{π}{2})$ es equipotente a $R$ .

Considera la función tangente, la función tangente es biyectiva en ese intervalo.

Tarea moral, investiga las propiedades de la función tangente para que te convenzas de lo anterior.

Nota

Se puede probar que:

Si $n \in N^{+}$ , todo subconjunto de ${1, \dots, n}$ es finito y tiene a lo más $n$ elementos.

Si $A$ es un conjunto finito con $n$ elementos, entonces todo subconjunto de $A$ es finito y tiene a lo más $n$ elementos.

La demostración puede verse en el libro de Avella y Campero mencionado en la bibliografía, corolario 6.9 y corolario 6.12, páginas 244 y 246.

Debido a lo anterior podemos establecer la siguiente definición.

Definición

Si $A$ es un conjunto, decimos que $A$ es finito si $A = \emptyset$ o existe $n \in N^{+}$ , tal que $A \sim {1, \dots, n}$ . El número de elementos de $A$ es cero en el primer caso y $n$ en el segundo caso.

Si $A$ no es finito decimos que $A$ es infinito.

Notación

$# \emptyset =∣ \emptyset ∣= 0$ , $# A =∣ A ∣= n .$

En este caso si $f : {1, \dots, n} \to A$ denotamos a $f (i)$ por $a_{i}$ y así $A = {a_{1}, \dots, a_{n}}$ con $a_{i} \neq a_{j}$ para toda $i \neq j$ .

Observación

Dados $A$ y $B$ conjuntos finitos: $A \sim B$ si y sólo si $# A = # B$ .

Recordemos que dos conjuntos son ajenos o disjuntos si su intersección es vacía, ver la nota 4. Veamos ahora qué ocurre con el número de elementos de la unión de dos conjuntos finitos y ajenos.

Teorema: principio de la suma.

Sean $A$ y $B$ conjuntos finitos con $A \cap B = \emptyset$ , entonces $A \cup B$ es finito y $# A \cup B = # A + # B$ .

Demostración

Sean $A$ y $B$ conjuntos finitos con $A \cap B = \emptyset$ . Sean $n = # A$ y $m = # B$ , $f : {1, \dots, n} \to A$ , $g : {1, \dots, m} \to B$ biyecciones.

Definimos:

$h : {1, 2, \dots, n, n + 1, n + 2, \dots, n + m} \to A \cup B$

con

$h (i) = {\begin{array}{lcc} f (i) & s i & i \in {1, \dots, n} \\ g (k) & s i & i = n + k c o n k \in {1, \dots, m} \end{array}$

Veamos que $h$ es suprayectiva.

Sea $c \in A \cup B$ , entonces $c \in A$ o $c \in B$ .

Caso 1 $c \in A$

Como $f$ es suprayectiva existe $i \in {1, \dots, n}$ , tal que $f (i) = c$ , así $h (i) = f (i) = c .$

Caso 2 $c \in B$

Como $g$ es suprayectiva existe $k \in {1, \dots, m}$ , tal que $g (k) = c$ , así $h (n + k) = g (k) = c$ .

por lo tanto $h$ es suprayectiva

Veamos que $h$ es inyectiva.

Sean $i, j \in {1, \dots, n + m}$ , tales que $h (i) = h (j)$

Por demostrar que $i = j$

Caso 1

$i, j \in {1, \dots, n} .$

Por definición de $h$ tenemos que:

$f (i) = h (i), f (j) = h (j)$

Por hipótesis tenemos que

$h (i) = h (j)$

y por lo tanto

$f (i) = f (j) .$

Como $f$ es inyectiva tenemos que $i = j .$

Caso 2

$i, j \in {n + 1, \dots, n + m} .$

En este caso tenemos que $i = n + k$ y $j = n + q$ para algunos $k, q \in {1, \dots, m} .$

Por hipótesis tenemos que

$h (i) = h (j),$

así obtenemos las siguientes igualdades

$h (n + k) = h (i) = h (j) = h (n + q)$

Por definición de $h$ tenemos que

$h (n + k) = g (k)$ y $h (n + q) = g (q)$

De lo que se deduce que

$g (k) = h (n + k) = h (i) = h (j) = h (n + q) = g (q) .$

Entonces $g (k) = g (q)$ , y como $g$ es inyectiva entonces $k = q$ y por lo tanto $i = n + k = n + q = j$ . Así, $i = j$ .

Caso 3

$i \in {1, \dots, n}$ y $j \in {n + 1, \dots, n + m}$

En este caso $j = n + k$ para algún $k \in {1, \dots, m} .$

Observa que:

$h (i) = f (i) \in A$ y que $h (j) = f (n + k) = g (k) \in B .$

Como $h (i) = h (j)$ entonces $h (i) \in A \cap B$ pero esto es una contradicción a nuestra hipótesis de que $\emptyset = A \cap B$ , por lo tanto no ocurre este caso.

Caso 4

$j \in {1, \dots, n}$ y $i \in {n + 1, \dots, n + m}$

Es similar al caso anterior y por lo tanto tampoco ocurre.

Por lo tanto $h$ es inyectiva.

Tenemos entonces que $h : {1, 2, \dots, n, n + 1, n + 2, \dots, n + m} \to A \cup B$ es una función biyectiva lo que nos permite concluir que $A \cup B$ es finito y $# A \cup B = n + m$ . Finalmente, $# A \cup B = n + m = # A + # B$ .

Nota

La generalización del resultado anterior, llamado principio generalizado de la suma, se enuncia como sigue:

Si $A_{1}, \dots, A_{t}$ son conjuntos finitos tales que $A_{i} \cap A_{j} = \emptyset$ $\forall i \neq j$ , entonces su unión es finita y $# A_{1} \cup \dots \cup A_{t} = # A_{1} + \dots + # A_{t}$ .

Corolario

Sean $A, B$ conjuntos finitos, entonces $A \cup B$ es finito y $# A \cup B = # A + # B - # A \cap B$ .

Demostración

Sean $A$ y $B$ conjuntos finitos, y sean $n = # A$ y $m = # B .$

Observemos que

$A \cup B = A \cup (B ∖ A)$ con $A \cap (B ∖ A) = \emptyset$

y que

$B = (B ∖ A) \cup (A \cap B)$ con $(B ∖ A) \cap (A \cap B) = \emptyset$ .

Así, por el teorema anterior tenemos que:

$# A \cup B = # A + # (B ∖ A)$

$# B = # (B ∖ A) + # (A \cap B)$

Despejando $# (B ∖ A)$ de la expresión anterior tenemos que

$# (B ∖ A) = # B - # (A \cap B) .$

Sustituyendo $# B ∖ A$ en $# A \cup B = # A + # (B ∖ A)$ tenemos lo que buscábamos.

$# A \cup B = # A + # B - # A \cap B .$

Tarea Moral

1. Realiza la prueba de la equipotencia entre conjuntos para los ejemplos $3$ y $4$ e investiga las propiedades de la función tangente para entender el ejemplo $5$ .

2. En cada inciso demuestra que los siguientes conjuntos $A$ y $B$ son equipotentes:

i) $A = N$ y $B = {3, 9, 27, \dots}$ .

ii) $A = N$ y $B = {\dots, - 5, - 4, - 3}$ .

iii) $A = {x \in R ∣ x > 0}$ y $B = {x \in R ∣ x < 0}$ .

3. Demuestra que $Z$ es equipotente con el conjunto ${\dots, - 12, - 8, - 4, 0, 4, 8, 12, \dots}$ .

4. Prueba que los siguientes intervalos de recta real son equipotentes:

$(0, 1)$ y $(0, 4)$
$(0, 4)$ y $(- 6, - 2)$
$(0, 1)$ y $(0, π)$
$(0, π)$ y $(- \frac{π}{2}, \frac{π}{2})$
Reflexiona
¿El intervalo $(0, 1)$ es equipotente con cualquier intervalo $(a, b)$ con $a < b$ ?
¿Cualesquiera dos intervalos abiertos de la recta son equipotentes?

5. Prueba las siguientes propiedades de la equipotencia:

Sea $A$ un conjunto, entonces $A \sim A$ .
Sean $A$ y $B$ conjuntos, si $A \sim B$ entonces $B \sim A .$
Sean $A, B, C$ conjuntos, si $A \sim B$ y $B \sim C$ entonces $A \sim C .$

7. Sean $A$ y $B$ conjuntos finitos. Prueba que $A \sim B$ si y sólo si $# A = # B$ .

8. Sean $A$ y $B$ conjuntos finitos. Demuestra que:

Si $# A = 0$ , entonces $A = \emptyset .$
Si $A \subseteq B$ y $# A = # B$ entonces $A = B .$

9. Ve el siguiente video sobre la paradoja de los hoteles infinitos del matemático David Hilbert.

Más adelante

En la siguiente nota analizaremos el número de elementos del producto cartesiano de dos conjuntos finitos, veremos también que las funciones inyectivas (o suprayectivas) entre dos conjuntos finitos de la misma cardinalidad son también funciones suprayectivas (inyectivas respectivamente) y por lo tanto biyectivas.

Enlaces relacionados

Página principal del curso.

Nota anterior. Nota 18b. Demostraciones por inducción de las propiedades de las operaciones de los números naturales.

Nota siguiente. Nota 20. Principio del producto, funciones entre conjuntos finitos.

Nota 18. El principio de inducción matemática.

Por Julio César Soria Ramírez

2 respuestas

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota usaremos el quinto axioma de Peano para hacer un tipo de prueba muy frecuente en matemáticas cuando se quiere constatar que un subconjunto $A$ de los números naturales es de hecho igual que los números naturales, es decir que $A = N$ . Nosotros obtuvimos el quinto axioma de Peano de una definición conjuntista de los números naturales (ver la nota 16), que nos dice que si en un conjunto cualquiera de los números naturales: se cumple que el cero está y que para cualquier elemento del conjunto su sucesor también está, entonces, ese conjunto es el de los números naturales. Hay muchísimos ejemplos donde queremos garantizar que cierta propiedad se cumple para todos los números naturales, así que una forma de hacerlo es considerar la colección de todos los números naturales que cumplen dicha propiedad y usar el quinto axioma de Peano para ver que esa colección es de hecho el conjunto de todos los números naturales.

Procedamos a dar una basta serie de ejemplos donde se usa este principio, en todos ellos probaremos que un subconjunto $A$ de naturales es igual a $N$ , para ello veremos que

$i) 0 \in A$ (llamada la base de inducción), y que

$i i)$ si $n \in A$ , entonces $n^{+} = n + 1 \in A$ (llamado paso Inductivo (PI), para ello supondremos que $n \in A$ , hipótesis que se conoce comúnmente como la hipótesis de inducción (HI), y probaremos que $n + 1 \in A$ ).

Con estas dos condiciones satisfechas podemos asegurar que $A = N$ en virtud del quinto Axioma de Peano.

Ejemplos de demostraciones que usan el principio de inducción

En los siguientes ejemplos veremos cómo se usa el principio de inducción o quinto Axioma de Peano, que justificamos a partir de la definición de los números naturales.

Ejemplos

1. La suma de los primeros $n$ naturales está dada por la fórmula:

Para todo $n \in N$ , $0 + 1 + \dots + n = \frac{n (n + 1)}{2} .$

Queremos ver que la fórmula anterior se cumple para toda $n$ natural, pero hasta el momento no sabemos que así sea. Podemos entonces considerar el conjunto de naturales para los que sí se cumpla la fórmula, digamos

$A = {n \in N ∣ 0 + 1 + \dots + n = \frac{n (n + 1)}{2}} .$

Si logramos probar que en $A$ están todos los naturales, entonces habremos probado que la fórmula se cumple para todos los naturales. Una forma de hacerlo es usando el principio de inducción:

Por demostrar que $A = N .$

i) Base de inducción. Por demostrar que $0 \in A .$

$0 = \frac{0 (0 + 1)}{2}$ . Por lo tanto, $0 \in A .$

ii) Paso Inductivo. (PI).

Sea $n \in A$ , es decir, supondremos que

$0 + 1 + \dots + n = \frac{n (n + 1)}{2}$ .

Ésta es nuestra hipótesis de inducción.

Demostración de que $n^{+} = n + 1 \in A$ usando la HI.

Por demostrar que el sucesor de $n$ también está en $A$ , es decir por demostrar que $n^{+} = n + 1 \in A,$ o de modo equivalente por demostrar que

$0 + 1 + \dots + (n + 1) = \frac{(n + 1) ((n + 1) + 1)}{2} = \frac{(n + 1) (n + 2)}{2} .$

Usando la hipótesis de inducción sabemos que

$(0 + 1 + \dots + n) + (n + 1) = \frac{n (n + 1)}{2} + (n + 1) = \frac{(n) (n + 1) + 2 (n + 1)}{2} = \frac{(n + 1) (n + 2)}{2} .$

Así, $n^{+} = n + 1 \in A$ y por el principio de inducción $A = N .$

Observemos que probar que $0 \in A$ fue equivalente a probar que la fórmula que queríamos probar se cumplía para $n = 0$ . Por otro lado suponer que $n \in A$ fue equivalente a suponer que la fórmula se cumplía para $n$ , y demostramos a partir de ello que $n + 1 \in A$ verificando que la fórmula se cumplía para $n + 1$ . Así, comúnmente se omite el conjunto $A$ que consiste de todos los naturales que cumplen la propiedad que queremos verificar para todos los naturales y directamente se verifican los siguientes puntos:

$i)$ La propiedad se cumple para $n = 0$ ,

$i i)$ $\forall n \in N$ , si $n$ cumple la propiedad, entonces $n + 1$ también la cumple,

y con ello demostramos que todos los números naturales cumplen la propiedad. Veamos más ejemplos.

Para los siguientes ejemplos requerimos la definición de potencia de un natural:

Definición. Potencia en $N$

Dado $a \in N$ definimos:

$a^{0} = 1,$

para todo $m \in N$ , $a^{m + 1} = a (a^{m}) .$

Observación

Notemos que de acuerdo a la definición anterior, dado $a \in N$ se tiene que $a^{1} = a^{0 + 1} = a (a^{0}) = a (1) = a$ . Así, $a^{1} = a$ .

2. Para todo $n \in N$ , $2^{0} + 2^{1} + \dots + 2^{n} = 2^{n + 1} - 1$ .

i) Base de inducción. Veamos que el cero cumple la fórmula

$2^{0} = 1 = 2 - 1 = 2^{1} - 1 = 2^{0 + 1} - 1$ , por lo tanto la formula se cumple para $n = 0.$

ii) Paso Inductivo. (PI).

Sea $n \in N$ . Supongamos que el resultado se cumple para $n$ es decir supongamos que:

$2^{0} + 2^{1} + \dots + 2^{n} = 2^{n + 1} - 1.$

Ésta es nuestra hipótesis de inducción.

Demostración de que se cumple para $n + 1$ usando la HI.

Veamos ahora que se cumple para $n + 1$ . Usando la hipótesis de inducción

$(2^{0} + 2^{1} + \dots + 2^{n}) + 2^{n + 1} = (2^{n + 1} - 1) + 2^{n + 1} = 2 (2^{n + 1}) - 1 = 2^{(n + 1) + 1} - 1.$

Por lo tanto,

$2^{0} + 2^{1} + \dots + 2^{n} = 2^{n + 1} - 1$ , $\forall n \in N .$

3. Para todo $n \in N$ con $n \geq 2$ , $1 + 2 n < 3^{n} .$ $*$

Observa que, dado que $n \geq 2$ tenemos que $n = m + 2$ para alguna $m \in N$ , así que lo que debemos probar es equivalente a demostrar que:

Para todo $n \in N$ , $1 + 2 (m + 2) < 3^{m + 2} .$ $* *$

Para ello basta ver que

i) La propiedad ** se cumple para $m = 0$ ,

ii) Para todo $m \in N$ , si $m$ cumple la propiedad **, entonces $m + 1$ también cumple la propiedad **.

Pero el que ** se cumpla para $m + 1$ significa que $1 + 2 ((m + 1) + 2) < 3^{(m + 1) + 2}$ , es decir que $1 + 2 ((m + 2) + 1) < 3^{(m + 2) + 1}$ . Así, debemos ver que

i) La propiedad ** se cumple para $m = 0$ ,

ii) Para todo $m \in N$ , si $1 + 2 (m + 2) < 3^{m + 2}$ , entonces $1 + 2 ((m + 2) + 1) < 3^{(m + 2) + 1}$ ,

y como $n = m + 2,$ escribiendo todo en términos de $n$ esto es equivalente a probar que

i) Base de inducción. La propiedad * se cumple para $n = 2$ ,

ii) Paso Inductivo. (PI).

Para todo $n \in N$ con $n \geq 2$ , si $1 + 2 n < 3^{n}$ , entonces $1 + 2 (n + 1) < 3^{n + 1} .$

Así, cuando queramos probar una afirmación para todos los naturales a partir de un valor $k$ , bastará con realizar el proceso de inducción de la manera usual sólo que la base de inducción se trabajará con $n = k$ en vez de $n = 0$ .

Escribamos ahora sí la prueba del ejercicio:

i) Base de inducción. Para $n = 2$

$1 + 2 (0 + 2) < 3^{(0 + 2)}$ es verdadero pues

$1 + 2 (0 + 2) = 5 < 9 = 3^{2} .$

ii) Paso Inductivo. (PI).

Supongamos que el resultado se cumple para $n \geq 2$ , es decir supongamos que $1 + 2 n < 3^{n}$ .

Ésta es nuestra hipótesis de inducción.

Demostración de que se cumple para $n + 1$ usando la HI.

Veamos ahora que se cumple para $n + 1$ , es decir mostremos que $1 + 2 (n + 1) < 3^{n + 1} .$

Multiplicando la HI por $3$ tenemos que

$3 + 6 n = 3 (1 + 2 n) < 3 (3^{n}) = 3^{n + 1} .$

Basta ver que $1 + 2 (n + 1) < 3 + 6 n$ . Como $n \geq 2$ , entonces $0 < 4 n$ pero:

$0 < 4 n ⟺ 2 n < 6 n ⟺ 3 + 2 n < 3 + 6 n ⟺ 1 + 2 (n + 1) < 3 + 6 n .$

Así, $1 + 2 (n + 1) < 3 + 6 n$ .

Tenemos entonces que $1 + 2 (n + 1) < 3 + 6 n$ y que $3 + 6 n < 3^{n + 1}$ por lo que concluimos que:

$1 + 2 (n + 1) < 3^{n + 1},$

que es lo que queríamos probar.

Por lo tanto $1 + 2 (n + 1) < 3^{n + 1}$ $\forall n \in N$ , $n \geq 2$ .

A continuación enunciaremos el segundo principio de inducción y su equivalente el principio de buen orden.

Segundo principio de inducción (inducción fuerte o modificada)

Si $A \subseteq N$ es tal que:

Para toda $n$ , si para todo $m < n$ , $m \in A$ , implica que $n \in A,$

concluimos que $A = N$ .

Principio del buen orden PBO

Si $A$ es un subconjunto no vacío de $N$ , entonces $A$ tiene un elemento menor o igual a los demás. Es decir, si $A \subseteq N$ , $A \neq \emptyset$ , entonces existe $m \in A$ , tal que para todo $a \in A$ $m \leq a$ .

Nota. El segundo principio de inducción y el principio del buen orden son equivalentes y ambos se pueden probar con el principio de inducción.

Ejemplo del segundo principio de inducción

Considera la sucesión de Fibonacci:

$1, 1, 2, 3, 5, 8, \dots$

dada por

$F_{0} = F_{1} = 1,$

para todo $n \in N$ , $F_{n + 2} = F_{n} + F_{n + 1} .$

Veamos que para todo $n \in N$ , $F_{n} \leq 2^{n}$ .

Sea $n \in N .$ Supongamos que para todo $n \in N$ con $m < n,$ $F_{m} \leq 2^{m} .$

Por demostrar que

$F_{n} \leq 2^{n} .$

Si $n = 0$ o $n = 1$

$F_{0} = 1 = 2^{0}$ , $F_{1} = 1 < 2 = 2^{1}$ .

Podemos suponer entonces que $n > 1$ , así $n \geq 2.$

Entonces $n = 2 + k$ , con $k \in N$ y así

$F_{n} = F_{2 + k} = F_{k} + F_{k + 1}$ que por hipótesis de inducción es menor que $2^{k} + 2^{k + 1}$ . Concluimos que:

$\begin{aligned} F_{n} = F_{2 + k} & = F_{k} + F_{k + 1} \leq 2^{k} + 2^{k + 1} = 1 (2^{k}) + 2 (2^{k}) = 2^{k} (1 + 2) = 2^{k} (3) \\ < 2^{k} (4) = 2 (2 (2^{k})) = 2 (2^{k + 1}) = 2^{(k + 1) + 1} = 2^{k + 2} = 2^{n} . \end{aligned}$

Por lo tanto para todo $n \in N$ , $F_{n} \leq 2^{n} .$

Tarea Moral

1. Prueba que para toda $n \in N$

$\sum_{k = 0}^{n} k^{2} = \frac{n (n + 1) (2 n + 1)}{6} .$

2. Prueba que para toda $n \in N$ , $n < 2^{n} .$

3. Prueba que la suma de los ángulos internos de un polígono de $n$ lados es $(n - 2) 180$ usando inducción sobre $n$ .

4. Considera la secuencia definida de manera recursiva como:

$f_{0} = 1$ , $f_{n + 1} = f_{n} + \dots + f_{0} + 1.$

Prueba que $f_{n} = 2^{n}$ para toda $n \in N$ .

5. Sean $a, b, n, m \in N$ . Demuestra que por tinducción que:

i) $a^{n} b^{n} = (a b)^{n},$

i) $a^na^m=a^{n+m}.

Sugerencia: En el inciso $i i$ considera $n$ fija y realiza inducción sobre $m$ .

Más Adelante

Ahora que ya estamos más familiarizados con las pruebas por inducción, en la siguiente nota continuaremos usando el quinto Axioma de Peano para realizar demostraciones y probaremos de esta forma las propiedades de la suma y el producto de los números naturales.

Enlaces relacionados.

Página principal del curso.

Nota anterior. Nota 17. El orden en los números naturales.

Nota siguiente. Nota 18b. Demostraciones por inducción de las propiedades de las operaciones de los números naturales.

Nota 17. El orden en los números naturales.

Por Julio César Soria Ramírez

Deja un comentario

(Trabajo de titulación asesorado por la Dra. Diana Avella Alaminos)

Introducción

En esta nota continuaremos con el estudio de las propiedades de los números naturales y desarrollaremos formalmente el concepto de cuándo un número natural es más grande que otro, es decir daremos un orden en el conjunto de los números naturales que acabamos de construir, a partir del cual podremos decir cuándo un número natural es más grande que otro.

Procedamos a dar la definición formal del orden en los números naturales.

Definición. Orden en $N$ .

Sean $n, m \in N$ .

Decimos que $n$ es menor que $m$ , si existe $x \in N$ , $x \neq 0$ , tal que:

$n + x = m .$

Lo denotaremos por $n < m$ (o por $m > n$ ).

Decimos que $n$ es menor o igual que $m$ , si existe $x \in N$ , tal que:

$n + x = m .$

Lo denotaremos por $n \leq m$ (o por $m \geq n$ ).

En ambos casos, le llamaremos al natural $x$ la diferencia de $m$ con $n$ y lo denotaremos por $m - n$ .

Observación 1

Si $n \in N$ con $n \neq 0$ , entonces $n > 0$ .

Demostración: Si $n \in N$ y $n \neq 0$ , tenemos que $0 + n = n$ , con $n \in N$ , $n \neq 0$ , por lo tanto, $0 < n$ .

Observación 2

Para toda $n \in N$ , $n < n^{+}$ .

Demostración: Dada $n \in N$ , como $n + 1 = n^{+}$ (por la observación 3 de la nota previa) con $1 \in N$ (por el tercer Axioma de Peano), $1 \neq 0$ , por lo tanto $n < n^{+}$ .

Observación 3

Si $n \in N$ , con $n \neq 0$ , entonces $n \geq 1$ .

Demostración: De acuerdo a un ejercicio de la tarea moral de la nota previa, si $n \in N$ , entonces $n = 0$ o $n = m^{+}$ con $m \in N$ . De esta forma si $n \in N$ y $n \neq 0$ , entonces $n = m^{+} = m + 1$ para alguna $m \in N$ y se concluye que $n \geq 1$ .

Notación

Denotaremos por $N^{+}$ al conjunto de números naturales distintos de cero, es decir $N^{+} = {n \in N ∣ n \geq 1} .$

Notación

En ocasiones simplificaremos la notación del producto de los naturales y escribiremos $n m$ en lugar de $n \cdot m$ , para cualesquiera $n, m \in N .$

Propiedades de Orden en $N$

Sean $n, m, l \in N$

Si $n < m$ y $m < l$ , entonces $n < l$ . Esta es la propiedad transitiva.
Si $n < m$ , entonces $n + l < m + l$ .
Si $n < m$ y $l \neq 0$ , entonces $n l < m l$ .
Se cumple una y sólo una de las siguientes condiciones:
$n < m$ , $n = m$ o $n > m$
A este hecho se le conoce como tricotomía.
Si $n + l < m + l$ , entonces $n < m$ .
Si $n l < m l$ , entonces $n < m$ .

Demostración

Demostración de 1

Por demostrar que si $n < m$ y $m < l$ , entonces $n < l$ .

Supongamos que $n < m$ y que $m < l$ , entonces existen $x, y \in N$ , $x \neq 0$ , $y \neq 0$ tales que:

$n + x = m$

$m + y = l .$

Así, $n + (x + y) = (n + x) + y = m + y = l$ , con $x, y \in N$ . Además, por las propiedades de la suma de los naturales, como $x \neq 0$ y $y \neq 0$ se tiene que $x + y \neq 0$ . Por lo tanto $n < l$ .

Demostración de 2

Por demostrar que si $n < m$ , entonces $n + l < m + l$ .

Supongamos que $n < m$ , entonces existe $x \in N$ , $x \neq 0$ tal que $n + x = m$ .

Por las propiedades de la suma $(n + l) + x = (n + x) + l = m + l$ con $x \in N$ , $x \neq 0$ y por lo tanto $n + l < m + l$ .

Demostración de 3

Por demostrar que si $n < m$ y $l \neq 0$ , entonces $n l < m l$ .

Supongamos que $n < m$ y $l \neq 0$ . Existe $x \in N$ , $x \neq 0$ tal que $n + x = m$ .

Por las propiedades de las operaciones de los naturales $n l + x l = (n + x) l = m l$ con $x l \in N$ . Además, debido a las propiedades del producto de los naturales, como $x \neq 0$ y $l \neq 0$ tenemos que $x l \neq 0$ . Por lo tanto $n l < m l$ .

Demostración de 4

La prueba se realiza por inducción pero en la nota 18b se dejará revisarla a manera de ejercicio debido a que preferimos estudiar primero las pruebas por inducción en casos más concretos con el fin de que se entiendan con mayor claridad.

Demostración de 5

Por demostrar que si $n + l < m + l$ , entonces $n < m$ .

Supongamos que $n + l < m + l .$

Por la propiedad $4$ sabemos que sólo pasa alguna de estas tres situaciones:

$n < m$ , $n = m$ o $n > m .$

Si $n = m$ , entonces se tiene que $n + l = m + l$ , lo cual contradice nuestra hipótesis.

Si $n > m$ , entonces por la propiedad $2$ se tiene que $n + l > m + l$ , lo cual contradice la hipótesis.

Así, la única posibilidad es que $n < m$ .

Demostración de 6

Por demostrar que si $n l < m l$ entonces $n < m$ .

Supongamos que $n l < m l$ , por $4$ sabemos que $n < m$ , $n = m$ o $n > m$ .

Si $n = m$ entonces $n l = m l$ , lo cual contradice la hipótesis.

Si $n > m$ y $l = 0$ tendríamos que $n l = m l$ , por otro lado si $n > m$ y $l > 0$ , tendríamos que $n l < m l$ por la propiedad $3$ . En cualquier caso esto es una contradicción a nuestra hipótesis.

Así, la única posibilidad es que $n < m$ .

Tarea Moral

1. Sean $n, m \in N$ . Prueba que si $n \geq 2$ y $m \geq 2$ , entonces $n + m \leq n m$ .

2. Sea $n, m, l, t \in N$ , prueba o da un contraejemplo para las siguientes afirmaciones:

i) Si $n < l$ y $m < t$ , entonces $n + m < l + t$ .

ii) Si $n < l$ y $m < t$ , entonces $n m < l t$ .

iii) Si $n < l$ y $m < t$ , entonces $n + m < l t$ .

Más adelante

En la siguiente nota explicaremos con detalle cómo aplicar el quinto axioma de Peano para hacer pruebas por inducción. En dichas pruebas se garantiza que un subconjunto de los números naturales es de hecho el de todos los naturales y con ello se justifica que alguna propiedad se cumple para todos los números naturales.

Enlaces relacionados

Página principal del curso.

Nota anterior. Nota 16 Los números naturales.

Nota siguiente. Nota 18. El principio de inducción matemática.

Introducción

Definición

Teorema

Tarea moral

Más adelante

Enlaces relacionados

Introducción

Lema 1

Teorema. Principio del producto

Lema 2

Teorema

Tarea moral

Más adelante

Enlaces relacionados

Introducción

Definición

Definición

Teorema: principio de la suma.

Corolario

Tarea Moral

Más adelante

Enlaces relacionados

Introducción

Ejemplos de demostraciones que usan el principio de inducción

Definición. Potencia en N

Observación

Segundo principio de inducción (inducción fuerte o modificada)

Principio del buen orden PBO

Tarea Moral

Más Adelante

Enlaces relacionados.

Introducción

Definición. Orden en N .

Propiedades de Orden en N

Tarea Moral

Más adelante

Enlaces relacionados

Definición. Potencia en $N$

Definición. Orden en $N$ .

Propiedades de Orden en $N$