Tema 2: Cardinalidad PDF

Preview

Summary

Download Tema 2: Cardinalidad PDF

Description

Cardinalidad Teorema Sean A,

Introducción a la Cardinalidad

1

Mariam Cobalea Universidad de Málaga Dpto. de Matemática Aplicada

EAC, Curso 15/16

A⇡A

2

Si A ⇡ B, entonces B ⇡ A

3

Si A ⇡ B y B ⇡ C, entonces A ⇡ C.

Demostración: Trivial a partir de las propiedades de las funciones biyectivas:

Curso 15/16

Mariam Cobalea (UMA)

B y C conjuntos cualesquiera. Se verifica:

Tema 1 - Int. a la Cardinalidad

1 / 54

Cardinalidad

1

La identidad es una biyección.

2

La inversa de un función biyectiva es también un función biyectiva.

3

La composición de biyecciones tambien es biyección.

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

3 / 54

Cardinalidad

Definición (Conjuntos equipotentes) Se dice que el conjunto A es equipotente al conjunto B función biyectiva f : A ! B. Se escribe A ⇡ B.

si existe una

„ Este teorema nos dice que dada una colección relación

⇡

S

es una relación de equivalencia en

de conjuntos, la S.

„ En cada clase de equivalencia estarán los conjuntos equipotentes. Ejemplo

„ A cada clase de equivalencia se le asigna un objeto: el cardinal de cada

El conjunto A = {000, 001, 010, 100, 011, 101, 110, 111} es equipotente al

elemento en la clase.

conjunto B = {0, 1, · · · , 7}

„ De esta forma, a los conjuntos {1}, {a}, . . .

Ejercicio

se les asigna el cardinal 1;

Sea X un conjunto con 10 elementos. Consideramos los conjuntos

a los conjuntos {1, 2}, {a, b}, · · ·

que tienen un elemento

que tienen dos elementos se les

asigna el cardinal 2; ...

A = {Y ✓ X | Y tiene 7 elementos} B = {Z ✓ X | Z tiene 3 elementos}

a los conjuntos {1, 2, ..., n}, {a1 , a2 , ..., an }, · · · se les asigna el cardinal n; ...

que tienen n elementos

Demuestra que A ⇡ B. Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

2 / 54

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

4 / 54

Cardinalidad

Conjuntos Infinitos

Para algunos conjuntos, como los del primer ejemplo, A = {000, 001, 010, 100, 011, 101, 110, 111} y

B = {0, 1, 2, 3, 4, 5, 6, 7}

Definición (Conjunto infinito (

I ))

ser equipotentes, significa tener el mismo número de elementos.

Se dice que un conjunto A es infinito si no es finito (es decir, si no existe

En estos conjuntos el cardinal coincide con la idea intuitiva de ’tamaño’

un número natural n 2 N tal que se puede establecer una biyección entre

del conjunto. Sin embargo, no siempre ocurre esto.

el conjunto {1, 2, ..., n } y el conjunto A ).

Existen conjuntos equipotentes que no tienen el mismo ’tamaño’. * Para probar que un conjunto A es infinito usando la definición (

Ejemplo Sea E = {x 2 Z | x

es par }. f

La función

para ningún n.

Z ! E

:

x

I ) se

debe establecer que no existe ninguna biyección de {1, 2, . . . , n} en A * Esta prueba puede ser muy dificil debido a que hay que descartar

7! 2x

infinitas posibilidades.

nos permite afirmar que Z tiene el mismo cardinal que

E.

(¡¡¡ A pesar de que E tiene la mitad de los elementos de Z !!) Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

5 / 54

Conjuntos Finitos Definición (Conjunto finito (

I ))

Tema 1 - Int. a la Cardinalidad

7 / 54

Teorema

se puede establecer una biyección entre el conjunto Nn = {1, 2, . . . , n} y el conjunto A. Este entero n se llama cardinal de A. A = ∅,

EAC, Curso 15/16

Conjuntos Infinitos

Se dice que un conjunto A es finito si existe un número natural n, tal que

(Para

Mariam Cobalea (UMA)

Se denota |A| = n.

N es un conjunto infinito. Demostración: „ Veamos que no existe un número natural n tal que se pueda establecer una

|A| = 0 )

biyección del conjunto {1, 2, . . . , n} al conjunto N. „ Sea n cualquier elemento de N y sea f cualquier función de {1, 2, . . . , n} en N.

* Establecer una biyección entre {1, 2, . . . , n} y un conjunto A equivale a contar el número de elementos de

„ Se considera

A.

k = 1 + máx{f(1), . . . , f(n)}

„ Entonces k 2 N, pero para cada x 2 {1, 2, . . . , n},

„ De ahí, f no puede ser sobreyectiva y, por tanto, no es biyectiva.

Las propiedades de los conjuntos finitos ya se han estudiado en Matemática Discreta. Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

f(x) 6= k.

„ Ya que n y f se eligen arbitrariamente, concluimos que N es infinito.

6 / 54

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

8 / 54

Conjuntos Finitos e Infinitos Definición (

Conjuntos infinitos

I)

Se dice que un conjunto A es finito si existe un número natural n, que se puede establecer una biyección

tal

f : Nn = {1, 2, . . . , n} ! A.

Usando la definición (

II ) podemos dar una demostración más corta del

teorema anterior. Teorema

Se dice que un conjunto A es infinito si no es finito

N es un conjunto infinito. Definición (

II )

Demostración:

Se dice que un conjunto A es infinito si existe una función inyectiva f : A ! A tal que f(A) ⇢ A.

„ La función

f : N ! N definida por

Un conjunto A es finito si no es infinito.

f(n) = 2n es inyectiva y se cumple que

I ) establece explícitamente cómo reconocer un conjunto finito. La definición ( II ) establece explícitamente cómo reconocer un conjunto infinito. Se puede demostrar que las definiciones ( I ) y ( II ) son equivalentes.

La definición (

f(N) ⇢ N „ Por lo tanto,

N es un conjunto infinito.

Usaremos la definición que sea más conveniente. Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

9 / 54

Conjuntos infinitos * Usaremos la definición ( definición (

II II

II

Mariam Cobalea (UMA)

) para demostrar que un conjunto es finito y la

tal

Solución:

f : Nn = {1, 2, . . . , n} ! A. „ En efecto, sea f : ⇤Σ! ⇤Σ definida por

Se dice que un conjunto A es infinito si no es finito.

f(w) = aw.

„ Esta función es inyectiva y su imagen es un subconjunto propio de ⇤Σ,

II )

⇤ f(Σ ) es el subconjunto de las cadenas que empiezan con la letra a.

Se dice que un conjunto A es infinito si existe una función inyectiva f : A ! A tal que f(A) ⇢ A. A

Entonces ⇤Σ es infinito.

I)

que se puede establecer una biyección

Un conjunto

11 / 54

Ejemplo

) para mostrar que un conjunto es infinito.

Se dice que un conjunto A es finito si existe un número natural n,

Definición (

Tema 1 - Int. a la Cardinalidad

Conjuntos infinitos

Sea el alfabeto Σ= {a, b}. Definición (

EAC, Curso 15/16

„ Luego, ⇤Σ es infinito.

es finito si no es infinito.

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

10 / 54

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

12 / 54

Conjuntos infinitos

Conjuntos infinitos

Teorema

Teorema

Sea A un subconjunto de B. Si A es infinito, entonces B es infinito.

Sean A

Demostración: „ Si A es infinito, entonces existe una función inyectiva f : A → A tal que f(A) = A0 ⊂ A. „ Para mostrar que B es infinito, definimos g : B → B como sigue:

g(x) =

(

f(x) x

y

B conjuntos, tales que

1

P(A) es infinito,

2

A ⇥ B es infinito,

es infinito y

B 6= ∅.

Entonces

Demostración:

si x 2 A

1

si x 2 B  A

„ Entonces g es inyectiva y la imagen de g no incluye el conjunto no vacío A −

A0

Definimos la función f : A ! P(A),

f(x) = {x}

Claramente, f es inyectiva y, del teorema anterior, deducimos que P(A) es .

infinito.

„ Esto establece que B es infinito. 2

Por ser B 6= ∅, podemos elegir un elemento b 2 B, y definimos la función

Corolario 1 Si A es infinito, entonces A [ B es infinito. 2

A

f : A ! A ⇥ B,

f(x) = (x, b)

Sea A un subconjunto de B. Si B es finito, entonces A es finito.

Ya que A es infinito y f es inyectiva, se sigue del teorema anterior que

(Esto es, cada subconjunto de un conjunto finito es finito.)

A ⇥ B es infinito.

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

13 / 54

Conjuntos infinitos

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

15 / 54

Conjuntos numerables

Teorema

La técnica usada para establecer el cardinal de un conjunto infinito es

Sea f : A ! B una función inyectiva. Si A es un conjunto infinito,

esencialmente la misma que se usó para conjuntos finitos.

entonces B es infinito. Teorema Sean A y

Mariam Cobalea (UMA)

Para los conjuntos finitos, cada conjunto de la forma {1, 2, ..., n} se usa como un ’conjunto estándar’ con el que otros conjuntos son comparados mediante

B conjuntos, tales que

A es infinito y

B 6= ∅.

Entonces

una biyección. Así pues, un conjunto finito tiene cardinal n si, y sólo si, hay una biyección de

1

P(A) es infinito,

2

A ⇥ B es infinito,

{1, 2, ..., n} en A. Cada vez que introducimos un nuevo número cardinal infinito α elegimos un conjunto estándar S apropiado y afirmamos:

Demostración: 1

Consideramos la función f : A ! P(A)

definida por f(x) = { x }

El conjunto A tiene cardinal α si hay una biyección del conjunto S

Claramente, f es inyectiva y, del teorema anterior, deducimos que

en el conjunto A.

P(A) es infinito. Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

14 / 54

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

16 / 54

Conjuntos numerables

Conjuntos numerables Si A es infinito y A ⇡ N, tambien tenemos que N ⇡ A. Luego podemos demostrar que un conjunto A es infinito numerable encontrando

„ Hemos demostrado que el conjunto N es infinito. „ Ya que ningún número natural puede ser el cardinal de N, debemos introducir un conjunto estándar para |N|.

1

una biyección f : N ! A o bien

2

una biyección f : A ! N

„ Se elige el propio N como conjunto estándar y denotamos por @0 el cardinal de N.

Algunos autores consideran N = {0, 1, 2, 3, ..., n, ...} y al conjunto {1, 2, 3, ..., n, ...} lo denotan Z+ .

Definición

Los conjuntos {0, 1, 2, 3, ..., n, ...} y {1, 2, 3, ..., n, ...} son equipotentes,

Se dice que un conjunto A tiene cardinal ℵ0 , si existe una función biyectiva de N en A. Se escribe |A| = @0 .

ya que la función f : {0, 1, 2, 3, ..., n, ...} ! {1, 2, 3, ..., n, ...} dada por f(n) = n + 1 es biyecctiva. Ambos conjuntos tienen el mismo cardinal: @0 .

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

17 / 54

Mariam Cobalea (UMA)

EAC, Curso 15/16

Conjuntos numerables

Conjuntos numerables

La existencia de biyección de N o algún conjunto {1, 2, ..., n} en A

Ejemplo

sugiere la idea de contar los elementos de A, incluso aunque el proceso de

Sea k 2 Z,

recuento pudiera ser interminable.

k 6= 0. Demuestra que el conjunto kZ+ es numerable.

Sea k 2 Z,

k 6= 0.

La función

Se dice que un conjunto A es infinito numerable si existe una biyección de N en A.

Luego, kZ+

es numerable y

|kZ+ | = |Z+ |.

* En particular, el conjunto Z de los enteros negativos, es decir,

A es un conjunto infinito numerable, |A| = @0 .

Tema 1 - Int. a la Cardinalidad

definida

es una biyección.

En otro caso, se dice que el conjunto A es no numerable.

EAC, Curso 15/16

f : Z+ ! kZ+ f(x) = kx

El conjunto A se llama numerable si es finito o infinito numerable.

Mariam Cobalea (UMA)

19 / 54

Solución:

Definición

* Si

Tema 1 - Int. a la Cardinalidad

(1)Z+ , es un conjunto numerable.

18 / 54

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

20 / 54

Conjuntos numerables

Conjuntos numerables

Ejemplo

Para avanzar un poco más en nuestro estudio de los conjuntos numerables,

1 Determina el cardinal del conjunto A = {1, , 1 , . . . } = { 1 | n 2 Z+ }. n 2 3 Solución: La función biyección entre

Z+

f : Z+ ! A definida f(n) = y

introducimos algunos conceptos que nos servirán para simplificar las demostraciones.

1 , establece una n

Decimos que un conjunto se puede enumerar si sus elementos se pueden listar.

A.

Por lo tanto, |A| = |Z+ | = @0 ,

Esta lista puede ser finita o infinita; y pueden ocurrir repeticiones

A es numerable.

(es decir, no todas las entradas de la lista deben ser distintas). Si una lista enumera el conjunto A, entonces cada entrada de la lista

Ejercicio

es un elemento de A y cada elemento de A aparece como una

Halla el cardinal de los conjuntos siguientes: A = {10, 20, 30, 40, ...},

B = {6, 7, 8, 9, ...},

Mariam Cobalea (UMA)

C=

EAC, Curso 15/16

⇢

cn =

2n |n2N n+6



Tema 1 - Int. a la Cardinalidad

21 / 54

entrada de la lista. Se formalizan estos conceptos como sigue.

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

Conjuntos numerables

Conjuntos numerables

Ejercicio

Un segmento inicial de N es el conjunto N o un conjunto de los n

23 / 54

Definición primeros números naturales, Nn = {1, 2, . . . , n}.

En el conjunto R

de los números reales se consideran los subconjuntos: ⇢  2n A = {x 2 R | 1  x  2} B = bn = |n2N n+6

Definición Sea A un conjunto. Una enumeración de A es una función sobreyectiva

Determina los cardinales de los conjuntos siguientes: (i) B

(ii) A \ B

f de un segmento inicial de N en A. Si f es inyectiva tambien (y por tanto, biyectiva), entonces f es una

(iii) B  A

enumeración sin repeticiones. Justifica las respuestas.

Si f no es inyectiva, entonces f es una enumeración con repeticiones.

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

22 / 54

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

24 / 54

Conjuntos numerables

Conjuntos numerables

Ejemplo

Cuando presentamos una enumeración f, la función se especifica

El conjunto de los números racionales positivos Q+ es infinito numerable.

normalmente dando la secuencia hf(1), f (2), . . . i.

Solución:

Nos referiremos a f como una función enumeración.

3 Claramente Q+ no es finito, ya que podemos establecer una función inyectiva de los naturales N en Q+ .

Ejemplo Si A = {a, b, c}, entonces hb, c, b, ai y hc, b, ai son enumeraciones de A ;

3 Demostramos que Q+ es numerable mostrando una enumeración con repeticiones.

la primera con repeticiones y la segunda sin repeticiones.

3 El orden de la enumeración se especifica en un grafo dirigido.

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

25 / 54

Conjuntos numerables

Mariam Cobalea (UMA)

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

Conjuntos numerables 3 Todo número racional positivo es el cociente

Teorema

3 Se escriben los números racionales positivos enumerando los de denominador 1 en la primera fila, los de denominador 2 en la segunda fila, y así sucesivamente.

Ejemplo ⇤ Dado cualquier alfabeto finito Σ , el conjunto Σ es infinito numerable.

1 1/1

2 2/1

3 3/1

4 4/1

Solución: Esto se puede demostrar exponiendo los elementos de ⇤Σ en un

1

orden estándar.

2

1/2

2/2

3/2

4/2

3

1/3

2/3

3/3

4/3

4

1/4

2/4

3/4

5

1/5

2/5

6 .. .

1/6

En particular, si Σ= {0, 1} y 0 precede a 1 en el orden ‘alfabético’ de Σ , entonces la enumeración de ⇤Σ en el orden estándar es hλ, 0, 1, 00, 01, 10, 11, 000, 001, . . . i

EAC, Curso 15/16

Tema 1 - Int. a la Cardinalidad

de dos enteros

p/q

positivos.

Un conjunto A es numerable si, y sólo si, existe una enumeración de A.

Mariam Cobalea (UMA)

27 / 54

26 / 54

Mariam Cobalea (UMA)

EAC, Curso 15/16

5 5/1 . ..

... ...

Tema 1 - Int. a la Cardinalidad

28 / 54

Conjuntos numerables 3 Para enumerar Q con

+

Conjuntos numerables