¿Cuáles son algunos de los métodos de prueba más interesantes?

Las pruebas teóricas de modelos generalmente me parecen magia negra.

La teoría de modelos trata con modelos de axiomas, capturados por oraciones en lógica de primer orden. Una oración en lógica de primer orden es una afirmación como [math] \ forall x, \ exist y, P (x) \ text {or} f (x, y) = x [/ math], donde [math] P [ / math] es un predicado de algún tipo (es decir, dada una entrada, devuelve VERDADERO o FALSO), y [math] f [/ math] es algún tipo de función. Es decir, estas son oraciones donde permitimos el uso de los cuantificadores [math] \ forall, \ exist [/ math], algún conjunto de símbolos predefinidos (en el ejemplo anterior, estos fueron [math] x, y [/ math] ), y un conjunto de funciones predefinidas (en lo anterior, este era el papel de [math] f [/ math]). También podríamos necesitar el uso de () para indicar orden, = para indicar igualdad y conectivos lógicos booleanos básicos como AND, OR, etc. Hay una sintaxis precisa que debe seguirse para que la oración tenga sentido (por ejemplo, [ math] \ forall x, \ exist [/ math] no es bueno).

Si desea una definición más exhaustiva y rigurosa, puede mirar aquí Lógica de primer orden, pero en su mayor parte si mira algo y piensa “¡Esta es una oración de primer orden!”, Probablemente tenga razón. Lo más importante que debe recordar es que, si bien nuestros cuantificadores [math] \ forall, \ exist [/ math] pueden tener una variable [math] x [/ math] que se encuentra dentro de un conjunto fijo, no nos permitimos tener cuantificadores sobre, por ejemplo, todos los subconjuntos de ese conjunto. Por ejemplo, supongamos que estamos interesados ​​en investigar verdades en la lógica de primer orden sobre los números naturales. Los números naturales tienen la propiedad de que todos los subconjuntos no vacíos de los números naturales tienen un elemento más pequeño. La forma más obvia de expresar esto matemáticamente es

[matemáticas] \ forall U \ subconjunto \ mathbb {N}, \ left (\ exist x \ in U \ right) \ Rightarrow \ left (\ exist y \ in U, \ forall z \ in U, y \ leq z \ derecha) [/ matemáticas].

Sin embargo, esta no es una oración de primer orden; si tuviéramos que colocar el cuantificador en frente sobre los subconjuntos de [math] \ mathbb {N} [/ math], esta sería una oración de primer orden perfectamente buena (diciendo que [math] U [/ math] tiene un elemento más pequeño si no está vacío), pero como está escrito no es de primer orden.

Sin embargo, uno podría preguntarse si tal vez es posible preparar una oración de primer orden muy inteligente que capture la propiedad deseada (solo porque esta oración en particular no sea de primer orden no significa que alguna oración haya capturado esta verdad lógica particular no sería de primer orden). La respuesta es ‘no’, pero volveré a eso.

Dado un conjunto de símbolos y funciones predefinidos, así como un conjunto de oraciones de primer orden en esos símbolos y funciones, un modelo es un conjunto particular [matemática] M [/ matemática] tal que cuando identificamos los símbolos y funciones con elementos de [matemática] M [/ matemática] y funciones en [matemática] M [/ matemática], las oraciones de primer orden son verdaderas.

Esto se entiende mejor a modo de ejemplo: tendremos un símbolo marcado especial [math] id [/ math] y una operación binaria [math] \ cdot [/ math], con las oraciones de primer orden

1. [matemáticas] \ forall g_1, g_2, g_3, (g_1 \ cdot g_2) \ cdot g_3 = g_1 \ cdot (g_2 \ cdot g_3) [/ math],
2. [matemáticas] \ forall g, id \ cdot g = g \ cdot id = g [/ math],
3. [math] \ forall g, \ exist h, g \ cdot h = h \ cdot g = id [/ math].

Es posible que esté familiarizado con estos como axiomas grupales: cualquier modelo de estas oraciones es un grupo. La operación es la multiplicación grupal, que el primer axioma nos dice que es asociativa. La identidad es [math] id [/ math], cuyas propiedades multiplicativas se explican en el segundo y tercer axiomas (con el tercer axioma introduciendo la noción de inverso multiplicativo).

Entonces, por ejemplo, si [math] id = 0 [/ math], y [math] \ cdot = + [/ math], entonces los enteros [math] \ mathbb {Z} [/ math] además dan un modelo de esta teoría de primer orden.

Uno de los resultados fundamentales de la teoría de modelos es el teorema de compacidad, que dice algo realmente notable: si [matemática] L [/ matemática] es cualquier conjunto de axiomas de primer orden, [matemática] L [/ matemática] tiene un modelo si y ¡solo si algún subconjunto finito [matemático] L_0 \ subconjunto L [/ matemático] tiene un modelo!

Esto es tremendamente poderoso: lo usé en mi respuesta a ¿Cómo se construye matemáticamente el sistema numérico hiperrealista infinitesimal? para mostrar que debe existir un conjunto de hiperreal que satisfaga el principio de transferencia. ¡Esto a pesar del hecho de que nunca construí explícitamente un conjunto de hiperrealistas!

Otra cosa para la que podemos usar el teorema de compacidad es mostrar que ciertas verdades matemáticas son fundamentalmente inexpresables en la lógica de primer orden. Volvamos al ejemplo de los números naturales y al hecho de que cualquier subconjunto no vacío de ellos debe tener un elemento más pequeño.

Supongamos por un segundo que hay una colección de oraciones de primer orden [math] \ Gamma [/ math] tal que [math] M [/ math] es un modelo de [math] \ Gamma [/ math] si y solo si cada subconjunto no vacío de [math] M [/ math] tiene un elemento más pequeño. Ahora, construya una nueva colección [math] \ Gamma ‘[/ math] agregando símbolos [math] c_1, c_2, c_3, \ ldots [/ math] y oraciones

[matemáticas] c_2

[matemáticas] c_3

[matemáticas] c_4

[matemáticas] \ ddots [/ matemáticas]

Cualquier subconjunto finito de [math] \ Gamma ‘[/ math] tiene un modelo (solo tome [math] M = \ mathbb {N} [/ math] y si [math] c_N = 1, c_ {N – 1} = 2, \ ldots [/ math], donde [math] N [/ math] es el subíndice más grande que aparece en la sublista finita de axiomas).

Por el teorema de compacidad, sabemos que todas las oraciones en [math] \ Gamma ‘[/ math] tienen un modelo. Pero esto es un problema, ya que el subconjunto [matemáticas] \ {c_1, c_2, c_3, \ ldots \} \ subconjunto M [/ matemáticas] no tiene el elemento más pequeño: una contradicción. Concluimos que debemos haber estado inicialmente equivocados y que no hay una colección de oraciones en la lógica de primer orden que pueda capturar esta propiedad de los números naturales.

El teorema de compacidad también se puede utilizar para dar resultados positivos. Recuerdo que una vez vi una charla en la que el hablante demostró un resultado sobre gráficos finitos al probarlo primero para gráficos infinitos y luego usar el teorema de compacidad. (Podría estar equivocado, pero creo que fue de hecho el teorema de Ramsey: el lector interesado podría mirar aquí). También existe el resultado clásico de que una oración en lógica de primer orden es verdadera para todos los campos cerrados algebraicamente con la característica 0 si y solo si es cierto para todos los campos algebraicamente cerrados con características suficientemente grandes.

Daré un ejemplo más realista. Demostraremos que cada conjunto puede recibir un orden lineal (es decir, podemos definir un orden [matemático] <[/ matemático] tal que para todos los elementos del conjunto, [matemático] x y [/ matemática]).

Supongamos que [math] S [/ math] es el conjunto al que queremos dar un orden. Considere la teoría de primer orden definida por los símbolos [math] c_s [/ math] para cada [math] s \ en S [/ math], un símbolo [math] <[/ math] y las oraciones

1. [matemática] \ para m, \ para n, (m = n) \ text {o} (m
2. [math] c_s \ neq c_ {s ‘} [/ math] (agregue uno de esos axiomas para cada par de elementos [math] s, s’ \ en S [/ math]).

Cualquier sub-colección finita de estos axiomas será satisfecha por [math] \ mathbb {Z} [/ math] con el orden usual (solo mapee la mayoría de los símbolos a [math] 0 [/ math]). Por lo tanto, estos axiomas son satisfechos por algún conjunto [matemático] M [/ matemático] con algún orden lineal [matemático] <^ M [/ matemático] en él, y el mapa [matemático] s \ mapsto c_s ^ M [/ matemático] es inyectiva (ese era el objetivo de todos esos axiomas que obligaban a [matemáticas] c_s \ neq c_ {s ‘} [/ matemáticas]).

Sin embargo, dado que este mapa es inyectivo, podemos tomar el orden de su imagen (que es un subconjunto de [matemáticas] M [/ matemáticas]) y devolverlo a un orden lineal de [matemáticas] S [/ matemáticas].

John Horton Conway es aficionado a lo que él llama “pruebas de una línea”. Estas pruebas son declaraciones de la forma [math] \ alpha = \ omega [/ math], donde [math] \ alpha, \ omega [/ math] son ​​expresiones potencialmente complejas, y la prueba en sí es de la forma [math] \ alpha = \ beta = \ gamma = \ cdots = \ omega [/ math], donde cada expresión sucesiva [math] \ beta, gamma, \ ldots [/ math] sigue de manera obvia y trivial a la anterior.

Pierre de Fermat ideó (o al menos hizo más popular) una técnica de prueba llamada “descenso infinito”. Básicamente, muestra que si alguna proposición se cumple para algún número natural [matemática] m [/ matemática], entonces también se debe cumplir para algún número natural [matemática] n [/ matemática] con [matemática] n

Soy un gran admirador de:

Demuestre que dada la hipótesis de Riemann es verdadera, luego demuestre que dada la hipótesis es falsa. Deduce es verdad.

Sin embargo, esto probablemente no sea lo que quisiste decir.

También encuentro que las pruebas que implican moverse entre diferentes campos son muy interesantes. Por ejemplo, probar el Teorema fundamental del álgebra usando el grupo fundamental, una herramienta de la topología (algebraica).

¿Todavía no es lo que querías decir?

Hay algo realmente agradable e interesante sobre el método probabilístico Método probabilístico: Wikipedia. A menudo se usa en combinatoria (aquí es donde se originó), pero ha estado buscando aplicaciones en otros lugares. A menudo es fabulosamente no constructivo y es realmente genial que pueda usar métodos probabilísticos para obtener un resultado que es una certeza.

El artículo de Wikipedia incluye 2 pruebas agradables y accesibles que utilizan el método, por lo que no incluiré ningún ejemplo aquí.