Cardinalidad

Dados dos conjuntos A y B, decimos que A es equivalente a B, o que A y B tienen la misma potencia, y lo notamos A ∼ B, si existe una biyecci´on de A en B. Es f´acil probar que ∼ es una relaci´on de equivalencia entre conjuntos. La clase de equivalencia de un conjunto A es el conjunto A = {B/B ∼ A}. El cardinal o potencia de A es la clase de equivalencia de A. Frecuentemente, para describir una de estas clases, especificaremos un elemento que pertenece a ella, que la represente. Algunos cardinales tienen s´ımbolos asignados. Por ejemplo ∅ = 0;

{1, 2, ..., n} = n;

N = ℵ0 ;

R = c.

El s´ımbolo ℵ se lee alef y corresponde a la primera letra del alfabeto hebreo. La potencia de R, R = c, se llama la potencia del continuo. Un conjunto se dice finito si tiene cardinal 0 ´o n, n ∈ N. En otro caso el conjunto se dice infinito. Los cardinales 0 ´o n, n ∈ N se llaman cardinales finitos. Cualquier otro cardinal se llama cardinal transfinito. Un conjunto que tiene cardinal finito o ℵ0 se llama numerable; en otro caso el conjunto se llama no numerable. Teorema 0.1 Si A es numerable y B ⊂ A entonces B es numerable. Demostraci´on. Si A es finito y B ⊂ A, B es finito. Supongamos que A es infinito entonces A = ℵ0 , es decir que existe f : A → N biyectiva. Luego f : B → f (B) ⊆ N es biyectiva. Si f (B) es finito entonces B es finito. Supongamos que f (B) es infinito. Sea n1 = m´ın f (B), n2 = m´ın f (B) − {n1 }, etc. Luego la aplicaci´on g : f (B) → N, g(nk ) = k es biyectiva y f (B) es numerable. Corolario 0.2 Si A no es numerable y A ⊂ B entonces B no es numerable. Teorema 0.3 Todo conjunto infinito contiene un subconjunto infinito numerable. Demostraci´on. Sea A un conjunto infinito. Construimos una sucesi´on de elementos de A de la siguiente forma: sea α1 ∈ A. A − {α1 } 6= ∅, pues, de otro modo A ser´ıa finito. Sea α2 ∈ A − {α1 }. De manera inductiva sea αn ∈ A − {α1 , ..., αn−1 } (A − {α1 , ..., αn−1 } = 6 ∅ pues, si no, A ser´ıa finito). Observemos que si n 6= m, αn 6= αm . Luego B = (αn ) ⊂ A y f : B → N, f (αn ) = n es una biyecci´on. Corolario 0.4 Todo conjunto infinito es equivalente a un subconjunto propio. Es decir, dado A un conjunto infinito, existe una biyecci´on de A en un subconjunto propio de A.

Demostraci´on. Si A es infinito, por el teorema anterior, existe B ⊂ A, B = (αn ) infinito numerable. Definamos f como la identidad en A \ B yf (αn ) = αn+1 . Entonces f es una biyecci´on de A en A − {α1 }. Para ordenar cardinales finitos podemos decir que, dados A y B conjuntos finitos A < B si existe una biyecci´on de A en un subconjunto propio de B. Observemos que esta definici´on de orden no es satisfactoria para cardinales transfinitos: por ejemplo, las correspondencias n → n + 1, n → 2n, n → n2 . son biyecciones de N en subconjuntos propios de N. Dados dos conjuntos A y B, A ≤ B si existe una aplicaci´on inyectiva f : A → B. Es f´acil ver que ≤ es reflexiva y transitiva. El siguiente teorema prueba que esta relaci´on es antisim´etrica, es decir que si A ≤ B y B ≤ A entonces A = B. Se puede demostrar, aplicando el axioma de elecci´on, que dados dos cardinales, siempre son comparables. Teorema 0.5 (de Cantor-Bernstein) Sean A y B dos conjuntos tales que existen aplicaiones inyectivas f : A → B y g : B → A. Entonces A y B son equivalentes. Demostraci´on. Sea A1 = g(B) ⊂ A. Definimos A2 = g(f (A)), A3 = g(f (A1 )) y Ak+2 = g(f (Ak )), k ∈ N (observemos que Ak+2 es equivalente a Ak ). Si A = A0 vale que Ak ⊃ Ak+1 , k ≥ 0 y ∞ [ A= (Ak \ Ak+1 ) ∪ D, (1) k=0

∩∞ k=1 Ak .

donde D = An´alogamente,

A1 =

∞ [

(Ak \ Ak+1 ) ∪ D.

(2)

k=1

Reordenando las f´ormulas (1) y (2) obtenemos que A = D ∪ [(A1 \ A2 ) ∪ (A3 \ A4 )...] ∪ [(A \ A1 ) ∪ (A2 \ A3 ) ∪ ...] A1 = D ∪ [(A1 \ A2 ) ∪ (A3 \ A4 )...] ∪ [(A2 \ A3 ) ∪ (A4 \ A5 ) ∪ ...] Observemos que A\A1 es equivalente a A2 \A3 , A2 \A3 es equivalente a A4 \A5 , ect., luego es posible construir una biyecci´on entre A y A1 ya que las uniones que figuran en ambas f´ormulas son disjuntas. De este modo A y A1 son equivalentes y luego A y B tambi´en lo son. Corolario 0.6 Sean a y b dos cardinales tales que a ≤ b y b ≤ a entonces a = b. Dados a y b dos cardinales, decimos que a es menor que b, y lo notamos a < b, si a ≤ b y b a, es decir si A = a y B = b, existe una aplicaci´on inyectiva f : A → B pero no existe una aplicaci´on inyectiva g : B → A. Corolario 0.7 ℵ0 es el menor cardinal transfinito.

Demostraci´on. Supongamos que A = ℵ0 y B = ℵ es transfinito. Por el Teorema 0.3 existe f : A → B inyectiva. Luego ℵ0 ≤ ℵ. Teniendo en cuenta el orden que definimos podemos decir que un conjunto A es finito si A < ℵ0 , infinito si A ≥ ℵ0 , A es numerable si A ≤ ℵ0 y no numerable si A > ℵ0 . Teorema 0.8 La uni´on de una familia numerable de conjuntos numerables es numerable. Demostraci´on. Sea {An }n∈N tal que cada An es numerable. Podemos suponer que los An n−1 Ak , si n > 1). Es decir que son disjuntos (si no, consideramos A01 = A1 , A0n = An \ ∪k=1 An = (ank )k∈N . Sea A = ∪n∈N An . Definimos la siguiente aplicaci´on de A en N. El conjunto A se mira como la siguiente “matriz” infinita A1 : a11

a12 .

A2 : a21

. a22

a14

...

. a23

a24

...

a32

a33

a34

...

an2

an3

an4

. A3 : a31 . . An : an1 . .

a13

.

. ...

y se ordena ∪n An como indica el diagrama. Es decir, se consideran las diagonales ordenadas. Entonces se obtiene una aplicaci´on f : A → N inyectiva (ya que algunos de los An pueden ser finitos). Observemos que en la demostraci´on anterior hemos ordenado el conjunto de pares ordenados de n´ umeros naturales {(m, n) : m, n ∈ N} el siguiente modo: dados dos pares 0 0 (m, n) y (m , n ) consideramos que (m, n) < (m0 , n0 ) si m + n < m0 + n0 , es decir si el primer par pertenece a una diagonal anterior al segundo. Si ambos pares est´an en la misma diagonal, es decir si m + n = m0 + n0 entonces (m, n) < (m0 , n0 ) si m < m0 . Se deja como ejercicio calcular la f´ormula expl´ıcita de esta funci´on. Corolario 0.9 El conjunto de n´ umeros racionales es numerable. Demostraci´on. Dado r ∈ Q, r = pq , p, q ∈ Z, q 6= 0. Para q ∈ Z, q 6= 0 fijo, sea Aq = { pq : p ∈ Z}. Entonces Aq es numerable y Q = ∪q∈Z Aq . Luego Q es numerable. Veamos alg´ un ejemplo de un conjunto no numerable: Teorema 0.10 El intervalo [0, 1] no es numerable. Demostraci´on. Basta ver que para toda sucesi´on (an )n∈N ⊂ [0, 1] puedo hallar un n´ umero c ∈ [0, 1] que no pertenece a la sucesi´on. Para esto determinamos un intervalo [p1 , q1 ] ⊂ [0, 1] tal que a1 ∈ / [p1 , q1 ] tal que q1 −p1 = 13 (´este ser´a uno de los intervalos [0, 31 ], [ 31 , 23 ], [ 23 , 1]).

A continuaci´on fijamos un intervalo [p2 , q2 ] ⊂ [p1 , q1 ] tal que a2 ∈ / [p2 , q2 ] y q2 − p2 = 1/9. En general determinamos un intervalo [pn , qn ] ⊂ [pn−1 , qn−1 ] tal que an ∈ / [pn , qn ] y 1 qn − pn = 3n . T Sea {c} = ∞ ımn pn = l´ımn qn . Entonces c 6= an , ∀n ya que n=1 [pn , qn ], es decir c = l´ an ∈ / [pn , qn ]. Corolario 0.11 R no es numerable y c = R > ℵ0 . A continuaci´on veremos que dado un cardinal arbitrario ℵ siempre existe un cardinal mayor. Dado un conjunto A, consideremos el conjunto partes de A, P(A) = {X : X ⊆ A}, de todos los subconjuntos de A. Este conjunto es equivalente al conjunto de funciones de A en {0, 1}, que notaremos {0, 1}A (es decir, {0, 1}A = {f : A → {0, 1}}). Para ver esta equivalencia basta considerar la aplicaci´on g : P(A) → {0, 1}A , g(B) = χB , donde B ⊂ A y χB es la funci´on caracter´ıstica de B, i.e.,   1 si x ∈ B χB (x) =  0 si x ∈ / B. Teniendo en cuenta esta observaci´on, si A = ℵ el cardinal de P(A) ser´a notado 2ℵ , es decir 2ℵ = P(A) = {0, 1}A . Teorema 0.12 Para cualquier cardinal ℵ, ℵ < 2ℵ . Demostraci´on. Supongamos que A = ℵ. La aplicaci´on f : A → P(A), f (a) = {a}, a ∈ A es inyectiva y luego ℵ ≤ 2ℵ . Veamos que no puede existir una biyecci´on g : A → P(A). Sea g : A → P(A) cualquier aplicaci´on. Veamos que la imagen de g es un conjunto propio de P(A). Sea B ⊆ A definido como B = {a ∈ A : a ∈ / g(a)} entonces B ∈ / Im g y B ∈ P(A) pues supongamos que B = g(a0 ) para alg´ un a0 ∈ A. Entonces a0 ∈ B si y s´olo si a0 ∈ / g(a0 ) = B lo cual es absurdo.

1.

Operaciones con n´ umeros cardinales

La suma de dos n´ umeros cardinales m y n es, por definici´on, la potencia de la uni´on de dos conjuntos disjuntos A y B tales que A = m y B = n. Si denotamos m + n a esta suma, entonces m + n = A ∪ B,

donde A ∩ B = ∅, A = m y B = n.

Observemos que si A = m y B = n entonces los conjuntos A1 = {1}×A y B1 = {2}×B son disjuntos y A1 = A y B1 = B. El producto mn de los n´ umeros cardinales m y n se define como mn = A × B,

donde A = m y B = n. Ejercicio: Demostrar que si m, n ∈ N entonces las definiciones anteriores coinciden con las operaciones de suma y producto en N. Ejercicio: Probar que si n ∈ N entonces ℵ0 + ℵ0 = ℵ0 , ℵ0 ℵ0 = ℵ0 y ℵ0 n = ℵ0 . La suma y el producto satisfacen las propiedades asociativa y conmutativa. Proposici´ on 1.1 (Propiedad distributiva) Si m, n, p son cardinales entonces m(n + p) = mn + mp. Demostraci´on. Sean A, B y C tales que A = m, B = n, C = p y B ∩ C = ∅. Entonces A × (B ∪ C) = (A × B) ∪ (A × C). Adem´as (A × B) ∩ (A × C) = ∅. Luego A × (B ∪ C) = A × B + A × C. Corolario 1.2 Si a y n son cardinales, n ∈ N, entonces an = a + a + ... + a, en donde el segundo miembro tiene n t´erminos. Demostraci´on. Aplicar inducci´on sobre n y la propiedad distributiva. Dados dos conjuntos A y B, el conjunto de funciones de A en B se nota B A . Es decir que B A = {f : A → B, f funci´on }. Si A = a y B = b definimos el cardinal ba = B A Es f´acil ver que se verifican las siguientes f´ormulas nm+p = nm np (mn)p = mp np (nm )p = mmp donde m, n y p son n´ umeros cardinales. Recordemos que P(X) = {0, 1}X , para cualquier conjunto dado X. luego, por definici´on, P(X) = 2X .

2.

Propiedades del numero c

Definimos el n´ umero c como la potencia de R. Dados a, b ∈ R, (a, b) = [a, b] = R = c, ya que dos intervalos arbitrarios (a, b) y (c, d) siempre son equivalentes y (− π2 , π2 ) es equivalente a R, pues f : (− π2 , π2 ) → R, f (x) = tg x es una biyecci´on. Como c = (a, b) ≤ [a, b] ≤ R = c , ya que (a, b) ⊂ [a, b] ⊂ R y ,(a, b) = c, resulta que estos cardinales coinciden. Ejercicio: Probar que c = c + n = c + ℵ0 = c + c = nc, donde n ∈ N. La siguiente proposici´on vincula los cardinales ℵ0 y c. Proposici´ on 2.1 2ℵ0 = c. Demostraci´on. Sea A = {0, 1}N , es decir el conjunto de sucesiones de ceros y unos. Entonces A = 2ℵ0 . Sea B el subconjunto de A de las sucesiones (xn ) tales que xm = 0 si m ≥ n0 , para alg´ un n0 ∈ N. Definimos f : A → R de la siguiente forma: si x = (xn ) ∈ B ∞ X xi = (0, x1 x2 ...)2 , f (x) = i 2 i=1 si x = (xn ) ∈ A \ B f (x) = 1 +

∞ X xi i=1

2i

= (1, x1 x2 ...)2 .

La funci´on f es inyectiva y (1, 2) ⊂ f (A) ⊂ R. Luego, f (A) = c = A. Corolario 2.2 ℵℵ0 0 = c = cℵ0 . 2

Demostraci´on. 2ℵ0 ≤ ℵℵ0 0 ≤ cℵ0 = (2ℵ0 )ℵ0 = 2ℵ0 = 2ℵ0 . Aqu´ı usamos la siguiente propiedad: si m, n y p son cardinales tales que m ≤ n entonces mp ≤ np . Corolario 2.3 c = cℵ0 = c2 = cℵ0 . Demostraci´on. c ≤ cℵ0 ≤ c2 ≤ cℵ0 = c. Corolario 2.4 2c = ℵ0 c = cc . Demostraci´on. cc = (2ℵ0 )c = 2ℵ0 c = 2c , pues aplicando el corolario anterior ℵ0 c = c.