El teorema de Геделя sobre incompleto de 20 minutos Bashny.Net

El teorema de Геделя sobre incompleto, uno de los más famosos teoremas de la lógica matemática, la suerte y la mala suerte a la vez. En esto se parece a la teoría especial de la relatividad de einstein.

Por un lado, casi todo acerca de ellos que escuchaste. Con el otro — en la interpretación de la teoría de einstein, como se sabe, "dice que todo en el mundo es relativamente". Y el teorema de Геделя de incompleto (en adelante, la ТГН), en aproximadamente la misma lucha libre folk-redacción, "demuestra que hay cosas inconcebibles para la mente humana".

Y he aquí algunos tratan de adaptar como un argumento en contra del materialismo, y otros, por el contrario, demuestran con su ayuda, que dios no existe. Es curioso, no sólo es que ambas partes no pueden ser de la derecha a la vez, sino que ni unos, ni los otros no удосуживаются comprender que, en realidad, este teorema afirma.



Entonces, ¿qué? A continuación trataré de "los dedos" contarlo. Resumen de mi ser, por supuesto нестрогим e intuitivo, pero le voy a pedir a los matemáticos no juzgar a mí estrictamente. Es posible que para нематематиков (a los que, en realidad, soy yo), en рассказанном a continuación será algo nuevo y útil.

La lógica matemática es una ciencia realmente es bastante complicado, y lo más importante — no es muy habitual. Se requiere un exacto y estrictos de las maniobras, en las que es importante no confundir realmente demostrada con el hecho de que "lo que es evidente". Sin embargo, espero que para la comprensión de la la siguiente siguiente "esbozo de la prueba de ТГН" el lector se necesita el conocimiento de la escuela de matemáticas/ciencias de la computación, habilidades de pensamiento lógico y a 15-20 minutos de tiempo.

Simplificando, ТГН afirma que en complejas de idiomas tienen недоказуемые de la enunciación. Pero en esta frase casi cada palabra necesita explicación.

Comencemos con el hecho de que tratemos de entender lo que es la prueba. Tomemos alguna escolar задачку de la aritmética. Por ejemplo, supongamos que desea demostrar la fidelidad a la siguiente sin complicaciones de la fórmula: "∀x(x−1)(x−2)-2=x(x−3)" (recordemos que el símbolo ∀ se lee "para todo" y se llama "el cuantificador universal"). Demostrar que se puede, es lo mismo que el transformando, digamos, así:

∀x(x−1)(x−2)-2=x(x−3)

∀xx2−3x+2-2=x2−3x

∀xx2−3x–x2+3x=0

∀x0=0

La VERDAD

 

La transición de una fórmula a otra se produce por alguna conocida de las reglas. La transición de 4º de la fórmula a la 5 ª se ha producido, digamos, porque todo número es igual a sí mismo — es un axioma de la aritmética. Y todo el procedimiento de la prueba, por lo tanto, la traducción de la fórmula en un valor booleano VERDADERO. El resultado podría ser una MENTIRA si nos refuta algún tipo de fórmula. En tal caso, habríamos demostrado su negación. Se puede imaginar un programa (y estos programas realmente se escriben), que han probado similares (y más complejos) de la enunciación, sin intervención humana.

Separado lo mismo un poco más formal. Supongamos que tenemos una multitud, compuesta por cadenas de caracteres de un alfabeto, y existen las reglas por las que desde estas líneas se puede seleccionar un subconjunto S de los llamados de expresión es decir, gramaticalmente significativas frases, cada una de las cuales es verdadera o es falsa. Se puede decir que existe una función de P, asigne las declaraciones de la S de uno de los dos valores de VERDAD: verdadero o FALSO (es decir, muestra su booleano que el conjunto B de los dos elementos).

Llamaremos a este tipo de pareja — en muchas expresiones S y la función P >S en el B — "la lengua de los dichos". Tenga en cuenta que en la vida cotidiana el sentido de la noción de lenguaje más amplio. Por ejemplo, la frase de la lengua rusa "¡ven aquí!" no era la verdadera, y no es falsa, es decir, desde el punto de vista de la lógica matemática, no es.

Para continuar necesitamos el concepto de algoritmo. Traer aquí formal, su definición no voy es завело nos llevará muy lejos en el lado. Limito informal: "el algoritmo" — esta secuencia de parámetros de instrucciones (el"programa"), que en un número finito de pasos traduce los datos de origen en el resultado.

Resaltado en cursiva, es fundamental — si en unos datos iniciales, el programa de fijarse, el algoritmo no se describe. Para la simplicidad y en la aplicación al caso nuestro, el lector puede considerar que un algoritmo es un programa escrito en cualquier conocido lenguaje de programación, que para cualquier entrada de datos de una clase dada garantiza que finaliza con la emisión de булевого resultado.

Pregúntense: para toda si la función P existe "probando el algoritmo" (o, en pocas palabras, "дедуктика"), el equivalente de esta función, es decir, переводящий cada cita es en el booleano, y que ella? Más compacto misma pregunta se puede formular así: toda si la función sobre la multitud de declaraciones вычислима?

Como verá, de la justicia ТГН que no hay, no todos — hay невычислимые funciones de este tipo. En otras palabras, no toda la acertada afirmación se puede demostrar.

Es muy posible que esta afirmación le causa interna de la protesta. Esto es debido a varias circunstancias. En primer lugar, cuando se nos enseña de la escuela de matemáticas, a veces se produce la falsa impresión de casi completa de la identidad de las frases "el teorema de X es verdadera" y "no se puede probar o comprobar el teorema de X".

Pero, si lo piensas, no es evidente. Algunos teoremas доказываются bastante simple (por ejemplo, un ataque de fuerza bruta a un pequeño número de opciones), y algunos — muy difícil. Recordemos, por ejemplo, la famosa Granteorema de la Granja:
 

No hay tales naturales x,y,z y n>2, que xn+yn=zn,

 

la prueba de la que sólo se encuentra a través de tres siglos y medio después de la primera redacción (y es no elemental). Condebe distinguir la verdad de la enunciación y su доказуемость. La nada no es que no hay verdaderas, pero недоказуемых (y no se analizan en plena) de expresión.

La segunda intuitivo argumento en contra de la ТГН más fino. Supongamos que tenemos algo de недоказуемое (en el marco de este дедуктики) la declaración. Lo que nos impide aceptar como nuevo axioma? Así que un poco усложним de nuestro sistema de pruebas, pero no es de miedo.

Este argumento sería totalmente fiel, si недоказуемых de declaraciones es un número finito. En la práctica, puede ocurrir lo siguiente — después de la afirmación de la nueva axiomas se tropiezan en el nuevo недоказуемое declaración. Recibiréis, como los axiomas — tropiezan a tercera. Y así hasta el infinito.

Dicen que дедуктика quedará incompleta. También podemos tomar medidas de fuerza, que demuestra el algoritmo termina a través de un número finito de pasos con el resultado de cualquiera de las declaraciones de la lengua. Pero él comienza a mentir — llevar a la verdad para los infieles de las declaraciones, o a la mentira para los fieles.

En estos casos, dicen que дедуктика es contradictoria. Por lo tanto, otro enunciado ТГН suena así: "los idiomas de los enunciados para los cuales no es posible la completa непротиворечивая дедуктика" — de ahí el nombre de teorema.

A veces se llama "el teorema de Геделя" la afirmación de que cualquier teoría contiene problemas que no pueden resolverse en el marco de la teoría y requieren de su generalización. En cierto sentido esto es cierto, aunque esta expresión sea la de la vela a la pregunta de lo que aclara.

Notar también que si se tratara de las funciones habituales que muestran un montón de números reales en él mismo, es "невычислимость" funciones de nadie que no hubiera sorprendido (no se debe confundir "вычислимые de la función" y "вычислимые el número de" son cosas diferentes).





Kurt Гедель

Cualquier los estudiantes se sabe que, por ejemplo, en el caso de una función sin⁡x se le debe fuerte que tengas suerte con el argumento de que el proceso de cálculo exacto de la representación decimal del valor de esta función ha terminado por un número finito de pasos.

Y es probable que usted va a calcular con la ayuda de la fila interminable, y esto nunca dará lugar a la exacta con el resultado, aunque puede acercarse a cualquiera de cerca — , simplemente porque el valor del seno de la mayoría de los argumentos irracionales. ТГН simplemente nos dice que, incluso entre las funciones, argumentos que son cadenas, y los valores de cero o la unidad de medida, невычислимые de la función, aunque muy diferente configuradas, son también.

Para seguir a describir "el lenguaje formal de la aritmética". Considere la clase de líneas de texto longitud final, formados por los números, variables (letras) que toman valores naturales, espacios, signos aritméticos, de igualdad y de desigualdad, de cuantificador ∃ ("hay") y ∀ ("para todo"), y, quizás, alguna otra caracteres (el número exacto y la composición para nosotros poco).

Está claro que no todas las filas sensatos (por ejemplo, "12=+∀x> — eso no tenía sentido). Un subconjunto significativas expresiones de esta clase (es decir, líneas que son verdaderas o son falsas desde el punto de vista convencional de la aritmética) y será nuestro multitud de declaraciones.
 

Ejemplos de declaraciones formales de la aritmética:

• 1=1
  
  
• 2×2=5
  
  
• ∃xx>3
  
  
• ∀y∀zy×z>y+z
  
  

 

y así sucesivamente, Ahora llamaremos "la fórmula de libre opción (efs) de la cadena, que se convierte en el refrán, si este parámetro poner en ella un número natural. Ejemplos de la efs (con la opción x):
 

• x=0
  
  
• 2×2=x
  
  
• ∃yx+y>x
  
  

 

y así sucesivamente, en Otras palabras, la efs son equivalentes a las funciones naturales de un argumento con булевыми valor.

Se denota el conjunto de todas las efs de la letra F. está Claro que se puede organizar (por ejemplo, primero daremos ordenados alfabéticamente однобуквенные de la fórmula, detrás de ellos — normalizados de dos letras, etc.; en qué orden alfabético tendrá lugar el deslinde, nos непринципиально). Por lo tanto, cualquier efs se corresponde con su número de k en la lista ordenada, y lo vamos a denotar su Fk.
 

Pasemos ahora a la наброску pruebas ТГН tipo de formulación:

Para el idioma enunciado formal de la aritmética no existe plenamente coherente дедуктики.

Vamos a demostrar de lo contrario.

Supongamos que esta дедуктика existe. Describir el auxiliar el algoritmo A, y pone en el cumplimiento de número natural k, el valor booleano de la siguiente manera:

1. Encontramos k-yu fórmula en la lista de F.

2. Подставляем en ella el número de k como argumento.

3. Aplicamos a la obtenida dicho nuestro probando el algoritmo (en nuestro supuesto, existe), que se traduce en la VERDAD o la MENTIRA.

4. Aplicamos la lógica de la negación al resultado obtenido.

En pocas palabras, el algoritmo hace que el valor de la VERDAD, entonces, y sólo entonces, cuando el resultado de la búsqueda en la efs de su propia habitación en nuestra lista da una falsa declaración.

Aquí llegamos al único lugar en el que quiero que el lector de creer en mí por la palabra.

Es evidente que, al formulada por encima supuesto, cualquier efs de F se puede asignar un algoritmo que contiene en la entrada de un número natural, y a la salida – valor booleano.

Menos obvio lo contrario:
 

Lema: Cualquier algoritmo, переводящему un número natural en un valor booleano cumple alguna de la efs de la multitud de F.

 

Prueba de esta леммы requeriría, como mínimo, la enseñanza formal y no intuitivo, la definición de algoritmo. Sin embargo, si un poco de pensar en ello, es bastante plausible.

En realidad, los algoritmos se escriben en алгоритмических idiomas, entre los cuales hay tan exóticos como, por ejemplo, Brainfuck, que consta de ocho односимвольных palabras, en el que, sin embargo, se puede implementar cualquier algoritmo. Extraño sería si descrito a nosotros más rico fórmulas de lenguaje formal de la aritmética sería el más pobre — aunque, sin duda, para regular la programación no es muy adecuado.

Después de pasar es resbaladizo, lo que rápidamente acceder hasta el final.

Así que, anteriormente, hemos descrito el algoritmo A. Según лемме, en la que he pedido a usted a creer, existe un equivalente a la de él, la efs. Tiene un número de la lista F — digamos, n. Pregúntense, lo que es igual a Fn(n)? Que es la VERDAD. Entonces, de la construcción de un algoritmo de A (es decir, el equivalente de su función (Fn), esto significa que el resultado de la sustitución de un número, n, de la función Fn — MENTIRA.

De manera similar se comprueba lo contrario: la de Fn(n)=FALSO debe Fn(n)=VERDAD. Hemos llegado a una contradicción, entonces, la suposición es incorrecta. Por lo tanto, para formal de la aritmética no existe plenamente coherente дедуктики. Que se quería demostrar.

Es oportuno recordar Эпименида, que, como se sabe, dijo, que todos los cretenses — los mentirosos, a sí mismo como критянином.En más concisa la formulación de su declaración (conocida como "paradoja del mentiroso") se puede formular así: "Yo miento". Precisamente en esa declaración, la misma превозглашающее su falsedad, y hemos utilizado para la prueba.

En conclusión, quiero señalar que la nada especial sorprendente ТГН no aprueba. Al final, todo se hace mucho acostumbrados, que no todos los números представимы en la forma de una relación entre dos enteros (recuerda, esta afirmación es muy elegante prueba de que más de dos mil años?). Y las raíces полиномов con coeficientes racionales son, también, que no todos los números. Y ahora sabemos que no todas las funciones natural argumento вычислимы.

El esbozo de la prueba se refería formal de la aritmética, pero no es difícil de entender, que ТГН es aplicable a muchos otros idiomas de expresión. Por supuesto, no todos los idiomas son. Por ejemplo, definir el idioma de la siguiente manera:
 

"Cualquier expresión del idioma chino es cierto el refrán, cuando se encuentran en цитатнике camarada mao Jo dong, y es falso, si o no".

 

Entonces correspondiente al completo y coherente probando el algoritmo (se le puede llamar "dogmática дедуктикой") se parece a esto:
 

"Листай цитатник camarada mao Jo dong, hasta que no lo encontrarás buscando en la declaración. Si se encuentra, es cierto, y si цитатник terminó, y la declaración no se encuentra, no es válida".

 

Aquí nos salva lo que cualquier цитатник, obviamente, es finito, por lo tanto, el proceso de "prueba", inevitablemente terminará. Por lo tanto, al lenguaje de la dogmática declaraciones ТГН no es aplicable. Pero nosotros ya que hablaban sobre los complejos idiomas, ¿verdad? publicado

 



Fuente: geektimes.ru/post/284486/