¿Cómo razono con las funciones de Skolem?

Oct 31 2020

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

2 DavidW Nov 01 2020 at 09:21

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) $$

PatrickBrowne Nov 08 2020 at 15:24

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}