Teoría de conjuntos y cardinalidad

Diagrama de matematicas discretas: grafo con nodos conectados, puertas logicas y diagramas de Venn. — Temas centrales de matematicas discretas: logica, conjuntos, grafos y conteo.

Mapa conceptual

Comparar sin contar Dos conjuntos tienen el mismo «tamaño» (misma cardinalidad) si sus elementos pueden emparejarse uno a uno sin que sobre ninguno: una biyección. Con conjuntos finitos es contar; con infinitos, es donde se vuelve fascinante.

Un conjunto no ordena y no repite: 1, 2, 3 = 3, 1, 2 y 1, 1, 2 es simplemente 1, 2. Dados A y B, la unión A ∪ B lleva los que están en cualquiera; la intersección A ∩ B, los que están en ambos; la diferencia A B, los de A que no están en B; y el complemento Ā, los que no están en A dentro del universo considerado.

Estas operaciones son las mismas que AND/OR/NOT de la lógica, aplicadas a colecciones.
Operación	Símbolo	Contiene los x tales que
Unión	A ∪ B	x ∈ A o x ∈ B
Intersección	A ∩ B	x ∈ A y x ∈ B
Diferencia	A B	x ∈ A y x ∉ B
Complemento	Ā	x ∉ A (en el universo)
Conjunto potencia	P(A)	cada subconjunto de A es un elemento

Cardinalidad finita y el principio de inclusión-exclusión

Para conjuntos finitos, A ∪ B = A + B − A ∩ B: al sumar ambos tamaños has contado dos veces la intersección, así que la restas una. El conjunto potencia P(A) de un conjunto de n elementos tiene 2ⁿ elementos: cada elemento puede estar o no en cada subconjunto.

Hay infinitos más grandes que otros La cardinalidad del continuo es estrictamente mayor que la de los naturales: no hay emparejamiento uno a uno entre ℕ y ℝ (argumento de la diagonal de Cantor). Pero ℕ y los enteros ℤ, o ℕ y los racionales ℚ, SÍ tienen el mismo tamaño: son numerables.

Infinitos que se emparejan

Los pares 2, 4, 6, … son «mitad» de los naturales, pero tienen la misma cardinalidad: empareja n con 2n y no sobra nadie. Este tipo de contra-intuición es exactamente lo que hace la correspondencia uno-a-uno con conjuntos infinitos: una parte puede ser tan grande como el todo.

Si A = 1,2,3,4 y B = 3,4,5, ¿cuánto vale A ∪ B?

Existen infinitos de distinto tamaño: los reales son «más» que los naturales.

Clasifica cada conjunto por su cardinalidad.

Finito

Numerable (infinito)

No numerable

Errores con conjuntos

Confundir ∈ (elemento de) con ⊆ (subconjunto de): 1 es elemento de 1,2, pero 1 es subconjunto de 1,2; y el vacío ∅ es subconjunto de todo conjunto.
Creer que ∅ = ∅: el primero es el conjunto vacío; el segundo tiene UN elemento (el vacío).
Olvidar que P(A) = 2ⁿ y no 2·n: para n = 3 son 8 subconjuntos, no 6.

Ejemplo resuelto

En un curso, 30 estudian Python, 25 estudian R y 10 ambas. ¿Cuántos estudian al menos una?
Aplica inclusión-exclusión: P ∪ R = P + R − P ∩ R.
Sustituye: 30 + 25 − 10.
Resultado: 45 estudiantes estudian al menos uno de los dos lenguajes.
Comprueba que 45 no excede el total: si el curso tuviera 50, 5 no estudian ninguno.

La teoría de conjuntos es el corazón de las operaciones de base de datos: un JOIN es una intersección sobre claves, un UNION es una unión y un WHERE es un complemento o una intersección con el predicado. Contar sin repetir —como en inclusión-exclusión— es contar bien las filas de una consulta.

Álgebra de conjuntos

A ∪ B

o (en alguno)

A ∩ B

y (en ambos)

A B

en A, no en B

complemento

A∪B

A+B−A∩B

P(A)

2ⁿ subconjuntos

ℤ,ℚ

numerables

ℝ

no numerable

Teoría de conjuntos (repaso formal)
Operaciones, diagramas de Venn y cardinalidad, incluidos los infinitos.

Da una biyección explícita que muestre que el conjunto de los enteros positivos y el de los enteros (positivos, negativos y cero) tienen la misma cardinalidad. Explica por qué esto choca con la intuición de que «los enteros son el doble».

MIT OCW 6.042J
Matematicas para Ciencias de la Computacion (MIT OpenCourseWare).