¿qué es un número real "definible"?

Question

Wikipedia afirma que un número definible (real) es un número "que puede ser especificado de forma única por su descripción". Ingenuamente pensé que esto era lo mismo que "un número que puede ser calculado", pero en otra parte de math.SE Descubrí que no es el caso, porque por ejemplo los números relacionados con la Chaitin's $\Omega$ son definibles pero no computables. ¿Podría alguien explicarme qué es un especificación es, entonces? Siempre pensé que $\Omega$ era un valor de probabilidad, que no era una especificación real.

Answer 1

"Definible" es siempre relativo a un lenguaje particular en el que se expresa la definición.

Un número es definible si hay una propiedad expresada en ese lenguaje que se satisface para ese número pero por ningún otro.

No hay ninguna expectativa particular de que el lenguaje que utilizamos para la definición sea lo suficientemente "ejecutable" como para señalar el número con una precisión particular. Como ejemplo, podemos considerar las definiciones en el lenguaje completo de primer orden de la teoría de conjuntos, donde $$ (x=1\land\text{the Riemann Hypothesis is true})\lor(x=-1\land\text{the Riemann Hypothesis is false})$$ puede expresarse como una propiedad perfecta que define un número entero no nulo $x$ -- pero ni siquiera sabemos el signo del número que se define.

La constante de Chaitin en realidad no es una constante única, sino que depende de la selección de una representación de las máquinas de Turing en primer lugar. Ligeramente simplificado, una vez que hemos seleccionado una enumeración $T_n$ de las máquinas de Turing, obtenemos una constante de Chaitin $$ \Omega = \sum_{n=1}^\infty \begin{cases} 2^{-n} & \text{if }T_n\text{ terminates} \\ 0 & \text{otherwise} \end{cases} $$ lo cual, de nuevo, es una buena definición (que una determinada máquina de Turing termine es una bien definido propiedad), pero no podemos computa la constante porque el hecho de que una determinada máquina de Turing termine no es computable .

(Esto puede también interpretarse como una probabilidad: Recorra todas las máquinas de Turing en secuencia, lanzando una moneda para cada una y seleccione la primera máquina en la que obtenga cruz; ¿cuál es la probabilidad de que esta máquina elegida al azar termine? Pero el hecho de ser una probabilidad no influye en sí mismo en que el número esté bien definido y/o sea computable).

Answer 2

Los números definibles dependen de cómo se definan. Dado que "el menor número entero positivo no especificable en menos de doce palabras" es una frase de once palabras, obtenemos algo llamado la paradoja de Berry, a menos que reconozcamos que la norma de especificación debe excluir la referencia a sí misma. Formalmente, esta separación se basa en un lenguaje objeto y un metalenguaje para hablar de él, de modo que "el menor número entero positivo no especificable en menos de dieciséis palabras de ese lenguaje objeto" puede existir como descripción en el metalenguaje, pero no en el lenguaje objeto; pero esto obliga a que la definibilidad sea relativa.

El punto importante es el siguiente: no importa qué especificación se formalice, si sólo se permiten descripciones de longitud finita en un lenguaje con un alfabeto contable, sólo se podrá definir un número contable de cosas. (A grandes rasgos, esto se debe a que $\sum_{n=0}^\infty\aleph_0^n=\aleph_0$ .) Desde $\mathbb{R}$ es incontable, seguro que te dejas algo.

Answer 3

"Definible" como un significado muy preciso. Dada una estructura $M$ en un lenguaje de primer orden $\mathcal L$ , un elemento $a\in M$ es definible si y sólo si existe una fórmula $\varphi(x)$ en una variable tal que $$ M \models \forall x, \varphi(x) \leftrightarrow (x=a)$$

En particular, "definible" es siempre relativo al lenguaje de especificación. Por ejemplo, dado $M$ como antes, un elemento $a\in M$ es siempre definible en (la estructura inducida en) $M$ sobre la lengua $\mathcal L \sqcup \{c_a\}$ donde la nueva constante $c_a$ se interpreta como $a$ (el buscado $\varphi(x)$ es simplemente " $x=c_a$ "). Incluso si $a$ no era definible sobre $\mathcal L$ .

---

Al decir "¿Es el número real $a$ definible", es probable que la gente quiera decir: dado un modelo $\mathcal S$ de ZFC, es (el conjunto correspondiente a) el número real $a$ (en la codificación habitual de los reales en ZFC) definible sobre el lenguaje $\{{\in}\}$ ?

Como nadie conoce un modelo explícito de ZFC, es muy probable que "el número real $a$ " es en realidad ya un atajo para la fórmula $\varphi(x)$ . Volviendo a tu pregunta, cuando la gente dice "constante de Chaitin", no se refiere a un elemento específico de un modelo divino de ZFC, se refiere a la construcción que probablemente conoces: enumera las máquinas de Turing contablemente infinitas como $m_1,\dots$ y afectan al valor $t_i=0$ si $m_i$ termina o $t_i=1$ en caso contrario, crea el número $\sum_{i=1}^\infty t_i10^{-i}$ . Todo eso es completamente expresable en el lenguaje $\{{\in}\}$ bajo los axiomas de ZFC. En particular, lo que le molesta es el "si $m_i$ termina", pero la terminación de una máquina de Turing es una propiedad que puede ser codificada en ZFC una vez que la noción de máquina de Turing es codificada en ZFC. (ZFC estaría haciendo un mal trabajo como fundamento de las matemáticas si tales cosas no fueran expresables).