¿Cuál es el propósito de variables libres en primer orden de la lógica?

Question

Entiendo la diferencia entre libre y variables vinculadas, pero ¿qué son las variables libres realmente útil? No se puede usar cuantificadores para expresar todo lo que queremos expresar con tanto obligados y variables libres? Estoy un poco frustrado de que la siempre presente posibilidad de variables libres complica la introducción de cuantificadores en FOL declaraciones, mientras que no se puede encontrar ninguna motivación para las variables libres.

Digamos que tienes una relación $R$, arity $2$. Si quieres expresar que, para todo x y para todo y, $R(x,y)$, supongo que habría que escribir:

$$\forall_x\forall_yR(x,y)$$

Tal vez también se podría formular como este:

$$R(x,y)$$

Pues parece que para que esta sea válida la proposición en FOL, usted tendría que capturar todas las variables libres con el cuantificador universal. Pero esto significa que las fórmulas con variables libres son equivalentes a cerrado fórmulas donde estas variables libres han sido capturados por los cuantificadores universal, si usted quiere averiguar la validez de la fórmula. Entonces, ¿cuál es el propósito de variables libres cuando se trata de probar fórmulas de FOL?

Answer 1

Considerar el informal argumento de " Todo el mundo le encanta la pizza. Cualquier persona que ama la pizza ama los helados. Así que todo el mundo ama los helados.' ¿Por qué es válido?

Aproximadamente: Recoger a alguien, quienquiera que te gusta. Entonces, s/él le encanta la pizza. Y por lo que s/él ama los helados. Pero sh/e fue elegido de forma arbitraria. Así que todo el mundo ama los helados.

Este informal argumento puede ser explicada con andar laboriosidad que conlleva explícita comentario como este:

1. Todo el mundo le encanta la pizza. (Que se da)

2. Cualquier persona que ama la pizza ama los helados. (Que se da demasiado)

3. Tomar algo de arbitrario persona, llamada Alicia. Entonces Alice le encanta la pizza (De 1)

4. Si Alice le encanta la pizza, ella ama el helado (De 2)

5. Alice ama de helado (De 3, 4, por modus ponens)

6. Pero Alice era un arbitrario representante de la persona, de modo que lo que se aplica a ella se aplica a cualquier persona: así que todo el mundo ama los helados.

Ahora, considere el formal análogo de esta prueba (el uso de $F$ 'ama la pizza", etc.)

1. $\forall xFx\quad\quad\quad\quad$ Premisa

2. $\forall x(Fx \to Gx)\quad$ Premisa

3. $Fa\quad\quad\quad\quad\quad$ A partir del 1., Univ. La creación de instancias

4. $(Fa \to Ga)\quad\quad$ A partir de 2., Univ. La creación de instancias

5. $Ga\quad\quad\quad\quad\quad$ A partir de 3, 4 por MP

6. $\forall xGx\quad\quad\quad\quad$ A Partir De 5, Univ. La generalización de

(UG en $a$ es legimitate como $a$ aparece en ninguna suposición sobre la que (5) depende, por lo que puede ser pensado como una indicación de un arbitrario representante miembro del dominio.)

Así que tenga en cuenta, que tenemos aquí un símbolo de jugar el papel de $a$, no un verdadero constante con un fijo de interpretación, no una variable ligada, pero (como jerga tiene) un parámetro que es, en cierto sentido, un elemento arbitrario de la domaain.

Ahora, en algunos sintaxis, variables $x$, $y$ etc. sólo aparecen siempre vinculados, como parte de cuantificados frases. Y los parámetros son tipográficamente muy distinta, $a$$b$, etc. Este es el uso de Gentzen, por ejemplo.

Pero otra tradición (probablemente el más común, pero no por eso se prefiere), estamos tipográficamente económico, y la re-ciclo de las mismas letras como verdadero y variables como parámetros. En otras palabras, nos permiten las mismas letras que aparecen tanto como "dependiente" de las variables y como "libre" de las variables. A continuación, la prueba formal tendrá este aspecto:

1. $\forall xFx\quad\quad\quad\quad$ Premisa

2. $\forall x(Fx \to Gx)\quad$ Premisa

3. $Fx\quad\quad\quad\quad\quad$ A partir del 1., Univ. La creación de instancias

4. $(Fx \to Gx)\quad\quad$ A partir de 2., Univ. La creación de instancias

5. $Gx\quad\quad\quad\quad\quad$ A partir de 3, 4 por MP

6. $\forall xGx\quad\quad\quad\quad$ A Partir De 5, Univ. La generalización de

Este es un superficial de la diferencia, sin embargo: el papel de la libre (independiente) variable como parámetro. Y hemos visto, incluso en el sector informal argumentos, utilizamos expresiones como "él" o incluso "Alicia" como parámetros. Miró a la luz de esto, no debería haber ningún misterio acerca de por qué necesitamos de los parámetros en una lógica formal. Y en una sintaxis, independiente de las variables de desempeñar el papel de los parámetros.

Answer 2

Categórica lógica implica una manera muy natural pensar de variables libres: son otro tipo de elemento.

Existe una noción de "generalizada elemento" de un objeto $X$ en una categoría, la cual es simplemente cualquier morfismos cuyo codominio es $X$. Ordinario de los elementos de los conjuntos pueden ser vistos como generalizada de los elementos, mediante la identificación de un elemento $a \in X$ con la función

$$ f : \{ \varnothing \} \to X : \varnothing \mapsto a $$

El mapa de identidad en $X$, interpretarse como una generalización de los elemento, resulta ser una excelente manera de capturar la noción de un "indeterminado variable" o un "elemento genérico".

Cuando tenemos una colección de variables libres $x_1, \ldots, x_n$ de nuestro dominio de discurso, y hacemos una interpretación en el conjunto $U$, los interpretamos como la generalización de los elementos correspondientes a la proyección de los mapas de $U^n \to U$.

Podemos, en consecuencia interpretar la relación $R$ como ser un particular mapa

$$ R : U^2 \to \{ \text{true}, \text{false} \} $$

y $R(x,y)$ es el correspondiente generalizada elemento de $\{ \text{true}, \text{false} \}$.

Answer 3

Si no se tiene en cuenta las fórmulas con variables libres, entonces uno no puede escribir una prueba por inducción sobre la formación de fórmulas. Cada primer fin de fórmula está construido a partir de primitivas fórmulas por poner un cuantificador en frente de una fórmula con una variable libre, con lo que la unión de la variable, o de la aplicación de operaciones como "y", "o", "no", "si..., entonces...", etc., en otras fórmulas. En el paso inductivo en una prueba por inducción que muestran que si la cosa que estamos tratando de demostrar que es verdadero de dos fórmulas de $A$$B$, entonces es verdad lo de $[A\text{ or }B]$ y es verdad lo de $\exists x\ B$, y así sucesivamente.

Los del teorema dice que si una de primer orden enunciado es verdadero en "casi todos" factor en un ultraproduct, entonces es verdadero en el ultraproduct. Los del teorema se demuestra por inducción en la formación de primer orden fórmulas.

Answer 4

Voy a añadir este comentario largo tratando de responder a tu comentario de arriba :

"¿Cuál es la diferencia entre una variable libre y el uso de $∃x$ ? Quiero decir, ¿no $∃x$ igual que algunos variable aleatoria?"

Creo que tenemos que empezar de nuevo desde el libre variables y cuantificadores ...

"¿Qué son las variables libres realmente útil?"

Creo que es mejor preguntar : "¿cuáles son los cuantificadores útil ?"

Considere un ejemplo de álgebra elemental :

$(x + y)^2 = x^2 + 2xy + y^2$.

Generalmente, no hacemos uso de cuantificadores, esta "ley", pero es implícitamente universalmente cuantificada, es decir, tha "la intención de" el sentido de la ley es :

para cada dos números de $x$$y$, por encima de la identidad posee; es decir,

$\forall x \forall y [(x + y)^2 = x^2 + 2xy + y^2]$.

Por lo tanto, podemos pensar que, en la habitual práctica de matemáticas, se podrá dispensar con el cuantificador universal.

Considere ahora la siguiente fórmula aritmética :

$x = 0$.

Si la consideramos como implícitamente universalmente cuantificada :

$\forall x (x = 0)$

es claramente falso.

Por lo tanto, ¿qué acerca de su negación :

$\lnot (x = 0)$

Esperamos que la negación de un falso fórmula será verdadera. Pero si aplicamos de nuevo la "regla" de la "implícito el cuantificador universal", lo que tenemos es :

$\forall x \lnot (x = 0)$

que vuelvan a expresar una falsa realidad, porque hay, al menos, el número de $0$ que satisfacen la identidad de $x=0$.

Y aquí vienen ... los cuantificadores.

Si estamos de acuerdo en que $x = 0$ debe tener el mismo "significado" como $\forall x (x = 0)$, entonces su negación será $\lnot \forall x (x = 0)$, la cual es :

$\exists x \lnot (x = 0)$.

El hecho es que no es posible expresar todos los "interesantes" de los hechos, queremos expresar simplemente con cuantificadores universal por adelantado.

Espero que esto aclare un poco el asunto, dando también una explicación de la función de $\exists$.

---

No está claro para mí lo que se le menaing con : "$\exists x$ es el mismo que algunos variable aleatoria".

El cuantificador existencial es necesaria en orden a expresar el hecho de que en un cierto "dominio de discurso" sabemos que hay algunos objetos (al menos uno) que satisfacen una cierta propiedad.

Por ejemplo, tenemos que en el dominio $\mathbb N$ natural numebrs, no es un objeto (un número) que satisfacen la identidad : $x = 0$. Precisamente, el número de $0$.

Por lo tanto, estamos autorizados para el estado de los siguientes verdadero hecho acerca de $\mathbb N$ :

$\exists x (x = 0)$.

Anteriormente hemos visto que :

$\exists x \lnot (x = 0)$

es cierto; pero las dos de la fórmula son no contradictorias [ellos no forman un par $\alpha$$\lnot \alpha$]; simplemente tomamos el número de $1$ y tenemos que satisfacer la identidad : $\lnot (x = 0)$.

---

Peter Smith respuesta de arriba te da, además, una hermosa explicación de la función de variables libres en la lógica de primer orden de las pruebas.