An Intuitionistic Glance at Primes

Resumen Técnico: Una Mirada Intuicionista a los Primos

Planteamiento del Probleza
El artículo aborda la clasificación teoría-probatoria de los enteros positivos en unidades, primos y compuestos dentro del marco de la lógica intuicionista (específicamente, la Aritmética de Heyting, HA). Mientras que la aritmética clásica trata estas categorías como extensiones mutuamente excluyentes y exhaustivas, el artículo investiga las distintas formas de evidencia requeridas para establecer estas propiedades de manera constructiva. El problema central es formalizar cómo la "composicionalidad" (una afirmación existencial) y la "primidad" (una afirmación de refutación universal) funcionan como predicados decidibles cuando el espacio de búsqueda es acotado, y distinguir entre las reglas sintácticas de una teoría formal, el acuerdo interno de un modelo y la interpretación semántica relativa a los números naturales estándar $\mathbb{N}$.

Metodología
El autor emplea un enfoque constructivo y teoría-probatorio basado en la lógica intuicionista. La metodología procede a través de varias capas:

1. Clasificación Ternaria mediante Formas de Evidencia: El artículo define tres predicados —Unidad ($U$), Compuesto ($C$) y Primo ($P$)— basados en tipos de evidencia específicos:

   • $U(n)$: Evidencia de la igualdad $n=1$.
   • $C(n)$: Evidencia de una factorización interior $n=ab$ con $a,b > 1$ (un testigo existencial).
   • $P(n)$: Evidencia de $n > 1$ combinada con una refutación acotada de toda posible factorización interior (un negativo universal).
     Debido a que el dominio de los posibles factores para cualquier $n$ es finito y decidible, tanto $C(n)$ como $P(n)$ se muestran como predicados decidibles.

2. Presentaciones de Bloques por Etapas: Para operacionalizar la búsqueda acotada, el artículo introduce "configuraciones de bloques por etapas". Estas son listas finitas y ordenadas de pares de factores candidatos. El artículo analiza las relaciones de "defecto" (omisiones, duplicaciones, violaciones de orden) que surgen al extender estas etapas. Distingue entre la inhabitación local (una decisión válida en una etapa específica) y la totalización uniforme (un selector global para todas las etapas).

3. Escape Euclídeo y Cribas: El artículo utiliza una variante constructiva del argumento de Euclides ("Escape Euclídeo") para demostrar que ningún conjunto finito de "atrapadores" (generadores de números compuestos) puede capturar todos los compuestos. Esto conduce a una construcción de criba recursiva donde el superviviente menor de un conjunto finito de atrapadores es promovido a un nuevo generador, efectivamente enumerando los primos.

4. Análisis Algebraico y Semántico: El artículo examina las consecuencias algebraicas de esta clasificación, específicamente el contraste entre la cancelación modular (para primos) y la aniquilación por divisores de cero (para compuestos). Luego pasa a un análisis semántico, distinguiendo entre:

   • Conformidad de Regla: Verificación sintáctica de pruebas.
   • Acuerdo Multiplicativo Interno: La satisfacción de las definiciones dentro de un modelo fijo.
   • Acuerdo Definicional Estándar: La alineación de una teoría con la estructura estándar $\mathbb{N}$, lo cual requiere representación metateórica.

Contribuciones Clave y Resultados

• Decidibilidad de la Primidad: El artículo establece que la primidad es una propiedad decidible en HA porque el cuantificador universal en su definición está acotado por el input $n$. La distincción entre primo y compuesto es una cuestión de "polaridad de la prueba" (testigo existencial vs. refutación universal) en lugar de complejidad de la jerarquía aritmética (ambos son $\Delta_0$).
• El Límite de la Unidad: Se proporciona un tratamiento riguroso de la unidad ($1$), mostrando que la oposición binaria $\neg P(n) \to C(n)$ falla en $n=1$. La clasificación ternaria $U(n) \lor P(n) \lor C(n)$ es probada constructivamente.
• Atrapadores Finitos y Transición de Criba: Se demuestra que cualquier conjunto finito de generadores compuestos omite algunos compuestos (específicamente, el cuadrado del menor superviviente). Este mecanismo impulsa una criba recursiva que genera la secuencia de los primos ordinarios.
• Caracterización Algebraica: El artículo vincula la definición número-teórica de los primos con la propiedad algebraica de cancelación en el anillo $\mathbb{Z}/n\mathbb{Z}$. Un número $n > 1$ es primo si y solo si la multiplicación por cualquier residuo no nulo es inyectiva.
• Jerarquía Semántica: El artículo delinea una jerarquía de certificación:
  1. Evidencia Local: Testigos o refutaciones finitas para un $n$ específico.
  2. Acuerdo del Modelo: La extensión de los predicados en un modelo fijo.
  3. Representación Metateórica: La aserción de que una teoría concuerda con el $\mathbb{N}$ estándar.
     El artículo demuestra que mientras la teoría local es una extensión conservadora de HA, establecer el acuerdo con el modelo estándar requiere datos metateóricos externos.
• Límites de la Uniformidad: El artículo aplica el Teorema de Rice y el Segundo Teorema de Incompletitud de Gödel para mostrar que, aunque las pruebas de primidad individuales son decidibles, la certificación bilateral uniforme (producir pruebas tanto para la primidad como para la composicionalidad para todos los $n$) o los límites de completitud uniforme para los problemas de parada poseen una fuerza computacional equivalente al oráculo de la parada ($0'$).

Significancia y Reivindicaciones
El artículo pretende proporcionar un "relato teoría-probatorio" de la clasificación de los enteros, enfatizando que la distinción entre primos y compuestos es estructural y de evidencia, más que meramente extensional.

• Rigor Intuicionista: Argumenta que el "límite de la unidad" y la naturaleza de la búsqueda acotada son cruciales para comprender el contenido constructivo de la primidad. El artículo aclara que la "falta de factorización interior" para los primos no es un infinito negativo, sino una refutación finita y exhaustiva.
• Separación de Niveles: Una contribución primaria es la separación explícita de la conformidad de la regla sintáctica, la satisfacción del modelo interno y la representación de la estructura estándar. El artículo afirma que el "acuerdo con los primos" es una noción relativa dependiente de la metateoría e interpretación elegida.
• Primos como "Espejismo": En la conclusión, el artículo ofrece una caracterización metafórica: relativo a la multiplicación interior, los compuestos forman la imagen generada positivamente, mientras que los primos son los "huecos" en esa imagen. El artículo sostiene que las conjeturas globales sobre los primos (como la Conjetura de los Primos Gemelos o la Conjetura de Goldbach) piden una organización entre estos "huecos" sin suministrar un generador positivo para su distribución, resaltando una asimetría fundamental en su presentación constructiva.

El artículo no propone nuevos algoritmos para la factorización o la prueba de primidad, ni pretende resolver conjeturas abiertas. En su lugar, ofrece un análisis fundacional de cómo se construyen, verifican e interpretan estos conceptos dentro de la aritmética intuicionista, distinguiendo lo que es demostrable internamente de lo que depende de la interpretación estándar de los números naturales.