¿Qué es un conjunto?
Un conjunto es una colección bien definida de objetos de una misma especie. Esos objetos se llaman elementos del conjunto. La idea de "bien definida" es clave: dado cualquier objeto, debe ser posible determinar sin ambigüedad si pertenece o no al conjunto.
Convenciones de notación: los conjuntos se denotan con letras mayúsculas (A, B, C, …) y los elementos con letras minúsculas (a, b, x, …).
Formas de definir un conjunto
Hay tres formas principales de describir un conjunto:
- Por extensión: se listan todos los elementos entre llaves, separados por comas. Ejemplo: A = {2, 4, 6, 8}.
- Por comprensión: se indica una propiedad característica que cumplen exactamente los elementos del conjunto. Ejemplo: A = {x / x es un número par positivo menor que 9}.
- Por diagrama de Venn: se dibuja una curva cerrada (generalmente una elipse) y dentro se colocan los elementos. El conjunto universal se representa como un rectángulo que contiene todo.
Extensión vs. comprensión
Mismo conjunto, dos formas de escribirlo:
- Por extensión: A = {a, e, i, o, u}
- Por comprensión: A = {x / x es una letra vocal del español}
Otro ejemplo con números:
- B = {1, 4, 9, 16, 25}
- B = {x ∈ ℕ / x es un cuadrado perfecto y x ≤ 25}
Cardinal de un conjunto
El cardinal de un conjunto A es la cantidad de elementos que tiene, y se denota |A|. Si el conjunto tiene infinitos elementos, escribimos |A| = ∞.
Cardinales
- A = {a, e, i, o, u} → |A| = 5
- B = {2, 4, 6, 8} → |B| = 4
- ℕ = {0, 1, 2, 3, …} → |ℕ| = ∞
Conjunto vacío y conjunto universal
Conjunto vacío (∅)
El conjunto vacío es aquel que no tiene ningún elemento. Se denota ∅ o también {}. Puede definirse mediante una contradicción: ∅ = {x / x ≠ x} (ningún elemento puede ser distinto de sí mismo, así que no hay ningún elemento que satisfaga esa condición).
¡Cuidado! ∅ ≠ {∅}
El conjunto vacío ∅ no tiene elementos. En cambio, {∅} es un conjunto que tiene un elemento: el conjunto vacío. Es como una bolsa vacía vs. una bolsa que contiene otra bolsa vacía. La segunda bolsa tiene algo adentro (la bolsa interior), por más que esa bolsa interior esté vacía.
Por lo tanto: |∅| = 0 pero |{∅}| = 1.
Conjunto universal (U)
El conjunto universal (o referencial) es el que contiene todos los elementos del universo de discurso que estamos considerando. Se denota U. Puede definirse como U = {x / x = x} (todo elemento es igual a sí mismo). En diagramas de Venn se representa como un rectángulo que contiene todo.
Conjunto universal según el contexto
- Si trabajamos con números enteros: U = ℤ
- Si trabajamos con letras: U = {a, b, c, …, z}
- Si queremos estudiar subconjuntos de A = {1,2,3}: podemos tomar U = {0,1,2,3,4,5,6,7,8,9}
Pertenencia e inclusión
Relación de pertenencia (∈)
La pertenencia es una relación entre un elemento y un conjunto. Decimos que el elemento x pertenece al conjunto A, y escribimos x ∈ A. Si no pertenece, escribimos x ∉ A.
Pertenencia en los números
Usando los conjuntos numéricos estándar:
- -2 ∉ ℕ (los naturales no incluyen negativos)
- 0,75 ∈ ℝ (es un real, aunque no es entero)
- √2 ∉ ℚ (la raíz de 2 no es racional)
- 169 ∈ ℤ (169 = 13², es entero)
- ∅ ∉ ℤ (el conjunto vacío no es un número entero)
Pertenencia vs. inclusión: error muy frecuente
La pertenencia ∈ relaciona un elemento con un conjunto. La inclusión ⊆ relaciona dos conjuntos. Son relaciones distintas y no son intercambiables.
- 3 ∈ {1, 2, 3} — correcto (3 es un elemento)
- {3} ⊆ {1, 2, 3} — correcto ({3} es un subconjunto)
- {3} ∈ {1, 2, 3} — FALSO ({3} no es un elemento de ese conjunto)
- 3 ⊆ {1, 2, 3} — no tiene sentido (3 es un número, no un conjunto)
Relación de inclusión (⊆)
La inclusión es una relación entre dos conjuntos. Decimos que A está incluido en B (o que A es subconjunto de B) cuando todo elemento de A también pertenece a B. Formalmente:
A ⊆ B ⟺ ∀x: [x ∈ A → x ∈ B]
Si A no está incluido en B, escribimos A ⊄ B. Hay un elemento de A que no está en B.
Inclusión estricta (⊊)
Decimos que A está estrictamente incluido en B (notación A ⊊ B o a veces A ⊂ B) cuando A ⊆ B y además A ≠ B. Es decir, A está dentro de B pero B tiene al menos un elemento que A no tiene.
Inclusión e inclusión estricta
Sean X = {a, e, i, o, u}, Y = {a, e, o}, Z = {a, b}.
- Y ⊆ X: verdadero (a, e, o están todos en X)
- Y ⊊ X: verdadero (además, X tiene i y u que Y no tiene)
- Z ⊆ X: falso (la b no está en X)
- X ⊆ X: siempre verdadero (todo conjunto se incluye en sí mismo)
- ∅ ⊆ X: siempre verdadero (el vacío está incluido en todo conjunto)
Propiedades básicas de la inclusión
| Propiedad | Enunciado |
| Reflexiva | ∀A: A ⊆ A |
| Vacío | ∀A: ∅ ⊆ A |
| Universal | ∀A: A ⊆ U |
| Transitiva | A ⊆ B ∧ B ⊆ C → A ⊆ C |
Igualdad de conjuntos
Dos conjuntos son iguales cuando tienen exactamente los mismos elementos. Formalmente, la igualdad se define como inclusión mutua:
A = B ⟺ A ⊆ B ∧ B ⊆ A
Esto es fundamental para demostrar igualdades de conjuntos: hay que demostrar las dos inclusiones por separado.
Para demostrar A = B
La estrategia estándar es demostrar las dos inclusiones:
- Primera inclusión: tomar un x ∈ A arbitrario y demostrar que x ∈ B.
- Segunda inclusión: tomar un x ∈ B arbitrario y demostrar que x ∈ A.
Si todos los pasos son bicondicionales (⟺), se pueden hacer ambas inclusiones en una sola cadena.
Operaciones entre conjuntos
Dados dos conjuntos A y B (dentro de un universal U), se definen las siguientes operaciones:
| Operación | Símbolo | Definición formal | Significado intuitivo |
| Unión | A ∪ B | {x / x ∈ A ∨ x ∈ B} | Lo que está en A, en B, o en ambos |
| Intersección | A ∩ B | {x / x ∈ A ∧ x ∈ B} | Lo que está en A y también en B |
| Diferencia | A − B | {x / x ∈ A ∧ x ∉ B} | Lo que está en A pero no en B |
| Complemento | Ā | {x ∈ U / x ∉ A} = U − A | Todo lo que no está en A (dentro del universo) |
| Dif. simétrica | A △ B | (A − B) ∪ (B − A) | Lo que está en uno solo de los dos |
Operaciones con conjuntos concretos
Sea U = {1,2,3,4,5,6,7,8,9,10}, A = {1,2,3,4,5}, B = {2,4,6}.
- A ∪ B = {1,2,3,4,5,6}
- A ∩ B = {2,4}
- A − B = {1,3,5}
- B − A = {6}
- Ā = {6,7,8,9,10}
- B̄ = {1,3,5,7,8,9,10}
- A △ B = {1,3,5,6} (lo que está solo en A o solo en B)
Nótese: A ∩ C = ∅ cuando C = {7}. Decimos que A y C son disjuntos.
Equivalencia de la diferencia
Una propiedad muy usada en demostraciones: A − B = A ∩ B̄. La diferencia A−B se puede expresar como la intersección de A con el complemento de B. Esto permite pasar de diferencias a intersecciones y viceversa, lo que suele facilitar las cuentas.
Conjuntos disjuntos
Dos conjuntos A y B son disjuntos cuando A ∩ B = ∅, es decir, no tienen ningún elemento en común.
Diagramas de Venn
Los diagramas de Venn son representaciones gráficas de conjuntos y sus operaciones. Se dibuja un rectángulo para el universo U, y dentro del rectángulo se dibujan elipses o círculos para cada conjunto. Las regiones resultantes representan las distintas combinaciones.
Para dos conjuntos A y B, el diagrama tiene cuatro regiones posibles:
- Solo en A: A − B
- En A y en B: A ∩ B
- Solo en B: B − A
- En ninguno: Ā ∩ B̄
Los diagramas son útiles para visualizar, pero no son demostraciones formales. Para demostrar propiedades, se trabaja a nivel de elementos o con propiedades ya demostradas.
Propiedades de las operaciones entre conjuntos
| # | Nombre | Unión | Intersección |
| 1 | Involución | Ā̄ = A (complemento del complemento es el original) |
| 2 | Conmutativa | A ∪ B = B ∪ A | A ∩ B = B ∩ A |
| 3 | Asociativa | A ∪ (B ∪ C) = (A ∪ B) ∪ C | A ∩ (B ∩ C) = (A ∩ B) ∩ C |
| 4 | Distributiva | A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) | A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) |
| 5 | Idempotencia | A ∪ A = A | A ∩ A = A |
| 6 | De Morgan | A ∪ B̄ = Ā ∩ B̄ | A ∩ B̄ = Ā ∪ B̄ |
| 7 | Neutro / Absorbente | A ∪ ∅ = A · A ∪ U = U | A ∩ U = A · A ∩ ∅ = ∅ |
| 8 | Absorción | A ∪ (A ∩ B) = A | A ∩ (A ∪ B) = A |
| 9 | Complementación | A ∪ Ā = U | A ∩ Ā = ∅ |
| 10 | Equiv. diferencia | A − B = A ∩ B̄ |
Leyes de De Morgan para conjuntos
Las leyes de De Morgan son las más importantes para simplificar expresiones con complementos:
A ∪ B̄ = Ā ∩ B̄ (complemento de la unión = intersección de complementos)
A ∩ B̄ = Ā ∪ B̄ (complemento de la intersección = unión de complementos)
Son análogas a las leyes de De Morgan de la lógica proposicional, con ∪ ↔ ∨ e ∩ ↔ ∧.
Ejemplo de demostración de propiedad (nivel de elementos)
Demostración: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Para demostrar la igualdad demostramos dos inclusiones. Como todos los pasos son bicondicionales, los hacemos juntos:
∀x:
x ∈ A ∩ (B ∪ C)
⟺ x ∈ A ∧ x ∈ (B ∪ C) — por definición de intersección
⟺ x ∈ A ∧ (x ∈ B ∨ x ∈ C) — por definición de unión
⟺ (x ∈ A ∧ x ∈ B) ∨ (x ∈ A ∧ x ∈ C) — por distributiva de ∧ sobre ∨ (lógica)
⟺ x ∈ (A ∩ B) ∨ x ∈ (A ∩ C) — por definición de intersección
⟺ x ∈ (A ∩ B) ∪ (A ∩ C) — por definición de unión
Como todos los pasos son ⟺, queda demostrada la igualdad en ambas inclusiones. ∎
Demostración: A − (B ∩ C) = (A − B) ∪ (A − C)
∀x:
x ∈ A − (B ∩ C)
⟺ x ∈ A ∧ x ∉ (B ∩ C) — definición de diferencia
⟺ x ∈ A ∧ ¬(x ∈ B ∧ x ∈ C) — definición de intersección
⟺ x ∈ A ∧ (x ∉ B ∨ x ∉ C) — De Morgan lógico
⟺ (x ∈ A ∧ x ∉ B) ∨ (x ∈ A ∧ x ∉ C) — distributiva
⟺ x ∈ (A − B) ∨ x ∈ (A − C) — definición de diferencia
⟺ x ∈ (A − B) ∪ (A − C) — definición de unión ∎
No suponer la tesis verdadera antes de probarla
Un error clásico al demostrar igualdades de conjuntos es escribir lo que hay que demostrar como si ya fuera verdad, y luego "verificarlo". Eso es razonamiento circular.
La forma correcta: partir de un miembro (por ejemplo el lado izquierdo) y llegar al otro mediante pasos justificados por definiciones o propiedades ya conocidas.
Conjunto de partes P(A)
Dado un conjunto A, el conjunto de partes de A (también llamado conjunto potencia) es el conjunto formado por todos los subconjuntos de A:
P(A) = {X / X ⊆ A}
Observar que tanto ∅ como A siempre están en P(A) (el conjunto vacío es subconjunto de todo conjunto, y todo conjunto es subconjunto de sí mismo).
Conjuntos de partes
- A = {a, b} → P(A) = {∅, {a}, {b}, {a,b}}, con |P(A)| = 4
- B = {1, 2, 3} → P(B) = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}, con |P(B)| = 8
- C = {m} → P(C) = {∅, {m}}, con |P(C)| = 2
- D = ∅ → P(D) = {∅}, con |P(D)| = 1
Cardinalidad de P(A)
Si |A| = n (finito), entonces |P(A)| = 2n.
¿Por qué? Para construir un subconjunto de A, cada elemento tiene dos opciones: está o no está en el subconjunto. Con n elementos independientes, son 2 × 2 × … × 2 (n veces) = 2n subconjuntos posibles.
Ejemplo: si |A| = 4, entonces |P(A)| = 24 = 16.
P(A) vs. partición vs. elemento de A
Los elementos de P(A) son conjuntos (los subconjuntos de A), no elementos de A. Si A = {1, 2}:
- {1} ∈ P(A) — verdadero ({1} es un subconjunto de A)
- 1 ∈ P(A) — FALSO (1 no es un subconjunto de A, es un elemento)
- {1} ⊆ A — verdadero
- 1 ⊆ A — no tiene sentido (1 no es un conjunto)
Familias de conjuntos y operaciones generalizadas
Una familia de conjuntos es un conjunto cuyos elementos son conjuntos. Cuando tenemos una familia indexada {A1, A2, …, An}, podemos generalizar las operaciones de unión e intersección:
∪i=1n Ai = A1 ∪ A2 ∪ … ∪ An = {x / ∃i ∈ {1,…,n}: x ∈ Ai}
∩i=1n Ai = A1 ∩ A2 ∩ … ∩ An = {x / ∀i ∈ {1,…,n}: x ∈ Ai}
Estas operaciones generalizadas son fundamentales cuando se trabaja con inducción sobre conjuntos (ver más adelante la demostración del Ej. 15).
Particiones de un conjunto
Sea A ≠ ∅. Un conjunto P = {A1, A2, …, An} es una partición de A si cumple las tres condiciones siguientes simultáneamente:
- Ai ≠ ∅ para todo i — ninguna celda está vacía
- Ai ∩ Aj = ∅ para todo i ≠ j — las celdas son disjuntas entre sí
- A1 ∪ A2 ∪ … ∪ An = A — la unión de todas las celdas es el conjunto original
Los subconjuntos Ai se llaman celdas de la partición. En palabras: partir A es dividirlo en partes no vacías, sin traslapes, que juntas cubren todo A.
¿Cuál es partición de A = {a, b, c, d, e}?
- P1 = {{a,b,c}, {d,e}} — SÍ es partición (celdas no vacías, disjuntas, cubren A)
- P2 = {{a,b}, {c,d}, {b,e}} — NO: b aparece en dos celdas (falla condición 2)
- P3 = {{a,b}, {c}, {e}} — NO: d no aparece en ninguna celda (falla condición 3)
- P4 = {{a}, {b}, {c}, {d,e}} — SÍ es partición
- P5 = {{a}, {b,c,d}, {∅}, {e}} — NO: ∅ es una celda vacía (falla condición 1)
Partición vs. conjunto de partes
Diferencia fundamental:
- P(A) contiene todos los subconjuntos de A, incluyendo ∅ y A mismo. Es uno solo.
- Una partición de A es una colección de subconjuntos de A que cumple las tres condiciones. Excluye ∅ como celda. Puede haber muchas particiones distintas de A.
Las particiones de un conjunto se vinculan íntimamente con las relaciones de equivalencia (tema de la Unidad 3).
Producto cartesiano A × B
Dados dos conjuntos A y B, el producto cartesiano de A por B es el conjunto de todos los pares ordenados (x, y) donde la primera componente x viene de A y la segunda componente y viene de B:
A × B = {(x, y) / x ∈ A ∧ y ∈ B}
El orden importa: (x, y) ≠ (y, x) en general (a menos que x = y). Por eso se llama "par ordenado".
Producto cartesiano concreto
Sean A = {m, p, h} y B = {1, 2}:
A × B = {(m,1), (m,2), (p,1), (p,2), (h,1), (h,2)}
B × A = {(1,m), (2,m), (1,p), (2,p), (1,h), (2,h)}
Claramente A × B ≠ B × A (el producto cartesiano no es conmutativo).
Cardinal del producto cartesiano
Si |A| = n y |B| = m, entonces |A × B| = n · m.
Tiene sentido: hay n elecciones para la primera componente y m para la segunda, independientemente.
Casos especiales: si A = ∅ o B = ∅, entonces A × B = ∅.
Propiedades del producto cartesiano
El producto cartesiano distribuye sobre la unión e intersección:
- A × (B ∪ C) = (A × B) ∪ (A × C) — distribución sobre ∪
- A × (B ∩ C) = (A × B) ∩ (A × C) — distribución sobre ∩
- A × B = ∅ ⟺ A = ∅ ∨ B = ∅
Ejemplo de distribución: Si A = {0,1}, B = {1,2}, C = {2,3}:
A × (B ∪ C) = {0,1} × {1,2,3} = {(0,1),(0,2),(0,3),(1,1),(1,2),(1,3)}
(A × B) ∪ (A × C) = {(0,1),(0,2),(1,1),(1,2)} ∪ {(0,2),(0,3),(1,2),(1,3)} = {(0,1),(0,2),(0,3),(1,1),(1,2),(1,3)}
Coinciden.
Cardinalidad de conjuntos finitos y principio de inclusión-exclusión
Para conjuntos finitos, el cardinal (cantidad de elementos) satisface reglas importantes cuando se opera con ellos.
Principio de inclusión-exclusión para dos conjuntos
Si sumamos |A| + |B|, los elementos que están en A ∩ B los contamos dos veces. Hay que restar una vez esa intersección:
|A ∪ B| = |A| + |B| − |A ∩ B|
Principio de inclusión-exclusión para tres conjuntos
Análogamente, para tres conjuntos sumamos los individuales, restamos los de a pares (que se contaron doble), y sumamos la intersección triple (que se sobre-corrigió):
|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
Problema de inclusión-exclusión: lectores
Sobre un grupo de 45 personas: 16 leen novelas (N), 18 leen ciencia ficción (CF), 17 leen cuentos (Cu). Además: 3 leen los tres géneros, 1 lee solo cuentos y CF, 8 leen solo cuentos, 4 leen solo N y CF.
Datos que interpretamos como intersecciones exclusivas o totales:
- |N ∩ CF ∩ Cu| = 3
- "Solo Cu y CF" (sin N): |Cu ∩ CF| − |N ∩ CF ∩ Cu| = 1 → |Cu ∩ CF| = 4
- "Solo N y CF" (sin Cu): |N ∩ CF| − 3 = 4 → |N ∩ CF| = 7
- Por PIE: |N ∪ CF ∪ Cu| = 16 + 18 + 17 − 7 − |N ∩ Cu| − 4 + 3
Calculando con todos los datos, resulta que 10 personas no leen ningún género.
Ejercicio 1 del teórico: A, B, C sobre ℤ
Sea A = {x ∈ ℤ / x² < 10} = {-3,-2,-1,0,1,2,3},
B = {x ∈ ℤ / |x−2| ≤ 3} = {-1,0,1,2,3,4,5},
C = {x ∈ ℕ / x es divisor de 8} = {1,2,4,8}.
- A ∩ B = {-1,0,1,2,3}
- A ∩ C = {1,2}
- B ∩ C = {1,2,4}
- A ∩ B ∩ C = {1,2}
- A − B = {-3,-2}
- B − A = {4,5}
- Con U = {x ∈ ℤ / |x| ≤ 8}: Ā = {-8,-7,-6,-5,-4,4,5,6,7,8}
Conjuntos numéricos
Los conjuntos de números estándar forman una cadena de inclusiones. Cada uno está contenido en el siguiente:
ℕ ⊊ ℤ ⊊ ℚ ⊊ ℝ ⊊ ℂ
| Símbolo | Nombre | Descripción | Ejemplos |
| ℕ | Naturales | Enteros no negativos (con 0 en UTN) | 0, 1, 2, 3, … |
| ℤ | Enteros | Naturales + negativos | …, -2, -1, 0, 1, 2, … |
| ℚ | Racionales | Cocientes p/q con p ∈ ℤ, q ∈ ℤ, q ≠ 0 | 1/2, -3/4, 0,333… |
| ℝ | Reales | Racionales + irracionales | √2, π, e, -7,5 |
| ℂ | Complejos | a + bi con a,b ∈ ℝ, i = √(−1) | 3+2i, -1, 0+5i |
Los irracionales son los reales que no se pueden expresar como cociente de enteros: √2, √3, π, e, etc. El conjunto de irracionales es ℝ \ ℚ.
¿El 0 pertenece a ℕ?
Hay convenciones distintas según el texto o la cátedra. En Matemática Discreta UTN (Cátedra Piñeiro), se considera ℕ = {0, 1, 2, 3, …} (con el 0 incluido). Verificar siempre la convención de la cátedra antes de responder.
Inducción matemática completa
La inducción matemática es una técnica de demostración que nos permite probar que una proposición p(n) es verdadera para todos los naturales (o para todos los naturales a partir de un cierto valor m).
¿Por qué necesitamos inducción?
Verificar un caso particular, o incluso mil casos, no prueba que algo vale para todos los naturales. Por ejemplo, observar que la suma de los primeros k impares es k² para k = 1, 2, 3, 4, 5 no basta para asegurar que vale para k = 1000. La inducción matemática sí nos da esa certeza.
Motivación: suma de impares
Calculemos: 1 = 1², 1+3 = 4 = 2², 1+3+5 = 9 = 3², 1+3+5+7 = 16 = 4².
Parece que 1 + 3 + 5 + … + (2n−1) = n². Pero ¿es siempre así? Para probarlo con certeza usamos inducción.
Principio de Inducción Completa (PIC)
Sea p(n) un predicado con dominio en ℕ. Si se cumplen:
- Caso base: v[p(1)] = V (la proposición es verdadera para n = 1)
- Paso inductivo: ∀h ∈ ℕ: v[p(h)] = V → v[p(h+1)] = V
Entonces p(n) es verdadera para todo n ∈ ℕ.
Estructura obligatoria de una demostración por inducción
Toda demostración por inducción debe tener exactamente esta estructura:
- Enunciar p(n) claramente.
- Paso base: verificar p(1) (o p(m) si el enunciado empieza desde m).
- Paso inductivo:
- Hipótesis inductiva (HI): suponer p(h) verdadera para algún h arbitrario.
- Tesis inductiva (TI): lo que hay que demostrar: p(h+1).
- Demostración: partiendo del primer miembro de TI, usar HI en algún paso y llegar al segundo miembro.
- Conclusión: "Por el Principio de Inducción, p(n) es verdadera para todo n ∈ ℕ."
Los 3 errores más frecuentes en inducción
- Olvidar el caso base: el paso inductivo solo dice "si p(h) entonces p(h+1)". Sin el caso base, la cadena no empieza. Es como afirmar "si la ficha k cae, la k+1 también cae" sin tirar la primera ficha.
- Usar la tesis en la demostración: durante el paso inductivo, la TI es lo que queremos demostrar, no lo que podemos asumir. Solo la HI (p(h)) puede usarse como hipótesis. Usar la TI como verdadera antes de probarla es razonamiento circular.
- Verificar un caso particular y creer que vale en general: demostrar que p(5) es verdadera no implica que p(n) sea verdadera para todo n. Para eso se necesita el argumento completo de inducción.
Demostraciones por inducción — Ejemplos completos
Ejemplo 1: Suma de los primeros n naturales
Demostrar: ∀n ∈ ℕ, n ≥ 1: 1 + 2 + 3 + … + n = n(n+1)/2
p(n): ∑k=1n k = n(n+1)/2
Paso base (n=1):
Primer miembro: 1. Segundo miembro: 1·(1+1)/2 = 1. Coinciden → v[p(1)] = V. ✓
Paso inductivo:
HI: 1 + 2 + … + h = h(h+1)/2 (suponemos esto verdadero para algún h ∈ ℕ arbitrario)
TI: 1 + 2 + … + h + (h+1) = (h+1)(h+2)/2 (esto es lo que hay que demostrar)
Dem.: Partimos del primer miembro de la TI:
1 + 2 + … + h + (h+1)
= (1 + 2 + … + h) + (h+1) — asociativa
= h(h+1)/2 + (h+1) — aplicamos la HI
= (h+1) · [h/2 + 1] — sacamos factor común (h+1)
= (h+1) · (h+2)/2 — simplificamos
Llegamos al segundo miembro de TI. ✓
Conclusión: Por el Principio de Inducción Completa, la propiedad p(n) es verdadera para todo n ∈ ℕ, n ≥ 1. ∎
Ejemplo 2: Suma de los primeros n números impares
Demostrar: ∀n ∈ ℕ: 1 + 3 + 5 + … + (2n−1) = n²
p(n): ∑k=1n (2k−1) = n²
Paso base (n=1):
Primer miembro: 2·1−1 = 1. Segundo miembro: 1² = 1. → v[p(1)] = V. ✓
Paso inductivo:
HI: 1 + 3 + … + (2h−1) = h²
TI: 1 + 3 + … + (2h−1) + (2(h+1)−1) = (h+1)², o sea 1 + 3 + … + (2h+1) = (h+1)²
Dem.:
1 + 3 + … + (2h−1) + (2h+1)
= [1 + 3 + … + (2h−1)] + (2h+1) — asociativa
= h² + (2h+1) — aplicamos HI
= h² + 2h + 1
= (h+1)² — cuadrado de binomio
Llegamos al segundo miembro de TI. ✓
Conclusión: Por PIC, p(n) es verdadera para todo n ∈ ℕ. ∎
Ejemplo 3: Suma de potencias de 2
Demostrar: ∀n ∈ ℕ₀: 2⁰ + 2¹ + 2² + … + 2ⁿ = 2ⁿ⁺¹ − 1
Motivación: S₁=1, S₂=3, S₃=7, S₄=15, … siempre una unidad menos que la siguiente potencia de 2.
p(n): ∑i=0n 2i = 2n+1 − 1
Paso base (n=0):
Primer miembro: 2⁰ = 1. Segundo miembro: 2¹ − 1 = 1. → v[p(0)] = V. ✓
Paso inductivo:
HI: 2⁰ + 2¹ + … + 2ʰ = 2ʰ⁺¹ − 1
TI: 2⁰ + 2¹ + … + 2ʰ + 2ʰ⁺¹ = 2ʰ⁺² − 1
Dem.:
2⁰ + 2¹ + … + 2ʰ + 2ʰ⁺¹
= (2⁰ + 2¹ + … + 2ʰ) + 2ʰ⁺¹ — asociativa
= (2ʰ⁺¹ − 1) + 2ʰ⁺¹ — aplicamos HI
= 2 · 2ʰ⁺¹ − 1 — juntamos los dos términos iguales
= 2ʰ⁺² − 1 — propiedad de potencias (a · aⁿ = aⁿ⁺¹)
Llegamos al segundo miembro de TI. ✓ ∎
Ejemplo 4: Demostración por inducción con divisibilidad
Demostrar: ∀n ∈ ℕ: 23n − 18n es divisible por 5
p(n): ∃k ∈ ℤ: 23n − 18n = 5k
Paso base (n=1):
23·1 − 18·1 = 23 − 18 = 5 = 5·1, y 1 ∈ ℤ. → v[p(1)] = V. ✓
Paso inductivo:
HI: 23h − 18h = 5k para algún k ∈ ℤ
TI: 23(h+1) − 18(h+1) = 5t para algún t ∈ ℤ (notar: t no tiene por qué ser el mismo k)
Dem.:
23(h+1) − 18(h+1)
= 23h · 23 − 18h · 18 — propiedades de potencias
= 23h · (5 + 18) − 18h · 18 — escribimos 23 = 5 + 18 (truco clave)
= 5 · 23h + 18 · 23h − 18h · 18 — distributiva
= 5 · 23h + 18 · (23h − 18h) — sacamos factor 18
= 5 · 23h + 18 · 5k — aplicamos HI
= 5 · (23h + 18k) — sacamos factor 5
= 5t, donde t = 23h + 18k ∈ ℤ (suma y producto de enteros es entero). ✓
Conclusión: Por PIC, 23n − 18n es divisible por 5 para todo n ∈ ℕ. ∎
Ejemplo 5: Desigualdad por inducción
Demostrar: ∀n ∈ ℕ, n ≥ 4: 2n < n!
Observación: El enunciado empieza en n = 4 (para n = 1, 2, 3 es falso: 2 < 1! es falso, etc.). El caso base es n = 4.
Paso base (n=4):
Primer miembro: 2⁴ = 16. Segundo miembro: 4! = 24. Como 16 < 24 → v[p(4)] = V. ✓
Paso inductivo:
HI: 2h < h! (para algún h ≥ 4)
TI: 2h+1 < (h+1)!
Dem.:
2h+1 = 2 · 2h — propiedad de potencias
< 2 · h! — por HI (2h < h!), y como 2 > 0 la desigualdad se mantiene
≤ (h+1) · h! — porque h+1 ≥ 2 cuando h ≥ 4 ≥ 1 (se cumple h+1 ≥ 2)
= (h+1)! — definición de factorial
Entonces 2h+1 < (h+1)!. ✓
Conclusión: Por PIC (con base en n = 4), p(n) es verdadera para todo n ∈ ℕ, n ≥ 4. ∎
Truco para divisibilidad: el despiece del factor
Para demostrar que una expresión de la forma an+1 − bn+1 es divisible por algo, un truco muy útil es escribir a = (a − b) + b y desarrollar. Esto permite extraer la diferencia (a−b) y usar la HI sobre an − bn. En el ejemplo anterior se usó 23 = 5 + 18 para extraer el 5 (divisor que buscamos).
Inducción fuerte (Segundo Principio de Inducción)
El Principio de Inducción fuerte (o segundo principio) es una variante más potente que dice: si puedo demostrar p(n+1) asumiendo que p(h) es verdadera para todos los h ≤ n (no solo para h = n), entonces p vale para todos los naturales.
Si v[p(m)] = V y [∀h ≤ n: v[p(h)] = V → v[p(n+1)] = V], entonces ∀n ≥ m: v[p(n)] = V
La inducción usual (primera forma) es un caso particular de la fuerte, donde solo se usa p(h) para demostrar p(h+1). En la forma fuerte, se pueden usar todos los casos anteriores.
¿Cuándo usar inducción fuerte?
Se usa cuando para demostrar p(n+1) no alcanza con saber solo p(n), sino que necesitamos algún p(k) con k < n. Ejemplo clásico: la demostración del Teorema Fundamental de la Aritmética (todo natural mayor que 1 es producto de primos), donde para descomponer n+1 necesitamos saber que sus factores propios (menores que n+1) ya son productos de primos.
Caso base en valor m ≠ 1
El principio de inducción no exige que el caso base sea n = 1. En general:
- Si el enunciado dice "∀n ≥ m", el caso base es n = m.
- El paso inductivo demuestra que si p(h) vale para h ≥ m, entonces p(h+1) también vale.
- La conclusión es que p(n) vale para todo n ≥ m.
Definiciones recursivas (recursión)
Una definición es recursiva cuando define un objeto en función de casos más simples del mismo objeto, más un caso base que corta la recursión.
Factorial recursivo
El factorial se puede definir recursivamente:
- Caso base: 0! = 1
- Paso recursivo: n! = n · (n−1)! para n ≥ 1
Entonces: 4! = 4 · 3! = 4 · 3 · 2! = 4 · 3 · 2 · 1! = 4 · 3 · 2 · 1 · 0! = 24.
Sucesión de Fibonacci
Definición recursiva: F(1) = 1, F(2) = 1, F(n) = F(n−1) + F(n−2) para n ≥ 3.
Los primeros términos: 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Las definiciones recursivas son el sustento teórico de la recursión en programación y de muchos enunciados de inducción fuerte.
Recursión e inducción son "duales"
La definición recursiva construye objetos de abajo hacia arriba (del caso base a los más grandes). La demostración por inducción prueba propiedades de arriba hacia abajo en el sentido conceptual: "si vale para n, vale para n+1". Son dos caras de la misma idea: la estructura de ℕ.
Inducción aplicada a operaciones de conjuntos
La inducción también se aplica para demostrar propiedades que involucran operaciones generalizadas sobre familias de conjuntos. El ejemplo canónico es demostrar la distributividad generalizada.
Demostración: (∩ₙ Aᵢ) ∩ B = ∩ₙ (Aᵢ ∩ B)
Enunciado formal: ∀n ∈ ℕ: (A₁ ∩ A₂ ∩ … ∩ Aₙ) ∩ B = (A₁∩B) ∩ (A₂∩B) ∩ … ∩ (Aₙ∩B)
p(n): (∩i=1n Aᵢ) ∩ B = ∩i=1n (Aᵢ ∩ B)
Paso base (n=1):
A₁ ∩ B = A₁ ∩ B — ambos miembros son iguales trivialmente. → v[p(1)] = V. ✓
Paso inductivo:
HI: (A₁ ∩ … ∩ Aₕ) ∩ B = (A₁∩B) ∩ … ∩ (Aₕ∩B)
TI: (A₁ ∩ … ∩ Aₕ ∩ Aₕ₊₁) ∩ B = (A₁∩B) ∩ … ∩ (Aₕ∩B) ∩ (Aₕ₊₁∩B)
Dem.: Partimos del primer miembro de la TI:
(A₁ ∩ … ∩ Aₕ ∩ Aₕ₊₁) ∩ B
= [(A₁ ∩ … ∩ Aₕ) ∩ Aₕ₊₁] ∩ B — asociativa de ∩
= [(A₁ ∩ … ∩ Aₕ) ∩ B] ∩ (Aₕ₊₁ ∩ B) — distributiva de ∩ respecto de ∩ (y conmutativa)
= [(A₁∩B) ∩ … ∩ (Aₕ∩B)] ∩ (Aₕ₊₁ ∩ B) — aplicamos HI
= (A₁∩B) ∩ … ∩ (Aₕ∩B) ∩ (Aₕ₊₁∩B) — asociativa
Llegamos al segundo miembro de TI. ✓
Conclusión: Por PIC, la propiedad vale para todo n ∈ ℕ. ∎
Nota: la demostración del Ej.15 (∪ₙ Aᵢ) ∩ B = ∪ₙ (Aᵢ ∩ B) es análoga, usando distributividad de ∩ respecto de ∪.
Demostración por inducción: |P(A)| = 2ⁿ cuando |A| = n
p(n): Si |A| = n, entonces |P(A)| = 2n.
Paso base (n=0):
Si |A| = 0, entonces A = ∅ y P(∅) = {∅}, por lo que |P(∅)| = 1 = 2⁰. ✓
Paso inductivo:
HI: Si |A| = h, entonces |P(A)| = 2ʰ.
TI: Si |A| = h+1, entonces |P(A)| = 2ʰ⁺¹.
Dem.: Sea A un conjunto con h+1 elementos. Tomo un elemento fijo a₀ ∈ A y llamo A' = A \ {a₀}, que tiene h elementos.
Cada subconjunto X de A o bien contiene a₀ o bien no lo contiene:
— Si X no contiene a₀: X ⊆ A', y hay |P(A')| = 2ʰ de estos (por HI).
— Si X contiene a₀: X = X' ∪ {a₀} con X' ⊆ A', y hay también 2ʰ de estos.
Total: |P(A)| = 2ʰ + 2ʰ = 2 · 2ʰ = 2ʰ⁺¹. ✓ ∎
Resumen de la unidad
| Concepto | Lo esencial |
| Conjunto | Colección bien definida de objetos. Se describe por extensión, comprensión o Venn. |
| ∈ vs. ⊆ | ∈ relaciona elemento-conjunto; ⊆ relaciona conjunto-conjunto. |
| Igualdad | A = B ⟺ A ⊆ B ∧ B ⊆ A (demostrar las dos inclusiones). |
| Operaciones | ∪, ∩, −, complemento, △. Todas con definición formal en términos de pertenencia. |
| De Morgan | A ∪ B̄ = Ā ∩ B̄ y A ∩ B̄ = Ā ∪ B̄. |
| P(A) | Todos los subconjuntos de A. Si |A| = n, |P(A)| = 2ⁿ. |
| Partición | Celdas no vacías, disjuntas, que cubren A. Las tres condiciones son obligatorias. |
| Producto cartesiano | Pares ordenados. No conmutativo. |A×B| = |A|·|B|. |
| PIE | |A∪B| = |A|+|B|−|A∩B|. Para tres conjuntos se suma la intersección triple. |
| Inducción | Caso base + paso inductivo (HI → TI). Demostrar sin suponer la TI verdadera. |
| Inducción fuerte | La HI supone p(h) para todos los h ≤ n, no solo el inmediato anterior. |
| Recursión | Definir objetos a partir de casos más simples + caso base. |
↑ Volver al índice