Cómo demostrar que los siguientes conjuntos son equinuméricos

Question

Esta es mi primera pregunta en este sitio web, así que por favor, denme su opinión cuando sea necesario.

Me he atascado en una pregunta de Computabilidad y Lógica 5ª edición de Boole i.a. Es la pregunta 2.10 y la pregunta es la siguiente:

2.10 Demuestre que los siguientes conjuntos son equinuméricos:

a) el conjunto de todos los pares de conjuntos de números enteros positivos

b) el conjunto de todos los conjuntos de pares de números enteros positivos

c) el conjunto de todos los conjuntos de enteros positivos.

Se ha demostrado que el conjunto de todos los conjuntos de enteros positivos no es enumerable y como los conjuntos de a) y b) contienen más elementos, éstos también deben ser no enumerables. Pero no creo que eso sea suficiente para demostrar que los conjuntos de a), b) y c) son equinuméricos.

Lo que demostraría, es si pudiera encontrar dos biyecciones entre dos pares desiguales de estos tres conjuntos. Pero no se me ocurrió ninguna.

Además, podría demostrar que estos tres conjuntos son equinuméricos con los números reales. Para c), esto ya se mostró en el texto. a) es claramente equinumérico con R^2 y R^2 es equinumérico con R, como se explica bien en este post: Ejemplos de mapa biyectivo de $\mathbb{R}^3\rightarrow \mathbb{R}$ . Así que a) debe ser equinumérico con c). Pero entonces, ¿cómo encuentro una biyección entre b) y a) o c)?

Gracias de antemano.

Answer 1

Para responder a tu pregunta concreta "¿cómo puedo biyectar el segundo conjunto con cualquier cosa?", fíjate en que existe una biyección entre "pares de enteros positivos" y "enteros positivos" dada por la función de emparejamiento de Cantor.

Una forma de responder a todo el ejercicio es proporcionar inyecciones a->b, b->c, c->a. Entonces se hace por Cantor-Schröder-Bernstein. Proporcionaré pistas para cada una de ellas.

• Una inyección a->b: dado un par de conjuntos de naturales, necesitamos hacer un único conjunto de pares de naturales. Si se sabe que los dos conjuntos tienen el mismo tamaño, es fácil: basta con emparejar los elementos. Pero puede que no tengan el mismo tamaño, así que en general habrá que rellenar uno de los conjuntos de alguna manera. Yo recomendaría multiplicar todo por $2$ para que tengas infinitos números (impar) con los que rellenar.
• Una inyección b->c: dado un conjunto de pares de naturales, hay que hacer un conjunto único de naturales. Eso es muy fácil por un truco estándar (pista: etiquetar cada miembro de su conjunto de naturales con el conjunto de donde vino, mediante el uso de la paridad y la imparidad).
• Una inyección c->a: dado un conjunto de naturales, hay que hacer un par único de conjuntos de naturales. Esta es la más fácil, y no necesitas hacer ningún trabajo para esto.