Me pregunto qué significa exactamente cuando la gente dice "Skolemization conserva satisfiability pero no de validez". Estoy teniendo problemas para envolver mi cabeza alrededor de ella porque creo que de Skolemization, cuando se la considera como una regla de inferencia, para ser "una buena cosa" cuando se trabaja con un segundo orden de la fórmula.
Skolemization se dice para preservar satisfiability pero no de validez. ¿Qué es exactamente lo satisfiability y validez significa en el contexto? ¿La "co-Skolemization" (doble a Skolemization como de segundo orden, equivalencia) tiene propiedades similares a la Skolemization?
Skolemization, como lo que puedo decir, se basa en la equivalencia entre el primer orden de la fórmula (y por lo tanto degenerado de segundo orden de la fórmula)
$$ \forall x_1 \cdots x_n . \exists y . P(x_1, \cdots, x_n, y) $$
y el siguiente de segundo orden de la fórmula, que se mueve a la $\exists$ frente a la $\forall$.
$$ \exists f. \forall x_1 \cdots x_n . P(x_1, \cdots, x_n, f(x_1, \cdots, x_n))$$
Tiene perfecto sentido cuando la expresión es pensado como un juego. En la primera expresión, el oponente primero hace $n$ se mueve y que hace el jugador 1. En la segunda expresión, el jugador que mueve primero, pero se compromete a una función de respuesta de la clase en lugar de comprometerse con un solo movimiento. Eso no es una prueba, pero parece un buen intuitiva justificación de por qué la reescritura de una expresión como esta está bien en el primer lugar.
A mí me parece que la realización de esta traducción sólo tiene sentido si estamos hablando de un circuito cerrado de expresión. Que es, $P(\cdots)$ no debe tener variables libres o, de manera equivalente, $P$ debe ser un $n+1$-lugar de predicado (primitivo o definido).
En lógica proposicional, satisfiability y validez pueden ser entendidas mediante la descripción de lo que sucede a las variables libres. Todas las variables son gratis porque no hay manera de obligar a ellos.
$ P \lor P $ es válido debido a que la asignación de $ \{ P = \top \} $ satisface.
$ P \lor \lnot P $ es una tautología, por razones obvias. No sé si es correcto decir $ P \lor \lnot P $ es válido.
Una regla de inferencia que se asigna a$P$ a $P \lor Q$ es válido (disyunción introducción).
Una regla que asigna a$P$ a $P \land Q$ conserva satisfiability. Podemos tomar cualquier edad asignación de $\mu$ y la construcción de $\mu \cup \{ Q = \top \}$ que satisface la nueva expresión.
En el contexto de Skolemization, son los significados de satisfiability y validez similar?
Vamos a "co-Skolemization" (probablemente tiene un nombre real), de ser la traducción de
$$ \exists x_1 \cdots x_n . \forall y . P(x_1, \cdots, x_n, y) $$
a
$$ \forall f . \exists x_1 \cdots x_n . P(x_1, \cdots, x_n, f(x_1, \cdots, x_n)) $$
Que parece tan legítimo como Skolemization, considerado como una regla de inferencia en un segundo orden de configuración. Hay una salvedad aquí que en un primer orden de la teoría de las definiciones se proporcionan para todas totalmente saturado combinaciones de símbolos de función y los argumentos. Por lo tanto, "co-Skolemization" definitivamente nos saca de primer orden de la tierra, pero no sé cómo lo relevante que es.
