Reconstrucción del lenguaje FOL

Question

Reconstrucción del lenguaje FOL

lógica
Matemáticas
cuantificadores
lógica de primer orden

Ahmed Lazar

Si tenemos un lenguaje FOL $S$ y de repente perdimos su estructura lógica $\left(\rightarrow,\wedge,\vee,\bot,\top,\forall x,\exists x\right)$ , podemos recuperarlo (módulo a equivalencia lógica) usando solo la relación de consecuencia lógica: $\models$ ?

Consideremos $S$ el conjunto de fórmulas de una lógica de primer orden y $\bar S$ su cociente establecido por la relación de equivalencia lógica ( $\equiv$ ).

Todos los conectores lógicos sobre $\bar S$ obviamente se puede expresar usando solo $\models$ , Por ejemplo:

\bar{pag} \to \bar{q} = {r \in S | \forall s \in S, s ⊨ r \Leftrightarrow s, pag ⊨ q}

$\bar p\rightarrow\bar q=\left\{r\in S\ |\ \forall s\in S,s\models r\Leftrightarrow s,p\models q\right\}$

Ahora, y para reconstruir cuantificadores, consideremos el siguiente conjunto:

Π = {π \in ({\bar{S}}^{\bar{S}})^{*} | \begin{array}{l} \forall pag \in \bar{S}, (π pag ⊨ pag) \land (π π pag = π pag) \\ \forall pag, q \in \bar{S}, π (π pag \to π q) = π pag \to π q \\ \forall pag \in \bar{S}, Γ \subseteq \bar{S}, Γ ⊨ pag \Rightarrow π Γ ⊨ π pag \end{array}}

$\Pi = \left\{\pi\in\big(\bar S^\bar S\big)^*\ \middle\vert\ \begin{array}{l} \forall p\in\bar S, (\pi\ p\models p)\wedge(\pi\ \pi\ p=\pi\ p) \\ \forall p,q\in\bar S, \pi\ (\pi\ p\rightarrow\pi\ q)=\pi\ p\rightarrow\pi\ q\\ \forall p\in\bar S,\Gamma\subseteq\bar S,\Gamma\models p\Rightarrow \pi\ \Gamma \models \pi\ p \end{array}\right\}$ Creo que elementos de

Π_{e} = {π \in Π, \exists! (π_{1}, π_{2}) \in Π^{2}, π = π_{1} \circ π_{2}}

$\Pi_e=\left\{\pi\in\Pi,\exists!\left(\pi_1,\pi_2\right)\in\Pi^2,\pi=\pi_1\circ\pi_2\right\}$ son cuantificadores universales (es decir

p \mapsto \forall x, p [a \leftarrow x]

$p\mapsto\forall x, p[a\leftarrow x]$ dónde

x

$x$ no ocurre en

p

$p$ y

a

$a$ es una variable o una constante) más conjunciones de sustituciones circulares:

pag \mapsto \underset{i < norte}{⋀} pag [X_{0} \leftarrow X_{i}, . . ., X_{k} \leftarrow X_{(k + i modificación norte)}, . . ., X_{norte - 1} \leftarrow X_{(norte - 1 + i modificación norte)}]

$p\mapsto\bigwedge_{i<n}p\left[x_0\leftarrow x_i,...,x_k\leftarrow x_{(k+i \mod n)},...,x_{n-1}\leftarrow x_{(n-1+i \mod n)}\right]$ Dónde

(x_{i})_{i}

$(x_i)_i$ pueden ser variables, funciones o relaciones de la misma aridad.

¿Es cierta esta afirmación en el FOL intuicionista y en el FOL clásico?

Si el tema del agujero ya se discutió, ¿podría alguien por favor referirme a los artículos apropiados? Muchas gracias.

EDITAR: Para ser más claro, estoy preguntando sobre la recuperación de la firma lógica hasta una equivalencia lógica. Entonces podemos determinar alguna relación entre las clases de equivalencia de fórmulas como: $\overline{\forall x, P(x)}$ es el resultado de una aplicación del cuantificador universal en $\overline{P(x)}$ mientras $\overline{P(x)\wedge Q(x)}$ no es.

EDITAR: Y dado que esto no es posible en general, ¿es posible al menos cuando la firma no lógica es finita y contiene al menos una relación de aridad distinta de cero y una función de aridad distinta de cero?

noah schweber

Tenga en cuenta que parece estar haciendo malabarismos entre oraciones y fórmulas un poco, aquí; en última instancia, no hace ninguna diferencia, pero trabajar con oraciones solo complica las cosas (ya que en general

\forall x φ (x)

$\forall x\varphi(x)$ puede ser una oración sin

φ (x)

$\varphi(x)$ siendo una oración).

Ahmed Lazar

Sí, tienes razón, lo siento por ese error.

Respuestas (1)

Reconstrucción del lenguaje FOL

Tenga en cuenta que parece estar haciendo malabarismos entre oraciones y fórmulas un poco, aquí; en última instancia, no hace ninguna diferencia, pero trabajar con oraciones solo complica las cosas (ya que en general $\forall x\varphi(x)$ puede ser una oración sin $\varphi(x)$ siendo una oración).

noah schweber · Answer 1

EDITAR: Las fórmulas facilitan aún más la situación: cualquier permutación de las variables induce un automorfismo de $\mathcal{B}$ . Por esta razón, he dejado mi respuesta mayormente como está, ya que la situación interesante es cuando restringimos la atención a las oraciones.

(Lo anterior supone que no identificamos una fórmula con su cierre universal; si lo hacemos, entonces la situación es la misma que para las oraciones, ya que cada fórmula es equivalente a una oración, a saber, su cierre universal).

No, no puedes hacer esto en general: cuando miramos el álgebra booleana $\mathcal{B}$ de clases de equivalencia semántica de $S$ -frases (que es lo que te queda cuando olvidas todo menos " $\models$ "- por cierto, esta es el álgebra de Lindenbaum de la teoría vacía sobre $S$ ), este álgebra tiene muchos automorfismos no triviales: estos enviarán oraciones a oraciones no equivalentes mientras conservan el $\models$ -estructura.

Bajo hipótesis débiles sobre $S$ (asumamos $S$ es contable por ahora) podemos probar esto rápidamente. Si $S$ contiene dos símbolos distintos del mismo tipo (por ejemplo, dos símbolos constantes, o dos $17$ símbolos de relación -aria, etc.), luego intercambiarlos induce un automorfismo no trivial de $\mathcal{B}$ . Más complicado, si $S$ es infinito entonces $\mathcal{B}$ es un álgebra booleana sin átomos numerable, y estos son homogéneos (dados dos elementos ninguno de los cuales es $0$ o $1$ , hay un automorfismo intercambiándolos); esto se demuestra mediante un argumento de ida y vuelta, similar al presentado en esta prueba de que dos álgebras booleanas sin átomos contables son isomorfas . Del mismo modo, si $S=\emptyset$ entonces cualquier permutación de las oraciones de la forma "hay exactamente $n$ elementos" induce un automorfismo de $\mathcal{B}$ .

De hecho, creo que nunca podremos realizar la reconstrucción que desea, pero aún no tengo una prueba de eso. Tenga en cuenta en particular que podemos producir ejemplos de $S$ donde algunos elementos de $\mathcal{B}$ son átomos, pero otros elementos no se encuentran por encima de ningún átomo, por lo que no es ni sin átomos ni "atómico"; esto complica un poco la imagen.

La imagen para la lógica intuicionista será similar, excepto que las álgebras de Heyting toman el papel de las álgebras booleanas. En general, cualquier lógica que permita una cantidad significativa de reconstrucción a lo largo de las líneas que está proponiendo tendría que ser muy "algebraicamente restrictiva" (en el sentido de lógica algebraica ), y no conozco ninguna lógica natural de este tipo.

Gracias por su respuesta. De hecho, cometí un error, escribí oraciones en lugar de fórmulas. Puedes por favor, verlo de nuevo :)
@AhmedLazhar: Eso realmente no cambia nada, porque generalmente consideramos que una fórmula sin oración y su cierre universal se vinculan entre sí. Entonces, cada una de las clases de equivalencia contendrá algunas oraciones de todos modos.
@HenningMakholm No estoy seguro de qué tan habitual es eso. Creo que las cosas son casi siempre más interesantes sin él. Ciertamente hace que la cuantificación sea más agradable, ya que $\forall xP(x)$ y $\forall xP(y)$ no son equivalentes a pesar de que los cierres universales de $P(x)$ y $P(y)$ son equivalentes.
@NoahSchweber, ¿y si la firma es finita? Por ejemplo, consideremos nuestra firma con dos relaciones $P(x)$ y $R(x,y)$ entonces $\forall x\forall y(P(x)\wedge Q(x,y)\wedge x=y)$ es un átomo Si la lógica no es con igualdad o requerimos la existencia de infinidad de elementos, entonces $\forall x\forall y(P(x)\wedge Q(x,y))$ sería un átomo. Es eso cierto ? En ese caso, ¿cuáles pueden ser los elementos de mi $\Pi$ ? Debo mencionar que lo que busco es reconstruir la firma lógica. No hay problema si intercambio dos símbolos siempre que se recupere la estructura de la oración del agujero.
Incluso si añadimos $\neg\forall x\forall y(P(x)\wedge R(x,y))$ como un axioma, ¿no podemos tomar como átomo $\forall x\forall y\ne a(P(x)\wedge R(x,y))$ si la lógica es con igualdad y $\forall x\forall y(P(x)\wedge R(x,f(y)))$ de lo contrario ?
no podemos tomar $\forall x\forall y(P(x)\wedge R(x,f(y)))$ como un átomo porque se sigue de $\forall x\forall y(P(x)\wedge R(x,f(y))\wedge R(x,a))$ . Entonces, olvidémonos de la lógica sin igualdad y concentrémonos solo en FOL con igualdad.

Reconstrucción del lenguaje FOL

Ahmed Lazar

noah schweber

Ahmed Lazar

Respuestas (1)

noah schweber

Ahmed Lazar

hmakholm sobra a Monica

noah schweber

Ahmed Lazar

Ahmed Lazar

Ahmed Lazar

¿Cómo traduzco 'ningún estudiante de filosofía admira a ningún profesor podrido' en una fórmula lógica cuantificacional?

¿Cuál es el significado de estas declaraciones predicativas de primer orden?

Traducción de la oración a la pregunta FOL

¿Cómo puedo probar que las dos definiciones siguientes del cuantificador de unicidad en lógica de primer orden son equivalentes?

¿Por qué podemos usar la implicación con el cuantificador universal pero no con el cuantificador existencial?

Análisis I (Terence Tao)—Variables libres y ligadas

¿Es la teoría de los lenguajes formales regulares finitamente axiomatizable?

Definición de rango de términos en lenguaje de primer orden

Necesito ayuda con respecto a una prueba en First Order Logic

¿Es esta teoría del conteo recursivo equiinterpretable con PA?