Escribir Una Prueba

Como escribir una prueba

Leslie Lamport

El americano matemático mensual, vol.102, No 7(1995), 600-608

1. PRUEBAS DE MATEMÁTICAS. La notación matemática ha mejorado en los últimos siglos. En el siglo XVII, un matemático podría haber escrito.

No existen cuatro enteros positivos, el último siendo mayor de dos, de tal manera que la suma de los dos primeros, cada uno elevado a la potencia de la cuarta, es igual a la tercera potencia elevada al mismo. (1)

Cuánto más fácil es leer la versión moderna

No existen números enteros positivos x, y, z, y n, con n> 2, tal que xn + yn = zn. (2)

Sin embargo, la estructura de las pruebas matemáticas no ha cambiado en 300 años. Las pruebas en los Principios de Newton difieren en estilo de las de un moderno libro de texto sólo por estar escrito en latín. Las pruebas se siguen escribiendo como ensayos, en una forma pomposa de la prosa ordinaria.

Las fórmulas escritas en prosa, como (1), son difíciles de entender y difícil de acertar. Las pruebas escritas en prosa también son difíciles de entender y difícil de acertar. La evidencia anecdótica sugiere que hasta un tercio de todos los artículos publicados en revistas matemáticas contener errores-no sólo errores menores, pero los teoremas y demostraciones incorrectas.

Declaración (2) es más fácil de leer que la declaración de (1) por dos razones: las variables se les asignan nombres, fórmulas y se escriben de una manera más estructurada.

Los beneficios del uso de nombres es obvia. El beneficio de la estructura es menos obvio, estamos tan acostumbrados a fórmulas como xn + yn = zn que tendemos a tomar su estructura por sentado, y pensar que son fáciles de leer sólo porque son cortos. A pesar de la brevedad de la fórmula ayuda, es sobre todo su estructura que hace que sea más fácil de entender que una versión en prosa. La expresión

x elevado a la potencia n

Más

y elevado a la potencia n es igual a z elevado a la potencia n

es bastante larga, pero es fácil de leer debido a su estructura.

Los mismos principios que conforman las fórmulas más fáciles de entender puede facilitar las pruebas de entender: los pasos de prueba debe ser referido por su nombre, y la estructura de la prueba debe ser manifiesta.

El estilo prueba que defiendo es un refinamiento de uno, llama deducción natural que ha sido utilizado por algunos lógicos durante casi un siglo. Deducción natural se ha visto principalmente como un método de escritura de pruebas en una lógica formal.

Lo que voy a describir es un método práctico para la escritura de las pruebas menos formales de las matemáticas ordinarias. Se basa en la estructuración jerárquica, una herramienta eficaz para la gestión de la complejidad.

Un método para la estructuración de las pruebas fue presentado por Leron [5]. Sin embargo, su objetivo era comunicar las pruebas mejor, no para que sean más rigurosos.

A pesar de su estructuración jerárquica, el abogado Leron pruebas son muy diferentes de las que se presentan aquí. Ellos no parecen ser mejores que las pruebas convencionales para evitar errores.

Evitar errores en la manipulación de fórmulas requiere cálculos cuidadosos y detallados. Evitar errores al demostrar teoremas requiere pruebas cuidadosas y detalladas. Cuando se muestra por primera vez una prueba detallada, estructurada, la mayoría de los matemáticos reaccionar: "Yo no quiero leer todos los detalles, quiero leer sólo el esquema general y tal vez algunas de las partes más interesantes." Mi respuesta es que esto es precisamente por qué quieren leer una prueba estructurada jerárquicamente. La estructura de alto nivel proporciona el esquema general, los lectores pueden ver tanto o tan poco como de los detalles de bajo nivel que quieran. Sin embargo, hasta que uno se acostumbra a ellos, las pruebas estructuradas se ven intimidante.

La herramienta ideal para la lectura de una prueba estructurada sería un sistema basado en ordenador de hipertexto. Esto permitiría al lector a concentrarse en un determinado nivel en la estructura, la supresión de niveles inferiores detalles. En una versión impresa, se puede ignorar detalles de nivel inferior sólo pasar por encima de la parte del texto.

Mientras esto no es ideal, la estructura se muestra por el formato, por lo que tales saltos bastante fácil ciertamente mucho más fácil que en una prueba de prosa de estilo, donde el formato proporciona poca información de la estructura lógica.

Ejemplo 2

Tomo como ejemplo la prueba clásica que √ 2 es irracional. Dejar Q denotar el conjunto de los racionales, la indicación precisa del resultado que debe probar es

Teorema No existe r en Q, tal que r2 = 2.

Para ilustrar la estructura jerárquica, la prueba se lleva a cabo a un nivel mucho más bajo de detalle de lo necesario para un lector típico.

2.1 La prueba de alto nivel

La estructura de alto nivel de la prueba de lo que se podría ver primero con un sistema de hipertexto-aparece en la figura 1. La prueba supone un lema del que se puede deducir que, para cualquier entero n, si 2 divide a n2 entonces 2 divide a n.

El conjunto de los enteros se denota por Z

Teorema No existe r en Q, tal que r2 = 2.

Esbozo de prueba: Asumimos r2 = 2 para r ∈ Q y obtener una contradicción. Escrito

r = m / n, donde m y n no tienen divisores comunes (paso 1), se deduce a partir de

(M / n) 2 = 2 y el lema de que tanto m como n debe ser divisible por 2 (pasos 2 y 3).

Supongamos que: 1. r ∈ Q

2. r2 = 2

Prueba: falsa

1. Elija m, n en Z de tal manera que

1. mcd (m, n) = 1

2. r = (m / n)

2. 2 divide m.

3. 2 divide a n.

4. Lo que había que demostrar

Figura 1: El nivel más alto de una prueba estructurada de la irracionalidad de

√ 2.

Después de la declaración del teorema viene un Esbozo de prueba, que es una explicación informal de la prueba siguiente. El boceto prueba sirve como una "hoja de ruta" para la prueba, lo que ayuda al lector a comprender intuitivamente por qué la prueba funciona. Esta prueba es tan simple que el boceto prueba es casi superfluo, la única información que se dispone que no es evidente a partir de la prueba de alto nivel en sí es el lema que se utiliza para probar los pasos 2 y 3.

Luego viene el Suponga y demostrar cláusulas. Ellos afirman que para demostrar el teorema, basta con asumir las dos hipótesis r ∈ Q y r2 = 2, y para demostrar la falsedad.

Finalmente viene la prueba. Esta es una secuencia de instrucciones que termina con "QED", que denota la afirmación de que sean sometidos a prueba, en este caso, falso.

Piense en esto como prueba de la mitad izquierda (las declaraciones) de una prueba de geometría de secundaria estilo, la mitad derecha (las razones) es omitted.1

2.2 Niveles más bajos de la Prueba

Examinemos ahora la prueba de la etapa 1, que aparece en la Figura 2. Está bastante claro lo que debe ser probada, por lo que no Suponga / Demostrar que se necesita. La prueba consta de cinco pasos, contados 1.1 a 1.5. También hay una declaración Let, que define la requerida m y n. (Yo prefiero Δ = el símbolo más común para ≡ "es igual por definición", ya que ≡ puede también significar equivalencia lógica.)

1. Elija m, n en Z de tal manera que

1. mcd (m, n) = 1

2. r = (m / n)

1,1. Elige p, q en Z tal que q = 0 y _ r = p / q.

Deje que: m = Δ

p / mcd (p, q)

n = Δ

q / mcd (p, q)

1,2. m, n ∈ Z

1,3. r = m / n

1,4. mcd (m, n) = 1

1,5. Lo que había que demostrar

Figura 2: La prueba de la Etapa 1.

Cada uno de estos cinco pasos a su vez tiene su prueba. La prueba de 1,1 es sólo

Demostración: Por supuesto: 1.

1En el curso introductorio geometría plana, los estudiantes en los EE.UU. se les enseña a escribir pruebas en un formato de dos columnas, la columna de la izquierda contiene una secuencia de sentencias y la columna de la derecha contiene sus justificaciones.

Hipótesis: 1 es el primer supuesto (r ∈ Q) en la prueba del teorema.

(El esquema de numeración de los supuestos que se explican a continuación.) Una prueba jerárquica debe detenerse en alguna parte. La cuestión general de dónde parar se trata en la sección 4.2. En esta prueba, se supone que el lector entiende que la definición de Q implica que r puede expresarse como el cociente requerido de números enteros. La prueba de 1,2 es el igualmente simple.

Prueba: 1,1 y definición de m y n.

Paso 1.3 se demuestra por una cadena de igualdades, cada uno con una breve justificación.

Prueba: m / n = [Definición de m y n]

= P / q [Simple álgebra]

= R [By 1.1].

Este tipo de prueba, que consiste en una cadena de igualdades, es simple y directa, ya que funciona tan bien para probar cualquier relación transitiva, como <, equivalencia lógica, y la implicación. Se debe utilizar siempre que sea posible.

Paso 1,4 tiene la prueba de múltiples etapas se muestra en la Figura 3, que consta de los pasos 1.4.1 a 1.4.3. El "1.4:1" en la prueba del paso 1.4.1 denota suposición 1 (s divide m) en la prueba del paso 1.4. El teorema en sí se considera que es un paso que tiene la cadena nula como su número, lo que explica por qué ": 1" denota suposición 1 del teorema.

...