¿Cuál de los siguientes conjuntos tiene la mayor cardinalidad? (Asignatura de matemáticas del examen GRE 0568 P.61 )

Question

¿Cómo puedo resolver esta pregunta en sólo 2,5 minutos? Hay que resolverla utilizando una profunda visión e intuición, que yo no tengo. ¿Podría alguien ayudarme, por favor?

Gracias.

61. ¿Cuál de los siguientes conjuntos tiene la mayor cardinalidad?

    (A) $\mathbb{R}$

    (B) El conjunto de todas las funciones de $\mathbb{Z}$ a $\mathbb{Z}$

    (C) El conjunto de todas las funciones de $\mathbb{R}$ a $\{0, 1\}$

    (D) El conjunto de todos los subconjuntos finitos de $\mathbb{R}$

    (E) El conjunto de todos los polinomios con coeficientes en $\mathbb{R}$

Answer 1

Esta es una de esas preguntas en las que habría que tener algún conocimiento previo sobre cardinalidades de tamaños infinitos. No creo que alguien pueda hacer esta pregunta a ojo sin haber trabajado antes con cardinales infinitos.

$(a)$ tiene tamaño $2^{\aleph_0}$ ; $(b)$ tiene tamaño $|\mathbb{Z}|^{|{\mathbb{Z}}|} = \aleph_0^{\aleph_0} = 2^{\aleph_0}$ (c) tiene un tamaño $2^{|\mathbb{R}|} = 2^{(2^{\aleph_0})}$ ; (d) y (e) son el tamaño de $\mathbb{R}$ que de nuevo es $2^{\aleph_0}$ . Por lo tanto, la respuesta es (c).

Como hay cierto debate, demostraremos que (e) está acotado por el tamaño de los reales. Sea $P(\mathbb{R})$ sea la colección de todos los polinomios sobre $\mathbb{R}$ . Sea $P_n(\mathbb{R})$ sea la colección de todos los polinomios de grado $n$ . Entonces $P(\mathbb{R})=\bigcup_{n\in\mathbb{N}}P_n(\mathbb{R})$ . Ahora, $|P_n(\mathbb{R})| = |\prod_{i =1}^n \mathbb{R}|$ . Por lo tanto, $$|P(\mathbb{R})| = |\bigcup_{n\in\mathbb{N}}P_n(\mathbb{R})| \leq \sum_{n \in \mathbb{N}} |P_n(\mathbb{R})| = \sum_{n \in \mathbb{N}}|\prod_{i=1}^n \mathbb{R}|= \sum_{n\in \mathbb{N}} |\mathbb{R}| = |\mathbb{R}|$$

Un argumento muy similar muestra que (d) está limitado por el tamaño del $\mathbb{R}$ . En particular, se sustituye $P_n(\mathbb{R})$ con conjuntos de tamaño $n$ .

Answer 2

En realidad, no es necesario calcular todos los tamaños de estos objetos, pero sí es necesario saber un poco sobre cómo se combinan los distintos infinitos.

Los hechos:

1. El conjunto de potencias de un conjunto es mayor que el propio conjunto.

2. Una suma contable de copias de $\mathbb{R}$ tiene la misma cardinalidad que $\mathbb{R}$ .

Esto significa que de inmediato, podemos ver que $A$ , $D$ y $E$ son del mismo tamaño.

$D$ : Hay menos subconjuntos de $\mathbb{R}$ de tamaño $n$ que hay puntos en $\mathbb{R}^n$ (una ordenada $n$ -puede definir un subconjunto de $\mathbb{R}$ de tamaño $n$ ). Cada uno de $\mathbb{R}^n$ es del mismo tamaño y al sumarlos todos se obtiene una suma contable.

$E$ : Es más fácil pensar en esto en términos de una sola variable, pero funciona para un número contable de variables. El conjunto de polinomios se puede escribir como: $$ \mathbb{R}+x\mathbb{R}+x^2\mathbb{R}+x^3\mathbb{R}+\cdots $$ se trata de una suma contable de copias de $\mathbb{R}$ , por lo que es del mismo tamaño que $\mathbb{R}$ .

$C$ : Ahora, podemos ver que $C$ es estrictamente mayor que $A$ , $D$ y $E$ . Si se toma una función $f:\mathbb{R}\rightarrow\{0,1\}$ Esto corresponde a un subconjunto de $\mathbb{R}$ tomando los elementos de $\mathbb{R}$ que se asignan a $1$ . Como esto puede hacerse para cualquier subconjunto de $\mathbb{R}$ estas funciones están en correspondencia de biyección con el conjunto de potencias de $\mathbb{R}$ . Por lo tanto, $C$ es mayor que $A$ , $D$ y $E$ .

$B$ : El conjunto de funciones de $\mathbb{Z}$ a sí mismo se puede trabajar de la siguiente manera. En lugar de mirar las funciones de $\mathbb{Z}$ a $\mathbb{Z}$ , podemos buscar funciones de $\mathbb{N}$ a $\mathbb{N}$ ya que estos tienen el mismo tamaño. Esto significa que estas funciones son lo mismo que las secuencias a los números naturales. Este es el mismo tamaño que $\mathbb{R}$ porque uno podría mapearlos en $\mathbb{R}$ mediante fracciones continuas (u otros medios). Es probable que haya una manera más fácil de ver esto último, ya que las fracciones continuas no son tan comunes en los GRE. Consulta los comentarios para ver formas alternativas de ver la cardinalidad de este conjunto.

Answer 3

Estos son también algunos enlaces importantes para resolver mi pregunta (al menos desde mi punto de vista):

(A) $\mathbb R$ es incontable

(B) ¿Cuál es la cardinalidad del conjunto de todas las funciones de $\mathbb{Z} \to \mathbb{Z}$ ?

(C) ¿Cuál es la cardinalidad del conjunto de todas las funciones de $\mathbb{R}$ a {0,1}?

(D) Cardinalidad del conjunto de todos los subconjuntos finitos de $\mathbb{R}$

(E) Cardinalidad del conjunto de todos los polinomios con coeficientes en $\mathbb R$

Answer 4

(C) es realmente $\beth_2$ mientras que las otras opciones son todas $\beth_1$ . Como $\beth_n=2^{\beth{n-1}}\gt \beth_{n-1} $ hemos terminado. Que el conjunto potencia tiene mayor orden que el conjunto original se deduce del argumento diagonal de Cantor. ..