¿Cómo razono con las funciones de Skolem?
Dada la oración de primer orden.
$\forall x \forall y : (Overlap(x,y) \iff (\exists z Part(z,x) \land Part(z,y)))~~~~~~~~~~~~~~~~$( 1 )
Aquí hay una prueba esquemática (parcial) de que $Overlap$ es simétrico:
Prueba 1 \ begin {align} & \ text {1} ~~ \ forall x \ forall y: (Superposición (x, y) \ iff (\ existe z Part (z, x) \ land Part (z, y)) ) & \ tag {Axiom} \\ & \ text {2} ~~~~~~~ Superposición (a, b) \ tag {Asumir} \\ & \ text {3} ~~~~~~~ \ existe z (Part (z, a) \ land Part (z, b)) \ tag {1,2} \\ & \ text {4} ~~~~~~~ \ existe z (Part (z, b) \ Land Part (z, a)) \ tag {3} \\ & \ text {5} ~~~~~~~ Superposición (b, a) \ tag {1,2,4} \\ & \ text {6 } ~~ \ forall x \ forall y: (Superposición (x, y) \ implica Superposición (y, x)) \ tag {$\forall$-Intro 2-5} \\ \ end {align} Note en la línea 4 el mismo existencial$z$ se utiliza.
Ahora deseo escribir el axioma ( 1 ) en una forma equisatisfactable que pueda demostrarse usando lógica ecuacional y reescritura de términos. Esto generalmente requiere Skolemization. La oración ( 1 ) se puede skolemizar de la siguiente manera:
$\forall x \forall y : (Overlap(x,y) \iff (Part(Sk(x,y),x) \land Part(Sk(x,y),y))~~~~~~~~~~~$( 2 )
Ahora trato de probar la simetría usando ( 2 ) con un enfoque similar al de la Prueba 1 :
Intento de prueba 2 \begin{align} & \text{1}~~\forall x \forall y : (Overlap(x,y) \iff (Part(Sk(x,y),x) \land Part(Sk(x,y),y))& \tag{Axiom}\\ & \text{2}~~~~~~~~Overlap(a,b) \tag{Assume} \\ & \text{3}~~~~~~~~Part(Sk(a,b),a) \land Part(Sk(a,b),b) \tag{1,2}\\ & \text{4}~~~~~~~~Part(Sk(a,b),b) \land Part(Sk(a,b),a) \tag{3}\\ & \text{5}~~~~~~~~Overlap(b,a)\tag{XX}\\ & \text{6}~~\forall x \forall y : (Overlap(x,y) \implies Overlap(y,x)) \tag{XX} \\ \end{align}
Estoy atascado en las líneas 4-5 en el intento de prueba 2. Al seguir el enfoque de la prueba 1, hay un problema con el orden de los argumentos para las funciones de Skolem.
Respuestas
Este es un bosquejo de la idea principal. El axioma es el mismo si se intercambian los cuantificadores universales.
Skolemization de esto da $$\exists Sk \forall y \forall x \; Overlap(x, y) \Leftrightarrow Part(Sk(y, x), x) \land Part(Sk(y, x), y) \tag{a}\label{eqa}$$
que es equivalente a
$$\exists Sk \forall x \forall y \; Overlap(y, x) \Leftrightarrow Part(Sk(x, y), y) \land Part(Sk(x, y), x) \tag{b}\label{eqb}$$
cambiando los nombres de las variables.
También podemos mostrar de manera similar del Axioma que
$$\exists S \forall x \forall y \; Overlap(x, y) \Leftrightarrow Part(S(x, y), y) \land Part(S(x, y), x) \tag{c}\label{eqc}$$
De (\ ref {eqb}) y (\ ref {eqc}) y la suposición en las funciones de Skolem de que $\exists Sk \exists S \forall x \forall y \; Sk(x, y) = S(x, y)$, sigue
$$\forall x \forall y \; Overlap(x,y) \Leftrightarrow Overlap(y, x) $$
Podemos traducir el axioma bi-condicional original en tres implicaciones. Usando la equivalencia del cuantificador,$\exists x (Q(x) \implies P) \equiv \forall x Q(x) \implies P $, lo existencial en el original ( 1 ) puede ser reemplazado por un universal$z$, por lo que la línea 3 a continuación no necesita una función Skolem. Creo que estas 3 oraciones y la oración FOL ( 1 ) son equisatisfactorias . Creo que dividir ( 1 ) en tres partes hace que la prueba sea bastante sencilla.
Prueba \ begin {align} & \ text {1} ~~ \ forall x \ forall y: (Superposición (x, y) \ implica Parte (Sk (x, y), x)) & \ tag {Axiom1} \\ & \ text {2} ~~ \ forall x \ forall y: (Superposición (x, y) \ implica Part (Sk (x, y), y)) & \ tag {Axiom2} \\ & \ text {3} ~~ \ forall x \ forall y \ forall z: ((Part (z, x) \ land Part (z, y)) \ implica Superposición (x, y)) & \ tag {Axiom3} \\ & \ text { 4 (a, b)} ~~ Superposición (a, b) \ tag {Asumir} \\ & \ text {5} ~~~~~~~~~~~~~ (Parte (Sk (a, b) , a) \ land Part (Sk (a, b), b)) \ implica Superposición (a, b) \ tag {$\forall$-Elim 3} \\ & \ text {6} ~~~~~~~~~~~~~ Superposición (a, b) \ implica Parte (Sk (a, b), a) \ etiqueta {$\forall$-Elim 1} \\ & \ text {7} ~~~~~~~~~~~~~ Superposición (a, b) \ implica Parte (Sk (a, b), b) \ etiqueta {$\forall$-Elim 2} \\ & \ text {8} ~~~~~~~~~~~~~ Parte (Sk (a, b), a) \ tag {$\implies$-Elim 4,6} \\ & \ text {9} ~~~~~~~~~~~~~ Parte (Sk (a, b), b) \ tag {$\implies$-Elim 4,7} \\ & \ text {10} ~~~~~~~~~~~~~ Part (Sk (a, b), b) \ land Part (Sk (a, b), a ) \ tag {$\land$-Intro 8,9} \\ & \ text {11} ~~~~~~~~~~~~~ (Part (Sk (a, b), b) \ land Part (Sk (a, b), a)) \ implica Superposición (b, a) \ etiqueta {$\forall$-Elim 3} \\ & \ text {12} ~~~~~~~~~~~~~ Superposición (b, a) \ tag {$\implies$-Elim 10,11} \\ & \ text {13} ~~ \ forall x \ forall y: (Superposición (x, y) \ implica Superposición (y, x)) \ etiqueta {$\forall$-Intro 4-12} \\ \ end {align}