Siguiente: Interpretaciones Un nivel arriba: Aritmética de Peano Anterior: Aritmética de Peano

Demostrabilidad

En toda lógica hay axiomas los cuales son fórmulas de tipo lógico o de tipo propio de la teoría:

Axiomas lógicos.

Cualesquiera que sean las fórmulas $\phi_1,\phi_2,\phi_3$ y cualquiera que sea el término t, los siguientes son axiomas lógicos:

1.

$\phi_1\rightarrow (\phi_2\rightarrow \phi_1)$.

2.

$\left(\phi_1\rightarrow (\phi_2\rightarrow \phi_3)\right)\rightarrow \left(\lef... ...ightarrow \phi_2\right)\rightarrow \left(\phi_1\rightarrow \phi_3\right)\right)$.

3.

$\left(\phi_1\rightarrow \neg \phi_2\right)\rightarrow \left(\left(\phi_1\rightarrow \phi_2\right)\rightarrow \neg\phi_1\right)$.

4.

$\phi_1(t)\rightarrow\exists x\phi_1(x)$.

Sea $\mbox{\it CP}$ (por cálculo de predicados) el conjunto de axiomas lógicos.

Axiomas propios.

Son característicos de cada lógica. Por ejemplo, en la aritmética de Peano, se introduce la relación de desigualdad como una fórmula:

$$(x\leq y)\equiv \exists z(x+z=y).$$

Con esto, sea P^- el conjunto de los siguientes axiomas propios:

$$\begin{array}{l\vert l} \begin{array}[t]{c} s(x)\not= 0 \\ ... ...x\cdot z \\ x+y=x+z \Rightarrow y=z \end{array} \end{array}$$

Sea $\mbox{\it AP}=P^-\cup \mbox{\it EI}$, donde EI es el esquema de inducción:

$$\mbox{\rm Para cualquier f\'ormula $\Phi$: }\Phi(0,\mbox{\bf ... ...),\mbox{\bf x})) \Rightarrow \forall x(\Phi(x,\mbox{\bf x})).$$

En toda lógica se considera también reglas de inferencia. En el cálculo de predicados y en la aritmética de Peano, las reglas son de los tipos siguientes:

Modus Ponens. Cualesquiera que sean las fórmulas $\phi_1,\phi_2$: $$\frac{\textstyle \begin{array}{l} \phi_1\rightarrow\phi_2 \\ \phi_1 \end{array}}{\textstyle \ \,\phi_2}$$

Generalización. Cualquiera que sea la fórmula $\phi$ y cualquiera que sea la variable x pero siempre que x aparezca ``libre'' en $\phi$: $$\frac{\textstyle \phi(x)}{\textstyle \forall x\phi(x)}$$

Sea H un conjunto de fórmulas bien formadas y sea $\phi$ una fórmula. Una demostración de $\phi$ a partir de H es una sucesión finita $D=[\delta_0,\ldots,\delta_m]$ de fórmulas bien formadas tal que

1.

La última fórmula en D es la tesis $\phi$, es decir, $\delta_m=\phi$.

2.

Para cada fórmula $\delta$ en D se cumple una de las siguientes aseveraciones:

(a)

$\delta$ es un axioma, sea lógico o propio,

(b)

$\delta$ es una hipótesis, es decir, $\delta\in H$,

(c)

$\delta$ se sigue mediante reglas de inferencia de fórmulas que la preceden en D, es decir,

i.

$\exists \psi\in[\delta_0,\ldots,\delta[:(\psi\rightarrow\phi) \in[\delta_0,\ldots,\delta[,$ o bien

ii.

$\exists \psi\in[\delta_0,\ldots,\delta[\,\exists x\mbox{\it variable libre en }\psi:\phi=\forall x\psi(x)$.

La notación $H\vdash \phi$ denotará que existe una demostración de $\phi$ a partir de H, y en tal caso se dice que $\phi$ es demostrable a partir de H. Toda fórmula $\phi$ demostrable sin ningunas hipótesis suplementarias, $\emptyset\vdash \phi$, se dice ser un teorema, y se escribe en tal caso, $\vdash \phi$. De hecho seremos más enfáticos y escribiremos

• $\mbox{\it CP}\vdash \phi$ para indicar que $\phi$ se demuestra sólo de los axiomas lógicos, y en este caso se dice que $\phi$ es un teorema lógico,
• $P^-\vdash \phi$ para indicar que $\phi$ se demuestra de los axiomas lógicos y de los propios de la aritmética de Peano exceptuando el esquema de inducción, y
• $\mbox{\it AP}\vdash \phi$ para indicar que $\phi$ se demuestra en toda la aritmética de Peano.

Se tiene, por ejemplo, que todas las tautologías son teoremas lógicos así como también se puede demostrar que toda fórmula bien formada es equivalente a una fórmula escrita en forma prenex, es decir escrita como una fórmula donde todos los cuantificadores aparecen al principio y el alcance de los cuantificadores está en forma normal conjuntiva, o sea, es una conjunción de disyunciones de literales, las cuales son fórmulas atómicas o negaciones de fórmulas atómicas. Dado un conjunto H de fórmulas bien formadas su teoría consta de todas las fórmulas demostrables a partir de H. La denotamos por $\mbox{\it Teor\'\i a}(H)=\{\phi\vert H\vdash \phi\}.$ H se dice ser consistente, o más bien coherente, si no existe fórmula alguna $\phi$ tal que ambas $\phi$ y $\neg\phi$ están en $\mbox{\it Teor\'\i a}(H)$.
Siguiente: Interpretaciones Un nivel arriba: Aritmética de Peano Anterior: Aritmética de Peano