Comience con cuatro relaciones binarias
y dos operaciones binarias
Ahora considera las frases sobre esta firma que sólo implican lo siguiente:
Intuitivamente hablando, estas sentencias son muy especiales, porque si son verdaderas, entonces podemos demostrarlas simplemente dando ejemplo(s) y/o comprobando finitamente muchos casos.
¿Tienen estas frases algún significado matemático?
Sí, pero hay una clase más amplia de fórmulas con la misma propiedad, que es la clase que se suele considerar. La clase $\Sigma^0_1$ consiste en fórmulas que utilizan las mismas relaciones y operaciones que en la pregunta, cualquiera de las operaciones lógicas habituales (incluidas NOT e IMPLIES), y que se pueden poner en la forma $$ (\exists x_1)\cdots(\exists x_n)\,\phi(x_1\ldots,x_n) $$ donde $\phi$ no tiene cuantificadores no limitados ( $\phi$ puede tener cuantificadores universales acotados y puede tener cuantificadores existenciales acotados).
Al igual que la clase de fórmulas de la pregunta, estas fórmulas pueden demostrarse dando un número finito de ejemplos (valores de $x_1,\ldots,x_n$ ) y luego verificar que una fórmula con sólo cuantificadores acotados es verdadera, lo que puede hacerse algorítmicamente.
La clase $\Sigma^0_1$ es bien conocido y significativo en lógica matemática por varias razones:
Un conjunto de números naturales es enumerable recursivamente si y sólo si es definible por un $\Sigma^0_1$ fórmula. Esta relación conduce a aplicaciones de $\Sigma^0_1$ fórmulas en teoría de la computabilidad.
La proposición de que una teoría formal efectiva fija es inconsistente puede escribirse como una $\Sigma^0_1$ declaración. Esto conduce a aplicaciones de $\Sigma^0_1$ fórmulas de la teoría de la demostración de la aritmética, como el teorema de incompletitud de Gödel.
La negación de un $\Sigma^0_1$ se denomina $\Pi^0_1$ fórmula; $\Pi^0_1$ Las fórmulas se pueden refutar dando un número finito de ejemplos y comprobando esos ejemplos. Las clases $\Sigma^0_1$ y $\Pi^0_1$ se sitúan cerca de la parte inferior de una jerarquía infinita de fórmulas conocida como jerarquía aritmética, y muchas propiedades de las clases superiores de la jerarquía se deducen de las propiedades correspondientes de las clases $\Sigma^0_1$ y $\Pi^0_1$ .
Se denominan $\Sigma_1$ (de hecho, la definición de $\Sigma_1$ es un poco diferente, pero funciona igual). Tienen la agradable propiedad de que siempre que $\phi$ es un verdadero $\Sigma_1$ también es demostrable en aritmética de Peano. Además, básicamente por la razón que has dicho, si $(\exists n)\phi(n)$ es un verdadero $\Sigma_1$ sentencia, entonces es posible calcular un testigo $n$ tal que $\phi(n)$ es cierto.
Que yo sepa, no hay muchos ejemplos de teoremas matemáticos "naturales" que sean $\Sigma_1$ . Sin embargo, $\Pi_1$ que son las negaciones de $\Sigma_1$ a veces aparecen frases. Por ejemplo, la conjetura de Goldbach es una $\Pi_1$ sentencia.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
