R no es enumerable

Por contradicci´ on, supongamos que existe una biyecci´on f : N ! R. I

Vamos a obtener una contradicci´ on usando el m´etodo de diagonalizaci´ on de Cantor.

Para cada i 2 N: f (i) = ni .di,0 di,1 . . . di,i . . . donde ni 2 Z y di,j 2 {0, . . . , 9}, para cada j 2 N

IIC1253

–

Cardinalidad

10 / 25

R no es enumerable: Diagonalizaci´on Definimos un n´ umero r 2 R usando la siguiente diagonal: f (0) f (1) f (2) f (3) ··· f (i) ···

= = = = =

n0 .d0,0 d0,1 d0,2 d0,3 . . . n1 .d1,0 d1,1 d1,2 d1,3 . . . n2 .d2,0 d2,1 d2,2 d2,3 . . . n3 .d3,0 d3,1 d3,2 d3,3 . . . ··· ni .di,0 di,1 di,2 di,3 . . . di,i . . . ···

Propiedad fundamental de r : f (i) 6= r para cada i 2 N I

IIC1253

–

Usando esta propiedad obtenemos una contradicci´on: f no es sobre

Cardinalidad

11 / 25

R no es enumerable: Diagonalizaci´on Definimos r como: r

= 0.r0 r1 r2 . . .

donde ri (i 2 N) es definido como: ( 5 si di,i = 6 5 ri = 4 si di,i = 5

¿Por qu´e la demostraci´ on anterior no funciona si reemplazamos R por Q?

IIC1253

–

Cardinalidad

12 / 25

R no es enumerable: Existencia de n´umeros trascendentes Un n´ umero a 2 R es algebraico si existe un polinomio p(x) tal que: I

p(x) no es nulo, y los coeficientes de p(x) son n´ umeros enteros

I

p(a) = 0

Ejemplo Cada n´ umero en Q es algebraico, adem´as

p

2 es algebraico.

Un n´ umero a 2 R es trascendente si no es algebraico. I

IIC1253

–

¿Existen n´ umeros trascendentes?

Cardinalidad

13 / 25

R no es enumerable: Existencia de n´umeros trascendentes Existencia de n´ umeros trascendentes: 1 X I Liouville (1850): 10 i! i=1

I

Hermite (1873): e

I

Lindemann (1882): ⇡

Un argumento m´as simple: El conjunto de los polinomios p(x) con coeficientes enteros es enumerable I

IIC1253

–

Como R no es enumerable, concluimos que existen n´ umeros trascendentes

Cardinalidad

14 / 25

R no es enumerable: Nombres para los n´umeros

Podemos asociar nombres a los n´ umeros reales: 1264, milpdoscientos sesenta y cuatro, 3.25, tres punto veinte y cinco, 2, ra´ız cuadrada positiva de 2, ⇡, e, menor ra´ız del polinomio 3x 3 17x + 1, . . .

¿Podemos asociar un nombre a cada n´ umero real? I

IIC1253

–

¿Qu´e alfabeto usamos?

Cardinalidad

15 / 25

R no es enumerable: Nombres para los n´umeros

Consideramos el alfabeto ASCII que tiene 95 caracteres (que pueden ser impresos) I

Otros alfabetos puedes ser codificados usando este alfabeto: "3*x^3 - 17*x + 1", "pi"

I

¿Podemos considerar un alfabeto m´as peque˜ no? ¿0 y 1?

El conjunto de los strings (finitos) que pueden construidos usando el alfabeto ASCII es enumerable I

IIC1253

–

¡Tenemos m´as n´ umeros en R que nombres para ellos!

Cardinalidad

16 / 25

Un teorema m´as general

Definici´on Un conjunto A es menos numeroso que un conjunto B si: I I

existe una funci´ on inyectiva f : A ! B; y no existe una biyecci´ on g : A ! B

Ejemplo En las transparencias anteriores demostramos que N es menos numeroso que R.

IIC1253

–

Cardinalidad

17 / 25

Un teorema m´as general Dado: Conjunto A I

Denotamos el conjunto potencia de A como 2A

Teorema (Cantor) A es menos numeroso que 2A Demostraci´ on: Si A = ;, tenemos que 2A = {;} y el teorema se cumple I

Suponemos que A 6= ;

Primero debemos mostrar una funci´ on inyectiva f : A ! 2A I

IIC1253

–

Para cada a 2 A: f (a) = {a}

Cardinalidad

18 / 25

Teorema de Cantor: Demostraci´on

Ahora debemos demostrar que no existe una biyecci´on g : A ! 2A . I

Por contradicci´on, suponemos que g existe

Definimos B ✓ A como sigue: B

=

{a 2 A | a 62 g (a)}

Como g es sobre, existe b 2 A tal que g (b) = B. I

IIC1253

–

Se debe tener que b 2 g (b) o b 62 g (b)

Cardinalidad

19 / 25

Teorema de Cantor: Demostraci´on

Consideramos los dos casos: b 2 g (b) ) b 2 B

) b 62 g (b)

b 62 g (b) ) b 62 B

) b 2 g (b)

En ambos casos obtenemos una contradicci´ on.

IIC1253

–

Cardinalidad

20 / 25

Teorema de Cantor: Definibilidad de una propiedad

Sea L = {0, 1, s, +, ·,