Hay una manera de saber cuántas maneras diferentes que usted puede demostrar un teorema?

Question

Considere la posibilidad de la pregunta.

Dada la naturaleza de una sentencia de $S$, hay alguna manera de saber cuántas maneras diferentes que usted puede probar esta frase?

Las pruebas no son distintas si tenemos una situación, como por ejemplo: $P \implies Q$ y queremos demostrar que $A\implies B$ y se dice que tenemos $A\implies P$ $Q\implies B$ $A\implies P\implies Q\implies B$ es la misma prueba como $A \implies P \implies B$. Así que los métodos de la prueba de tales declaraciones deben ser tan conciso como sea posible. Sin embargo, lógicamente, significa que, dado un conjunto de axiomas, que directamente implica el resultado. Este es un ejemplo de condiciones.

Así que mi verdadera pregunta(s) es/son:

¿Qué condiciones son necesarias para distinguir entre la prueba (pruebas de ser un conjunto de oraciones lógicas determinar el resultado deseado como verdadera) de tal manera que la cantidad de pruebas se puede contar?

Se puede determinar fácilmente cuales son las condiciones que implican la cardinalidad del conjunto de las pruebas?

por ejemplo. si me dicen que las condiciones $X$ para las pruebas de que puede ser capaz de obtener countibly cantidad infinita de pruebas. (Lo que no sería útil). O como la condición anterior, lo que implica pruebas son sólo aplicaciones de los axiomas. (También no muy útil).

Answer 1

Una prueba consiste de una secuencia de instrucciones. Cuando son dos secuencias distintas? Así, si dos secuencias tienen una longitud diferente, entonces se califica como algo distinto. Ahora considere la posibilidad de cualquier prueba de que usted tiene que decir que es Un como un paso intermedio antes de probar la conclusión de C. Así, puesto que a es verdadera, se sigue que B$\rightarrow$A) tiene como cierto también (donde $\rightarrow$ indica que el condicional de dos valores de la lógica o de cualquier sistema lógico donde $\vdash$($\rightarrow$B$\rightarrow$A)) o |=(A$\rightarrow$B$\rightarrow$A))). Pero "B" indica una variable arbitraria. Y así, usted puede insertar una larga

Un

(B$\rightarrow$A)

Un

a cualquier prueba de que usted ya tiene, incluyendo la prueba de que usted va a obtener al hacer esto. En consecuencia, la cardinalidad de todas las pruebas que viene al menos countably infinito.

Dicho esto, no hay probablemente existe un número finito de pruebas de una longitud dada, donde la longitud de la prueba es el número de pasos y un "paso" en una prueba consta de un el resultado de una aplicación de una regla.