13.4: Actividades

Actividad\(\PageIndex{1}\)

En cada una de las siguientes, demostrar que el conjunto dado es contable exhibiendo una correspondencia biyectiva explícitamente definida entre éste y\(\mathbb{N}\text{.}\)

1. El conjunto de números naturales excluyendo 0.
2. El conjunto de números naturales que son mayores que\(9,999,999\text{.}\)
3. El conjunto de números naturales impares.
4. El conjunto de potencias enteras de\(2\) (incluyendo exponentes positivos y negativos).

Actividad\(\PageIndex{2}\)

Sin hacer trampa y mirando las pruebas en este capítulo, pruebe cada una de las siguientes afirmaciones. Es posible que desee hacer uso de la caracterización de la contabilidad en Fact 13.1.2 en lugar de la definición técnica de conjunto contable.

Nota: Cada enunciado excepto los dos primeros puede probarse directamente a partir de los enunciados anteriores.

1. Cada subconjunto de\(\mathbb{N}\) es contable.
2. Si dos conjuntos tienen el mismo tamaño y uno de ellos es contable, entonces también lo es el otro.
3. Cada conjunto que tiene el mismo tamaño que un subconjunto de\(\mathbb{N}\) es contable.
4. Cada subconjunto de un conjunto contable es contable.
5. Cada conjunto que tenga el mismo tamaño que un subconjunto de un conjunto contable es contable.
6. Un conjunto que contiene un subconjunto incontable es incontable

Actividad\(\PageIndex{3}\)

1. Demostrar que\(\mathbb{N} \times \mathbb{N}\) es contable.

Insinuación.

Utilice un método zig-zag-through-a-grid similar a la prueba de la contabilidad de los números racionales. (Ver Teorema 13.1.1 y su prueba.)

2. Demostrar que si\(A\) y\(B\) son ambos contables, entonces también lo es\(A \times B\text{.}\)

Insinuación.

Podrías hacer más zigzagueos, o podrías usar la declaración de la Tarea a.

3. Demostrar que\(Z\) si\(X\text{,}\)\(Y\text{,}\) y cada uno es contable, entonces también lo es\(X \times Y \times Z\text{.}\)

Insinuación.

Utilice la declaración de Tarea b dos veces.

4. ¿Qué método de prueba crees que utilizarías para probar la siguiente afirmación?

Si todos\(A_1, A_2, \ldots, A_n\) son contables, entonces también lo es

\ begin {ecuation*} A_1\ times A_2\ times\ cdots\ times a_N\ text {.} \ end {ecuación*}

Actividad\(\PageIndex{4}\): The Infinite Orchard Problem.

Tienes un mágico huerto de manzanos que contiene un número infinito de árboles, cada uno de los cuales lleva un número infinito de manzanas. Describir un método para recoger todas las manzanas del huerto, una manzana a la vez. (¡No sacuden los árboles, por favor! Sin embargo, puede asumir una cantidad infinita de tiempo.)

Actividad\(\PageIndex{5}\)

Demostrar que si\(A_0,A_1,A_2,\ldots\) es una colección infinita de conjuntos, cada uno de los cuales es contablemente infinito, entonces la unión

\ begin {ecuación*}\ bigcup_ {n=0} ^\ infty a_n = A_0\ copa A-1\ copa A_2\ copa\ cdots\ end {ecuación*} también
es contablemente infinito.

Insinuación.

¿Y si cada juego fuera un manzano?

Actividad\(\PageIndex{6}\)

Let\(\mathscr{F}\) representar el conjunto de todas las funciones con dominio\(\{0,1\}\) y codominio\(\mathbb{N}\text{.}\)

1. Determinar una correspondencia biyectiva entre\(\mathscr{F}\) y\(\mathbb{N} \times \mathbb{N}\text{.}\)
2. Explique por qué Tarea a prueba que\(\mathscr{F}\) es contable.

Insinuación.

Ver Actividad\(\PageIndex{2}\) y Actividad\(\PageIndex{3}\).

Actividad\(\PageIndex{1}\)

Let\(\mathscr{F}'\) representar el conjunto de todas las funciones con dominio\(\mathbb{N}\) y codominio\(\{0,1\}\text{.}\)

Tenga en cuenta que cada elemento de\(\mathscr{F}'\) define una secuencia infinita de\(0\)\(1\) s y s.

1. Supongamos que\(A\) es un subconjunto contable de\(\mathscr{F}'\text{.}\) (Así\(A\) es una lista infinita de secuencias infinitas de\(0\)\(1\) s y s.)

Describir cómo construir un elemento de\(\mathscr{F}'\) eso definitivamente no está en Es\(A\text{.}\) decir, construir una secuencia infinita de\(0\) s y\(1\) s que definitivamente no es lo mismo que cualquiera de las secuencias infinitas en la lista infinita de\(A\text{.}\)

Insinuación.

Utilice el argumento diagonal de Cantor a partir de la prueba de Lemma 13.1.1.

2. Explique por qué Tarea a prueba que\(\mathscr{F}'\) es incontable.

Insinuación.

\(\mathscr{F}' \subseteq \mathscr{F}'\text{.}\)