El argumento diagonal de Cantor se encuentra con la lógica

Question

(Yo no soy normalmente lidiar mucho con la teoría de conjuntos y la lógica, así que discúlpame si mi elección de palabras de abajo parece un poco fuera de la tradicional terminología.) ¿De dónde viene el siguiente Cantor inspirado argumento ir mal?

Deje $\Sigma = \{A_0,A_1,A_2,\ldots\}$ ser el contable de la colección de declaraciones con una variable libre tal que para todos los $n\ge 0$, $$ \existe!x_n\in [0,1):A_n(x), $$ donde por $[0,1)$ me refiero al intervalo. ($\Sigma$ es contable, derecho? Las declaraciones deben consistir de un número finito de caracteres después de todo.) Ahora escribo $x_n$ en los decimales, como $$ x_n =\sum_{k=1}^\infty x_n^{(k)}10^{-k} $$ donde $x_n^{(k)}\in\{0,1,\ldots,9\}$ todos los $k\ge 1$ (nos aseguramos de que nunca para escribir por ejemplo,$0.1$$0.099999\ldots$). Ahora ponga $$ y^{(k)}=\begin{cases} 1 & \text{if %#%#%}\\ 2 & \text{else}. \end{casos} $$ Como era de esperar, ponemos $$ y:=\sum_{k=1}^\infty y^{(k)}10^{-k}. $$ Ahora $x_k^{(k)}\neq 1$ todos los $y\neq x_n$, al igual que en el Cantor del clásico argumento. Pero la definición anterior de $n$ debe: (I think---pero esto podría estar donde estoy equivocado) de ser posible formalizar en lógica de primer orden. En otras palabras, no existe una declaración de $y\in [0,1)$ tal que $A$ es el único número en $y$ tal que $[0,1)$ es cierto. Por lo tanto $A(y)$, lo que obviamente es una contradicción.

Answer 1

La declaración "se puede formalizar en lógica de primer orden" es problemático. La lógica de primer orden no es sólo una cosa, es un marco de trabajo para un montón de cosas.

Hable acerca de la definición de un elemento, por lo que es necesario especificar el lenguaje, la estructura y así sucesivamente. El problema es que no se puede cuantificar sobre las declaraciones, y, cuando se enumeran las declaraciones.

Mientras que usted puede, en teoría, hacer que dentro de una teoría en particular (por ejemplo, se puede cuantificar sobre los números de Gödel), la teoría debe tener algunas propiedades (por ejemplo, la capacidad para interpretar la lógica de primer orden interno). Y no le ha dicho a nosotros ¿qué es la teoría.

Incluso más que eso, si se las arreglan para tener la teoría de interpretar esta internamente, sigue funcionando en la Tarski del teorema que dice que la verdad no es de primer orden definibles. Así que usted no puede utilizar un predicado de verdad para arbitrario fórmula; por lo que tendría que limitar las fórmulas de una cierta clase que usted puede internamente definir un predicado de verdad.

Si usted ha hecho todo eso, y su teoría admite suficiente inducción como argumentos, entonces sí, probablemente es factible. Pero no nos han dado alguno de los datos mencionados.

Por otro lado, el Cantor de la diagonal argumento no es en el primer orden de teoría de la $\Bbb R$ o de cualquier otra estructura. Se trata de un conjunto teórico de la argumentación. Por lo que se hace en un contexto mucho más amplio marco de la teoría de conjuntos. Esto nos permite cuantificar sobre los conjuntos de los números reales, y de preformas de inducción internamente a la teoría de conjuntos; a pesar del hecho de que la teoría de conjuntos es una de primer orden de la teoría.

Por qué? Porque en la teoría de conjuntos los conjuntos son los elementos del universo. Como mucho se puede discutir sobre los números primos que dividen a $2^{1379123}-1$ dentro de la teoría de la aritmética; se puede hablar de los subconjuntos de a $\Bbb R$ en el conjunto de la teoría.

Así que dentro de la teoría de conjuntos, se puede formalizar todas estas nociones, internamente la lógica de primer orden y, a continuación, hablar de esta enumeración de fórmulas y así sucesivamente, y, a continuación, defina $y$. Pero esto no se hace en primer orden de la teoría dentro de la estructura de $[0,1)$.