¿Cómo dar pruebas formales en lógica?

Question

Estoy tomando un curso de lógica matemática y estoy luchando para dar formal de las pruebas de los teoremas o reclamaciones. Haciendo actualmente de primer orden de la lógica. Aquí, un ejemplo:

Reclamo: $\models (\exists x)\big(A(x)\Rightarrow (\forall y)(A(y))\big)$

donde $A$ es un predicado unario. Se me pide para probar esto. Esta es la razón:

Por la regla de la lógica proposicional $P\Rightarrow Q$ es equivallent a $\neg P\vee Q$. Por eso, deseamos mostrar que $$\models(\exists x)\big(\neg A(x)\vee (\forall y)(A(y))\big)$$ Así, supongamos que tenemos una interpretación arbitraria de la lengua $\mathcal{L}=\{A\}$, que es un conjunto no vacío $M$ junto con predicado unario $A$.. Por Tarski de la definición de la verdad, hay algo de $m\in M$ que $\neg A(m)$ o para todos los $n\in M$ $A(n)$ sostiene. Pero esto es claramente cierto (lógicamente válido). Porque siempre hay algo de $m\in M$ para que $\neg A(m)$, entonces la fórmula es satisfecho. Si no, entonces para todos los $n\in M$ para que $A(n)$, lo que la hace también muy satisfechos.

Ahora, me pregunto si esto puede ser tomado como una prueba formal de la afirmación de que la fórmula es lógicamente válido en cualquier interpretación de la lengua de $\mathcal{L}=\{A\}$. Parece muy trivial, pero me temo que soy demasiado uso de la teoría de conjuntos.

Otro razonamiento podría ser: De hecho, cuando se $A$ es un predicado unario, que significa $A$ es un subconjunto de a$M$. Ahora distinguir dos casos: 1. $A=M$, a continuación, $(\forall y)((y\in M) \Leftrightarrow (y\in A))$ en otras palabras $(\forall y)(A(y))$. Si $A\subsetneq M$ , entonces es claro que hay algunos $m\in M$ que no está en $A$, en este caso la parte $(\exists x)(\neg A(x))$ es cierto. Ahora, este utiliza la definición de la igualdad entre conjuntos y ¿qué es un subconjunto.

Otra idea: el Uso de una contradicción. Asumir que esto no era lógicamente válido, por lo que existe cierta interpretación $\mathcal{M}$ y el valor de asignación de $e$ para que $\mathcal{M}\models \neg(\exists x)\big(A(x)\Rightarrow (\forall y)(A(y))\big)$, que es $\mathcal{M}\models(\forall x)(A(x)\wedge (\exists y)(\neg A(y))$, por lo tanto para todos los $m$ $\mathcal{M}\models A(m)\wedge (\exists y)(\neg A(y))$, por definición, también hay un poco de $n\in M$ para que $\mathcal{M}\models A(m)\wedge \neg A(n)$, esto le da a $\mathcal{M}\models A(n)$ (la $n$ debe ser uno de todos los $m$'s), sino también a $\mathcal{M}\models \neg A(n)$. Cual es la contradicción por la ley de medio excluido, por lo que la instrucción antes era lógicamente válido.

O simplemente por mirar: es claro que para todas las $x$ $A(x)$ sostiene, o hay algo de $x$ para que $A(x)$ no tienen...

Todo esto parece un handwaving...

Así que, ¿qué herramientas/métodos/tipo de razonamiento debo usar en la mayoría de demostrar tales afirmaciones y los teoremas de la lógica del modelo o la teoría? Agradecería opiniones y/o ejemplos más (fuentes).

Answer 1

La prueba es correcta. Utiliza las definiciones matemáticas de todos los términos involucrados, como "válido", "interpretación", y "true en una interpretación" y vino para arriba con un riguroso argumento de que la declaración fue, de hecho, válido de acuerdo con esas definiciones.

A menudo las personas están bajo la impresión equivocada de que sólo porque somos el estudio de la lógica, tenemos que dejar de ser matemáticos y a su vez en los compiladores de C++. (Matemática) la lógica es una rama de las matemáticas, como cualquier otra, donde se argumenta de manera informal$^*$ pero con rigor acerca de las construcciones matemáticas. Es sólo que en el caso de la lógica, nuestros argumentos son a menudo acerca de las pruebas, que son propios de las construcciones matemáticas. Sin embargo, en un cierto sentido, el punto entero de la semántica y el modelo de la teoría consiste en abstenerse de pruebas y en lugar de pensar acerca de las sentencias en su 'significado llano" dentro de las estructuras matemáticas que podría hablar.

La semántica requieren más fuerte filosófica preceptos que sintácticos pruebas (como la que usted alude, no es cierta la teoría de conjuntos). También se podría construir una prueba formal de su estado de cuenta en alguna prueba de cálculo de primer orden de la lógica, y esta construcción sólo supondría finitary ideas. Si hacemos esto podemos decir que $\vdash (\exists x)\big(\neg A(x)\vee (\forall y)(A(y))\big)$ (con un $\vdash$ significado "comprobable (en algunos deductivo sistema)" en lugar de una $\models$ significado de "válido").

Cabe destacar que el estándar de prueba de los sistemas de primer orden de la lógica se completa y el sonido, es decir, se puede demostrar que una sentencia si y sólo si es semánticamente válido, es decir, $\vdash \phi\iff \models\phi$. Mientras que las pruebas están a menos de una carga filosófica, como una cuestión práctica es generalmente más difícil de construir pruebas que hacer argumentos semánticos. Pero las pruebas son muy importantes en la filosofía, especialmente si usted está preocupado acerca de los asuntos fundamentales. También son interesantes objetos de estudio en su propio derecho. (Y la noción de que la "verdadera en todos los modelos" y "eficacia comprobada en un sistema formal" son equivalentes en particular a los de primer orden de la lógica, de todos modos.)

$^*$Aquí podríamos tener un choque de terminología entre la forma en que usted está utilizando el término "formal" vs la forma en que los lógicos suelen utilizar el término. A un lógico, una prueba formal de la lógica de la frase es un objeto matemático construido según algunos formal de las reglas matemáticas para la prueba de la construcción. Un riguroso lenguaje natural argumento de que un determinado enunciado matemático es cierto es un informal de la prueba, independientemente de cómo a prueba de agua y bien-explicó el razonamiento es. (Aunque todavía puede oír los lógicos, de vez en cuando uso 'formal' para significar 'cuidado / detalladas / riguroso'). Pruebas son entendidas como modelos de bien razonada, y por supuesto el más cuidadoso / detalladas / riguroso - ly informal, la prueba de que hablamos, más fácil es imaginar que se está traduciendo en una prueba formal en algunos adecuado del sistema.