Entender los cuantificadores a través de las metáforas del juego

Question

En el apéndice sobre lógica matemática de su libro "Análisis 1", Terence Tao explica los cuantificadores mediante metáforas de juegos. Por ejemplo, escribe

En el primer juego, el oponente elige qué es x, y luego tienes que demostrar que P(x); si siempre puedes ganar este juego, entonces has demostrado que P(x) es verdadera para todo x.

¿No está confundiendo aquí "verdad" con "demostrabilidad"? Porque poder ganar siempre este juego significa que para cada x, hay una prueba individual del hecho de que P(x). Pero probar "para todo x, tenemos P(x)" es algo diferente a probar "para cada x, hay una prueba de P(x)". (Para hablar de la demostrabilidad de los enunciados, normalmente se da una definición exacta de lo que son los "términos (de primer orden)", las "fórmulas (de primer orden) bien formadas" y luego se especifica un cálculo formal consistente en reglas de inferencia y axiomas lógicos, para luego definir lo que significa que una fórmula "sea deducible de un conjunto de axiomas". Pero aunque se haya hecho esto, no hay que confundir "fórmulas deducibles" con "fórmulas verdaderas").

Las otras metáforas del juego son:

En el segundo partido, tienes que elegir lo que es x, y luego demuestras P(x); si puedes ganar este juego, habrás demostrado que P(x) es verdadera para algún x.

y

Para continuar con la metáfora del juego, supongamos que juegas una partida en el que tu oponente elige primero un número positivo x, y luego tú y tú eliges un número positivo y. Ganas la partida si y 2 = x. Si siempre puedes ganar el juego independientemente de lo que haga tu oponente, entonces has demostrado que para cada x positivo, existe un y positivo y positivo tal que y 2 = x.

Nos da el ejercicio de pensar en esas metáforas del juego para otras declaraciones, por ejemplo:

Existe un número positivo x tal que para todo positivo positivo y, tenemos y^2 = x.

¿Cuál sería la metáfora de juego correspondiente? Yo diría que es algo así: Elijo un número positivo x. Entonces, mi oponente me da un número positivo y. Gano si y^2 = x. La afirmación es verdadera si existe un número positivo fijo x con el que siempre puedo ganar. ¿Es esto correcto? De alguna manera no entiendo el propósito de estas metáforas de juego. ¿De qué se trata? En este ejemplo, pensar en cuál podría ser la metáfora de juego correspondiente, no me ayuda a entender más el enunciado.

Answer 1

Como ya se ha mencionado, Terence estaba siendo informal. Pero la distinción que intenta hacer es importante. $ \def\nn{\mathbb{N}} \def\pa{\text{PA}} \def\prf{\text{Proof}} \def\box{\square} $

Hablaré desde la perspectiva del metasistema. Tomemos cualquier sistema formal $S$ que tiene validez de prueba decidible. Para cada $n \in \nn$ y la fórmula $φ$ sobre PA, que $\prf_S(n,φ)$ ser un $Σ_0$ -sobre PA, tal que $PA \vdash \prf_S(n,φ)$ si $n$ codifica una prueba de $φ$ en $S$ et $PA \vdash \neg \prf_S(n,φ)$ de lo contrario. Entonces (ya que PA es consistente) para cada número natural $n$ tenemos $\pa \vdash \neg \prf_\pa(n,\bot)$ Sin embargo $\pa \nvdash \forall x\ ( \neg \prf_\pa(x,\bot) )$ .

Esto es, por tanto, un contraejemplo de la afirmación de Terence tal y como se ha expuesto. Para que su afirmación sea más correcta, debemos cambiar la redacción por algo así:

Si puedes probar que dado cualquier $x$ puede demostrar $P(x)$ Entonces ha demostrado que $\forall x\ ( P(x) )$ .

O podemos cambiar su frase a "si puedes mostrar que siempre se puede ganar este juego, ...".

Incluso con este cambio, en la práctica no se puede cumplir la condición en el sentido requerido por las matemáticas modernas. ¿Qué significa que se le dé, por ejemplo, un subconjunto infinito de $\nn$ ? ¿Y cómo podemos demostrar que ese conjunto satisface $P$ ? Una forma de interpretar la condición para que esto funcione es

Puede dar un procedimiento sistemático para construir la prueba de $P(x)$ en $S$ (además de cualquier otra frase que se sostenga en el contexto actual).

Esto suele equivaler a escribir la propia prueba... Esto, por supuesto, puede considerarse sólo una forma de expresar la regla de inferencia de que si $S \vdash P(x)$ entonces $S \vdash \forall x\ ( P(x) )$ donde la semántica del juego explica el significado de la libertad de $x$ en " $S \vdash P(x)$ ".

De todos modos, probablemente no necesites conocer la semántica del juego, ya que parece que ya conoces la lógica, pero mira mis comentarios en este puesto para ver cómo la semántica del juego puede aclarar mejor el papel de la LEM (ley del medio excluido) en la lógica clásica. La interpretación de la BHK encaja perfectamente con la semántica de los juegos, en la que el programa correspondiente a una prueba puede verse como la implementación de una estrategia ganadora para el juego.

Answer 2

Técnicamente tienes razón, y el autor está siendo algo informal con su elección de palabras. Más preciso sería: "Tu oponente puede elegir $x$ y si $P(x)$ sostiene que ganes". Esto, por supuesto, es mucho menos evocador de dos personas jugando a un juego, por lo que creo que eligió utilizar la frase más activa. De hecho, si nos ponemos muy formales, el juego descrito está quizá más cerca de un juego para comprobabilidad que para verdad .

La metáfora del juego que has elegido para la afirmación es correcta.

En este contexto (de un libro de introducción al análisis), asumo que la descripción teórica del juego de la interpretación de los cuantificadores es sobre todo para hacerlos fácilmente comprensibles para la gente que nunca los ha visto antes. Estos juegos son en realidad una forma muy natural de pensar en los cuantificadores. Por ejemplo, apuesto a que has escuchado un $\epsilon$ - $\delta$ prueba explicada por algo así como

Por cada $\epsilon > 0$ que elijas, por pequeño que sea, siempre puedo encontrar un $\delta > 0$ tal que ....