Tema 7 Cardinalidad PDF

CONJUNTOS Y CARDINALES INFINITOS Def. Un conjunto A decimos que es finito y de cardinal n (n = |A|) si existe una biyección f : n −→ A donde n = {0, 1,... , n − 1} ⊆ N Es una definición correcta pues si n 6= m no existen f1 , f2 , biyecciones f1 6= f2 tales que f1 : n −→ A f2 : m −→ A si n...

CONJUNTOS Y CARDINALES INFINITOS Def. Un conjunto A decimos que es finito y de cardinal n (n = |A|) si existe una biyección f : n −→ A donde n = {0, 1,... , n − 1} ⊆ N Es una definición correcta pues si n 6= m no existen f1 , f2 , biyecciones f1 6= f2 tales que f1 : n −→ A f2 : m −→ A si n 6= m. Esta propiedad se conoce como el Principio del Palomar que enunciamos a continuación: Sean A, B conjuntos finitos. Si f : A −→ B y |A| > |B| entonces f no es inyectiva. (Si hay más palomas que huecos en el palomar, al menos dos palomas tendrán que compartir hueco.) Teorema Sean A, B conjuntos finitos. Entonces 1. S ⊆ A =⇒ S también es finito y |S| ≤ |A| 2. A ∪ B es finito y |A ∪ B| = |A| + |B| − |A ∩ B| A ∩ B = ∅ =⇒ |A ∪ B| = |A| + |B|. 3. A − B es finito y |A − B| = |A| − |A ∩ B| B ⊆ A (A ∩ B = B) =⇒ |A − B| = |A| − |B| 4. A × B es finito y |A × B| = |A| · |B|. 5. El conjunto de todas las funciones de A en B (denotado por A −→ B) es finito y |A −→ B| = |B||A| 6. P(A) es finito y |P(A)| = 2|A| Dem. 1. Si S ⊆ A podemos definir la función de inclusión f : S ,→ A dada por f (x) = x pues x ∈ A, que es trivialmente inyectiva. Aplicando el Principio del Palomar |S| ≤ |A| y, por tanto, S es finito. 2. |A ∪ B| = |A| + |B| − |A ∩ B| pues los elementos de la intersección se cuentan dos veces, una al contar los de A y otra al contar los de B. Trivialmente si A ∩ B = ∅ =⇒ |A ∪ B| = |A| + |B|. 3. A\B es finito y |A\B| = |A|−|A∩B| pues los elementos de la intersección, que son elementos de B, se cuentan en A. Si B ⊆ A, (A ∩ B = B) =⇒ |A \ B| = |A| − |B| 1  4. A × B es finito y |A × B| = |A| · |B|. Como A×B = {(a, b)|a ∈ A, b ∈ B}, por cada elemento a de A hay tantos pares en A × B como elementos hay en B, luego |A × B| = |A| · |B|. 5. El conjunto de todas las funciones de A en B (denotado por A −→ B) es finito y |A −→ B| = |B||A| Identificamos cada función f de A en B con la n-tupla (f (a1 ), f (a2 ),... , f (an )) donde A = {a1 , a2 ,... , an }. Por tanto, el número de funciones de A en B coincide con el número de tuplas distintas que podamos construir. Si |B| = m hay m posibles valores para f (a1 ), para f (a2 ) y para f (an ), luego hay m · m · · · · · m = mn = |B||A| tuplas distintas. 6. Sea A un conjunto y sea B ⊆ A, la función caracterı́stica de B es: fB : A −→ {0, 1} definida por  1 si x ∈ B fB (x) = 0 si x 6∈ B Luego, existe una biyección h de P(A) en el conjunto de todas las fun- ciones de A en 2,A −→ 2 y, por tanto, |P(A)| = 2|A|. h : P(A) −→ (A −→ 2) h(B) = fB Es inyectiva. h(B1 ) = h(B2 ) =⇒ fB1 = fB2 =⇒ B1 = B2 Es suprayectiva. ∀g : A −→ 2 existe B ∈ P(A) tal que h(B) = g. Dado g : A −→ 2 construimos B de la siguiente forma: x ∈ B ⇐⇒ g(x) = 1. Se verifica g = fB y h(B) = fB = g Comparando Conjuntos Sean A, B conjuntos (finitos o infinitos). 1. A ∼c B sii ∃f : A −→ B biyectiva. Decimos que A y B son conjuntos equipotentes. 2. A ≤c B sii ∃f : A −→ B inyectiva. Decimos que A está dominado por B 3. A 0} es numerable. Q− = {x ∈ Q|x < 0} es numerable. Podemos definir f : Q+ −→ N inyectiva. f(mn ) = 2m 3n (m, n primos entre sı́.) Luego Q+ es numerable. CONJUNTOS NO NUMERABLES Teorema P(N) es un conjunto infinito, no numerable. Dem P(N) no es finito ya que N ≤c P(N) Basta definir f : N −→ P(N) inyectiva. f (n) = {n}. f es inyectiva. Si f (n) = f (m) =⇒ {n} = {m} =⇒ n = m. P(N) es no numerable. Vamos a demostrar que no existe g : N −→ P(N) suprayectiva. Supongamos que existe g0 : N −→ P(N) suprayectiva. Sean A0 = g0 (0) A1 = g0 (1) A2 = g0 (2)... Definimos D = {i ∈ N|i 6∈ Ai } ∈ P(N). Vamos a demostrar que aunque D ∈ P(N), D 6= g0 (n) ∀n ∈ N, es decir, g0 no es suprayectiva.. Supongamos D = g0 (n0 ) para algún n0 ∈ N : n0 ∈ D ⇐⇒ n0 6∈ An0 = g0 (n0 ) = D n0 ∈ D ⇐⇒ n0 6∈ D Contradicción. (Este método de demostración se conoce como método de Diagonalización de Cantor.) Teorema Sea A un conjunto. A