Bijection $f : \mathbb{N} \rightarrow \mathbb{A}$ de las naturales a las algebraicas

Question

Estoy haciendo una presentación sobre el artículo de Godel "¿Qué es el problema del continuo de Cantor?", y me gustaría incluir una demostración computacional de la contabilidad de los números algebraicos.

Estoy buscando una biyección explícita $f : \mathbb{N} \rightarrow \mathbb{A}$ de los números naturales a los algebraicos (preferiblemente de forma que $f(n)$ se puede calcular con relativa rapidez).

El plan es codificar un algoritmo basado en esta biyección y ejecutarlo durante la charla, escupiendo una secuencia no repetitiva de números algebraicos durante 50 minutos. Por supuesto, no es una prueba de contabilidad, sólo una demostración. Supongo que su construcción será similar a la de la bijección "zig-zag". $\mathbb{N} \rightarrow \mathbb{Q}$ .

Gracias de antemano.

Answer 1

Dado cualquier polinomio $f(x) \in \mathbb{Z}[x]$ Escriba $f(x) = a_1 + a_2 x + a_3 x^2 + \cdots + a_{n+1} x^n$ .

Sea $p(n)$ denotan el $n$ el primero.

Entonces podemos asignar $f(x)$ a $\prod_{k = 1}^{n+1} {p_k}^{a_k} \in \mathbb{N}$ .

También puedes ver cómo funcionaría la asignación inversa.

Por ejemplo, el número natural $63 = 3^2 \cdot 7^1$ correspondería al polinomio $g(x) = 2x + x^3$ .

Así que podrías encontrar un mapeo de cada número natural a un polinomio, luego calcular las raíces de ese polinomio y luego enumerarlas. A continuación, repita el proceso para el siguiente número natural, descartando cualquier repetición de raíces. Así obtendremos una lista de todos los números algebraicos.

Observación: Dado que encontrar exactamente las raíces de un polinomio es una tarea bastante difícil (para polis de grado superior a $4$ ) Creo que dar el argumento anterior sería mejor que tener un código vomitando algo. Aunque es sólo mi preferencia personal.

Answer 2

Hay finitamente muchos polinomios con coeficientes enteros tales que el grado más la suma de los valores absolutos de los coeficientes es igual a $n$ para cada número natural $n$ . Se pueden enumerar las raíces de estos polinomios para $n=1,2,3,\ldots$ omitiendo números que ya has visto si realmente necesitas una función inyectiva. Cada número algebraico aparece en esta enumeración.