Si toma infinitos pasos para demostrar que un enunciado, que es una prueba válida?

Question

En el Cantor de la diagonal argumento, toma (contables) infinitos pasos para construir un número diferente de cualquiera de los números en una contables secuencia infinita, por lo que, de hecho, la prueba se lleva a infinitos pasos. Es que una prueba válida?

Answer 1

Tomar la Cantorian diagonal argumento de que, dado un contable de la secuencia de infinitas cadenas binarias, debe ser una cadena no en la secuencia. Para obtener el argumento de que volar no es necesario realmente construir el anti-diagonal de la cadena en el sentido de imprimir todos los dígitos (que de hecho sería una tarea infinita)! Usted sólo tiene que ser capaz de especificar la cadena -- como es conocido, es aquel cuyas $n$-ésimo dígito es 1 si $n$dígitos de la $n$-ésimo de la cadena en el contable de la secuencia es 0, y 0 en caso contrario. Y sólo a partir de esa finito (!) especificación, se deduce que este especificado infinita cadena es distinta de todas las cadenas en la lista original. Usted no tiene que, en realidad, per impossibile, construir (en el sentido de escribir todas) la cadena para ver eso!

Es el mismo, por supuesto, con la Cantorian argumento para, por ejemplo, la uncountability de los reales entre 0 y 1.

Answer 2

En la habitual lógica empleada en las matemáticas y en la mayoría de los sistemas relacionados, una prueba tiene que tener sólo un número finito de pasos. Esto significa que en el nivel formal, no interpretada lenguaje, una prueba tiene que tener sólo un número finito de pasos.

Pero uno puede usar un lenguaje en el que todas las pruebas son finitos para hacer argumentos que colindan con infinitary teorías, como la teoría de conjuntos. Y la lengua habitual de la lógica expresiva suficiente para hacer infinitary declaraciones en un número finito de instrucción. El intuitivo conjunto de la infinidad de declaraciones "$1<2$", "$2<3$", "$3<4$", y así es lo mismo que "$\forall n: n<n+1$", que consta de un total de $8$ símbolos y es demostrable en un número finito de pasos a partir de los axiomas de la aritmética de Peano.

Es fácil crear un finita de la teoría de que sólo tiene infinitos modelos. Por ejemplo, es muy fácil axiomatize la teoría de la estricta parcial de las órdenes sin máximo de elementos con los tres axiomas:

1. $\forall x:\neg(x>x)$
2. $\forall x,y,z:(x<y)\wedge (y<z)\implies (x<z)$
3. $\forall x\exists y:x<y$.

Por un argumento estándar, cada finito estricto orden parcial tiene un elemento maximal, por lo que esta teoría describe sólo infinita estricto parcial de las órdenes.

En la teoría de conjuntos, sólo utilizamos finito de pruebas y tienen una contables idioma. Esto da lugar a la llamada paradoja de Skolem que una teoría lidiar con innumerables conjuntos puede tener un modelo de contables de la cardinalidad. Pero dentro de la teoría, podemos lidiar con muchos tamaños de infinito y hacer las operaciones que corresponden a una infinidad de operaciones en un idioma más débil. Y es el lenguaje formal en el que la teoría de conjuntos es formulado en el que todas las pruebas son de longitud finita.

Answer 3

En primer lugar, vamos a tratar con su confusión acerca del teorema de Cantor. Aquí me parece que probar que es el caso general, hace que sea mucho más claro que no hay nada especial acerca de los números que se utiliza.

Deje $X$ ser un conjunto, vamos a $\mathscr{P}(X)$ el conjunto de los subconjuntos de a $X$, y deje $f : X \to \mathscr{P} (X)$ ser un mapa. Se define un subconjunto $$C_f = \{ x \in X : x \notin f (x) \}$$ y se observa que el $C_f \ne f (y)$ cualquier $y$$X$. En efecto, supongamos $C_f = f (y)$. A continuación, $y \in C_f$ si y sólo si $y \notin C_f$ – una contradicción. Por lo $C_f \ne f (y)$. Llegamos a la conclusión de $f : X \to \mathscr{P} (X)$ no es surjective.

Creo que es bastante obvio aquí que tenemos un número finito de prueba, aunque $X$ puede ser un conjunto infinito. Con esto en mente, es fácil ver por qué la prueba de la uncountability de los números reales es un número finito de uno: no tenemos para construir el contraejemplo de la etapa por etapa, en cualquier sentido – acabamos de definir en un solo golpe tal y como hicimos con $C_f$.

---

Aquí está un ejemplo real de un infinito "prueba" de que resulta ser inválida. Supongamos que de primer orden de la Aritmética de Peano (PA) es constante. A continuación, cada una de las siguientes afirmaciones pueden ser formalmente demostrado en PA:

• $0$ no código de la prueba de una inconsistencia en PA.
• $1$ no código de la prueba de una inconsistencia en PA.
• $2$ no código de la prueba de una inconsistencia en PA.
• etc.

Es tentador decir que PA la prueba

• Para todos $n$, $n$ no código de la prueba de una inconsistencia en PA.

pero de hecho esto es falso, porque estaría en contradicción con Gödel del segundo teorema de la incompletitud. Básicamente, esto es debido a que las entidades $n$ que el PA considera números naturales son potencialmente no estándar; por ejemplo, por el teorema de compacidad de primer orden de la lógica podemos construir un incontable modelo de PA, que por obvias razones debe contener no estándar de los números. Por lo tanto, estamos obligados a concluir que la infinitary regla de inferencia

• De $\phi (0), \phi (1), \phi (2), \ldots$, deducir $\forall n . \phi (n)$.

es inadmisible para la PA.

Answer 4

Puesto que usted tiene un computabilidad doblado, aquí es otra versión del teorema de Cantor:

Deje $T$ ser una máquina de Turing que imprime una secuencia de salidas. Cada una de las salidas de $T$ es la especificación de una máquina de Turing que imprime una secuencia de números.

El Cantor del argumento dice que existe una máquina de Turing $S$ que imprime una secuencia de números que no se imprime por cualquiera de las salidas de $T$: específicamente la máquina de Turing:

• Para cada número natural $n$:
  • Simular $T$ a obtener es $n$-ésimo de salida.
  • Si $T$ se ha interrumpido de forma prematura:
    • La salida es 0
    • Halt.
  • Deje $M$ $n$- th salida de $T$.
  • Simular $M$ a obtener es $n$-ésimo de salida.
  • Si $M$ ha detenido:
    • La salida es 0.
  • Otra cosa
    • Deje $x$ $n$- th salida de $M$.
    • Salida $x+1$

Además, no es difícil ver que existe una máquina de Turing que, dada la especificación de cualquier $T$ la satisfacción de las hipótesis, es la salida de la especificación de la correspondiente máquina de Turing $S$.

Answer 5

Mientras la naturaleza de los pasos es formalista, no veo ningún problema con ello. La prueba de la igualdad de cardinalidad de Dedekind-infinito de conjuntos es similar. Para probar que dos conjuntos tienen la misma cardinalidad, se define un bijection que se transforma a cada elemento de un conjunto a un único elemento de la otra, sin "agujeros", sin duplicados y sin ambigüedades (uno de los elementos en la transformación de cualquiera de los dos elementos). Si un bijection existe, entonces uno puede decir que mediante la aplicación de la bijection a cada uno de los (infinitos) los elementos de la fuente, de un único elemento del conjunto de destino se crea, y por lo tanto los conjuntos tienen el mismo número de elementos (incluso a pesar de que el número es infinito).