Completitud limitada y cuantificadores restringidos

Question

Completitud limitada y cuantificadores restringidos

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

Amr

Dejar $L$ ser un lenguaje de primer orden sin constantes ni símbolos de operación. $L$ también tiene un símbolo de relación $R$ de aridad $2$ . Dejar $T$ sea un conjunto de fórmulas de Godel. Dejar $Q^1,Q^2$ ser dos fórmulas. La única variable libre de $Q^1$ es $v_1$ y la única variable libre de $Q^2$ es $v_2$ . $v_1$ no ocurre dentro $Q^2$ y $v_2$ no ocurre dentro $Q^1$ . Se da que:

\exists v_{1} (q^{1}), \exists v_{2} (q^{2}) \in T . . . (1)

$\exists v_1(Q^1),\exists v_2(Q^2)\in T...(1)$ También se da que para toda fórmula

P^{1}

$P^1$ con solo

v_{1}

$v_1$ como su variable libre, se cumple lo siguiente:

\forall v_{1} (q^{1} \to {PAG}^{1}) \in T o \forall v_{1} (q^{1} \to (\neg {PAG}^{1})) \in T . . . (2)

$\forall v_1 (Q^1\rightarrow P^1)\in T \,\,\text{or}\,\,\forall v_1(Q^1\rightarrow (\lnot P^1))\in T...(2)$

Informalmente, esto significa que si hay un objeto que satisface $Q^1$ , entonces sabemos todo al respecto.

Del mismo modo, para cada fórmula $P^2$ con solo $v_2$ como su variable libre, se cumple lo siguiente:

\forall v_{2} (q^{2} \to {PAG}^{2}) \in T o \forall v_{2} (q^{2} \to (\neg {PAG}^{2})) \in T . . . (3)

$\forall v_2 (Q^2\rightarrow P^2)\in T \,\,\text{or}\,\,\forall v_2(Q^2\rightarrow (\lnot P^2))\in T...(3)$

Realmente creo que lo siguiente debe ser cierto, pero no puedo probarlo:

\forall v_{1} \forall v_{2} [(q^{1} \land q^{2}) \to R (v_{1} v_{2})] \in T o \forall v_{1} \forall v_{2} [(q^{1} \land q^{2}) \to (\neg R (v_{1} v_{2}))] \in T . . . (4)

$\forall v_1\forall v_2 [(Q^1\land Q^2)\rightarrow R(v_1v_2)]\in T \,\,\text{or}\,\,\forall v_1\forall v_2 [(Q^1\land Q^2)\rightarrow \big(\lnot R(v_1v_2)\big)]\in T...(4)$

Me gustaría ver una prueba de la afirmación anterior.

Gracias

Un conjunto de Godel es un conjunto de fórmulas de máxima consistencia que contiene todos los axiomas lógicos, tautologías y está cerrado bajo el modus ponens y la regla de generalización de $\forall$ . Esta definición se usa en el libro de Manin y pensé que era estándar.

Amr

¿La pregunta es poco clara o poco interesante?

memming

Se necesita un mejor título para uno.

Amr

@Memming Sí, pero no se me ocurre un título mejor

matemáticas duras

He intentado dar un título más incisivo. No sé la respuesta, pero mi intuición es que es falsa y que se puede usar un modelo para demostrarlo.

Amr

@hardmath ¿Por qué tu intuición es falsa? Tengo la intuición de que es verdad. Seguiré probando las ideas dadas en las respuestas a continuación.

matemáticas duras

No conozco la frase conjunto de fórmulas de Goedel, pero parece significar una teoría completa. Eso sería más claro si habláramos de oraciones en lugar de fórmulas, pero con el requisito de cierre bajo Generalización, la distinción casi parece discutible.

matemáticas duras

asi que tengo en mente que

T

$T$ equivale a oraciones que son verdaderas en algún modelo fijo. La intuición es entonces similar a lo que expresan las dos Respuestas anteriores. Podríamos tener un modelo en el que todos los elementos sean intercambiables. Sin embargo, conocer la satisfacibilidad de una fórmula con una variable libre es suficiente para determinar la verdad de las fórmulas con dos variables libres, así es como entendí tu pregunta.

matemáticas duras

Vaya, quise decir " no es suficiente" en el último comentario. Quizás la distinción entre gráficos regulares y fuertemente regulares es análoga, o más concretamente, transitiva de vértice pero no transitiva de borde.

Respuestas (3)

Completitud limitada y cuantificadores restringidos

He intentado dar un título más incisivo. No sé la respuesta, pero mi intuición es que es falsa y que se puede usar un modelo para demostrarlo.
@hardmath ¿Por qué tu intuición es falsa? Tengo la intuición de que es verdad. Seguiré probando las ideas dadas en las respuestas a continuación.
No conozco la frase conjunto de fórmulas de Goedel, pero parece significar una teoría completa. Eso sería más claro si habláramos de oraciones en lugar de fórmulas, pero con el requisito de cierre bajo Generalización, la distinción casi parece discutible.
asi que tengo en mente que $T$ equivale a oraciones que son verdaderas en algún modelo fijo. La intuición es entonces similar a lo que expresan las dos Respuestas anteriores. Podríamos tener un modelo en el que todos los elementos sean intercambiables. Sin embargo, conocer la satisfacibilidad de una fórmula con una variable libre es suficiente para determinar la verdad de las fórmulas con dos variables libres, así es como entendí tu pregunta.
Vaya, quise decir " no es suficiente" en el último comentario. Quizás la distinción entre gráficos regulares y fuertemente regulares es análoga, o más concretamente, transitiva de vértice pero no transitiva de borde.

Wafik · Answer 1

Wafik

La afirmación es falsa. Dejar $Q_1$ ser $v_1=v_1$ y de manera similar para $Q_2$ . Considere una estructura $A$ dónde $R(x, y)$ a veces se sostiene y a veces falla, y deja $T$ sea el conjunto de todos los enunciados verdaderos en $A$ .

Amr

¡Hola, doctor Wafik!

Q_{1}

$Q_1$ definido para ser

v_{1} = v_{1}

$v_1=v_1$ no satisface: Para cada fórmula

P^{1}

$P^1$ con solo

v_{1}

$v_1$ como su variable libre, se cumple lo siguiente:

\forall v_{1} (q^{1} \to {PAG}^{1}) \in T o \forall v_{1} (q^{1} \to (\neg {PAG}^{1})) \in T

$\forall v_1 (Q^1\rightarrow P^1)\in T \,\,\text{or}\,\,\forall v_1(Q^1\rightarrow (\lnot P^1))\in T$ , lo hace ?

Amr

En mi pregunta,

(1), (2), (3)

$(1),(2),(3)$ son dados y

(4)

$(4)$ es lo que se requiere probar.

Wafik

Tienes razón. yo estaba descuidado La construcción de la estructura necesita lo siguiente: R forma un ciclo, y todas las demás relaciones siempre se mantienen. Ahora cada elemento satisface las mismas fórmulas con una variable libre.

Amr

Que hace

R

$R$ media cíclica? ¿Significa que

A ⊨ {\forall x \forall y [R (x y) \to R (y x)]}

$A\models {\{\forall x\forall y [R(xy)\rightarrow R(yx)]\}}$

UsuarioB1234 · Answer 2

Creo que la afirmación que quieres es falsa.

Dejar $L=\{R\}$ . Dada una oración $\varphi$ de L, sea $\varphi{'}$ Sea la oración obtenida reemplazando cada ocurrencia de $R$ en $\varphi$ por $=$ . Dejar $\psi_{\varphi}:=\varphi \iff \varphi{'}$ .

Ahora deja $T_{0}$ = La teoría de la igualdad $\cup$ hay exactamente dos elementos $\cup \{\psi_{\varphi}:=\varphi \iff \varphi{'}: \varphi \text{ is an L sentence with R in it}\}$ . Dejar $M\models{T_{0}}$ . Dejar $T=Th(M)$ . Dejar $Q^{1}:=v_{1}=v_{1}$ , $Q^{2}:=v_{2}=v_{2}$ . Ahora está claro que la conclusión que quieres no es cierta.

Ahora deja $P^{1}$ ser una fórmula con sólo $v_{1}$ gratis. Estoy bastante seguro de que podemos probar $\forall{v_{1}}(Q^{1}\implies{P^{1}})\in{T}$ o $\forall{v_{1}}(Q^{1}\implies{\neg P^{1}})\in{T}$ . por una inducción sobre la complejidad de $P^{1}$ : Sin embargo, es más complicado de lo que esperaba.

Gracias por tu ayuda. Un conjunto de Godel es un conjunto de fórmulas de máxima consistencia que contiene todos los axiomas lógicos, tautologías y está cerrado bajo el modus ponens y la regla de generalización de la lógica de primer orden. Esta definición se usa en el libro de Manin y pensé que era estándar.
Ah, ya veo. Editaré mi respuesta, pero creo que esto todavía te da lo que estás buscando, ¿o es algo diferente?
No estoy de acuerdo cuando dices: "Estoy bastante seguro de que podemos probar $\forall{v_{1}}(Q^{1}\implies{P^{1}})\in{T}$ o $\forall{v_{1}}(Q^{1}\implies{\neg P^{1}})\in{T}$ ."
Informalmente, si sólo sabemos que $c_1=c_1$ para algunas constantes en nuestro modelo, es posible que no podamos determinar todo sobre $c_1$ Realmente creo que los contraejemplos son fáciles de encontrar.
Dejar $L=\{\in\}$ . Por ejemplo, si dejas $T$ sea cualquier conjunto godeliano que contenga todos los axiomas de ZFC y todos los axiomas lógicos de $=$ ... No se sostiene que $\forall v_1[v_1=v_1\rightarrow v_1=\emptyset]\in T$ o $\forall v_1[v_1=v_1\rightarrow \lnot(v_1=\emptyset)]\in T$ . Desde $\forall v_1[v_1=v_1]$ es cierto y $T$ es godeliano, se seguirá que $\forall v_1[v_1=\emptyset]\in T$ o $\forall v_1[v_1\not=\emptyset]\in T$
La idea detrás de este ejemplo es que el lenguaje con solo igualdad es muy débil. Solo puede decir algunas cosas. Tus ejemplos donde las cosas van mal son mucho más complicados (tienes constantes en tu idioma y $ZFC$ es lo más complicado posible (ver aquí: en.wikipedia.org/wiki/Stable_theory ). Aquí las cosas son mucho más simples: solo hay una fórmula atómica con solo $v_{1}$ gratis: $v_{1}=v_{1}$ . Entonces, el resultado que desea está claramente establecido para atómico $P^{1}$ . Ahora haz una inducción sobre la complejidad de $P^{1}$ y el resultado debería seguir (aunque necesitas hacer algo de trabajo)

Amr · Answer 3

La respuesta es no. Daré el contraejemplo a continuación.

Considere el lenguaje de primer orden $L=\{\equiv\}$ que solo tiene el símbolo de relación binaria $\equiv$ . Dejar $M:=\{0,1\}$ . Definimos una interpretación $\Phi$ de $L$ en $M$ como sigue:

Φ (\equiv) := {(a, a) | a \in METRO}

$\Phi(\equiv):=\{(a,a)|a\in M\}$ Desde

L

$L$ no tiene ningún símbolo constante o de operación, la línea de arriba determina completamente nuestra interpretación

Φ

$\Phi$ . Ahora considera

f : M \to M

$f:M\rightarrow M$ que envía

0

$0$ a

1

$1$ y

1

$1$ a

0

$0$ . Claramente,

f

$f$ es una biyección.

Dejar $Var$ denota el conjunto de variables en nuestro alfabeto.

Claim1: Para cada fórmula $P$ en $L$ y cada interpretación $\Gamma:Var\rightarrow M$ , tenemos $|P|_{\Phi}(\Gamma)=|P|_{\Phi}(f\Gamma)$

Prueba: inducción sobre la longitud de la fórmula. $P$ . Dejar $\Gamma$ Sea nuestra función de interpretación de los símbolos de las variables. Base: $P$ es atómico. Caso 1: $P$ es " $\equiv(x_1x_2)$ " y $x_1,x_2$ son dos símbolos variables (posiblemente $x_1$ es el símbolo como $x_2$ ). Desde $f$ es una biyección, por lo tanto $\Gamma(x_1)=\Gamma(x_2)$ si y si $f\Gamma(x_1)=f\Gamma(x_2)$ . Por eso, $(\Gamma(x_1),\Gamma(x_2))\in \Phi(\equiv)$ si y si $(f\Gamma(x_1),f\Gamma(x_2))\in \Phi(\equiv)$ . De este modo, $|P|_{\Phi}(\Gamma)=|P|_{\Phi}(f\Gamma).$ La prueba del paso de inducción es trivial y se sigue inmediatamente de la definición recursiva de $|P|_{\Phi}(\Gamma)$ . $\square$

Ahora deja $T$ sea el subconjunto de las fórmulas de $L$ que es deinido por $T:=\{P|\text{For every interpretation of the variable symbols $\Gamma$, we have $|P|_{\Phi}(\Gamma)=1$}\}$ . Es un teorema que el conjunto de enunciados verdaderos sobre una estructura forman un conjunto godeliano. Por eso, $T$ es godeliano.

Ahora usando ideas de las otras dos respuestas.

Ahora configura $Q^1,Q^2$ ser $v_1=v_1,v_2=v_2$ . Mirando nuestra interpretación $\Phi$ , podemos ver claramente que $\exists v_1(Q^1),\exists v_2(Q^2)\in T$ .

Afirmación 2: para cada fórmula $P^1$ eso $v_1$ como su única variable libre, O bien $\forall v_1[ P^1]\in T$ o $\forall v_1[\lnot P^1]\in T$

Prueba: suponga que la primera opción no se cumple, por lo tanto, hay alguna interpretación variable $\Gamma$ tal que $| P^1|_{\Phi}(\Gamma)=0$ . Por eso, $| \not P^1|_{\Phi}(\Gamma)=1$ . Usando la Reclamación 1, obtenemos $| \lnot P^1|_{\Phi}(f\Gamma)=1$ también. Ahora para cualquier interpretación variable $\Theta$ , cualquiera $\Theta(v_1)=\Gamma(v_1)$ o $\Theta(v_1)=f\Gamma(v_1)$ (porque el tamaño de nuestro modelo es dos y $f$ no tiene puntos fijos). Desde $v_1$ es la única variable libre de $P^1$ . Así, ya sea $| \lnot P^1|_{\Phi}(\Theta)=| \lnot P^1|_{\Phi}(\Gamma)=1$ o $| \lnot P^1|_{\Phi}(\Theta)=| \lnot P^1|_{\Phi}(f\Gamma)=1$ . Por eso, $| \lnot P^1|_{\Phi}(\Theta)$ es siempre $1$ para cualquier interpretación variable $\Theta$ . De este modo, $|\forall v_1( \lnot P^1)|_{\Phi}(\Theta)=1$ para cada $\Theta$ . De este modo, $\forall v_1( \lnot P^1) \in T$ . $\square$

Desde, $\forall v_1(Q^1)\in T$ uno usa la afirmación 2 para mostrar que:

\forall v_{1} (q^{1} \to {PAG}^{1}) \in T o \forall v_{1} (q^{1} \to (\neg {PAG}^{1})) \in T

$\forall v_1 (Q^1\rightarrow P^1)\in T \,\,\text{or}\,\,\forall v_1(Q^1\rightarrow (\lnot P^1))\in T$ Del mismo modo, también se puede demostrar que:

\forall v_{2} (q^{2} \to {PAG}^{2}) \in T o \forall v_{2} (q^{2} \to (\neg {PAG}^{2})) \in T

$\forall v_2 (Q^2\rightarrow P^2)\in T \,\,\text{or}\,\,\forall v_2(Q^2\rightarrow (\lnot P^2))\in T$

Sin embargo, mirando el modelo $M$ y la interpretacion $\Phi$ podemos ver claramente que:

\forall v_{1} \forall v_{2} [(q^{1} \land q^{2}) \to\equiv (v_{1} v_{2})] \notin T y \forall v_{1} \forall v_{2} [(q^{1} \land q^{2}) \to (\neg \equiv (v_{1} v_{2}))] \notin T

$\forall v_1\forall v_2 [(Q^1\land Q^2)\rightarrow \equiv(v_1v_2)]\not\in T \,\,\text{and}\,\,\forall v_1\forall v_2 [(Q^1\land Q^2)\rightarrow \big(\lnot \equiv(v_1v_2)\big)]\not\in T$

Ahora podemos aislar cierto concepto interesante en la prueba anterior y hacer la siguiente definición:

Dejar $L$ ser un lenguaje de primer orden con símbolos de relación solamente. Dejar $\Phi$ ser una interpretación de $L$ en $M$ . Decimos que una biyección $f:M\rightarrow M$ es un modelo de automorfismo iff para cada símbolo de relación $R$ en $L$ con aridad $r$ , tenemos lo siguiente:

Para cada $m_1,m_2,...,m_r\in M$ :

({metro}_{1}, {metro}_{2}, . . ., {metro}_{r}) \in Φ (R) si y si (F ({metro}_{1}), F ({metro}_{2}), . . ., F ({metro}_{r})) \in Φ (R)

$(m_1,m_2,...,m_r)\in \Phi(R) \,\,\, \text{iff} \,\,\,(f(m_1),f(m_2),...,f(m_r))\in \Phi(R)$

Claramente, el conjunto de automorfismos del modelo de $M$ forma un grupo bajo composición de funciones. Volveré y agregaré a esta publicación cuando tenga tiempo.

@DanulG Probé la parte de su solución para la que no proporcionó una prueba. Está relacionado con lo que yo llamaría modelo "automorfismos"
@hardmath La respuesta es no. Ahora tengo una prueba completa.

Completitud limitada y cuantificadores restringidos

Amr

Amr

memming

Amr

matemáticas duras

Amr

matemáticas duras

matemáticas duras

matemáticas duras

Respuestas (3)

Wafik

Amr

Amr

Wafik

Amr

UsuarioB1234

Amr

UsuarioB1234

Amr

Amr

Amr

Amr

UsuarioB1234

Amr

Amr

Amr

Amr

Amr

Amr

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

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

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?

Pregunta sobre mi prueba de: limh→0f(ch)=limch→0f(ch)limh→0f(ch)=limch→0f(ch) \lim_{h \to 0}f(ch)=\lim_{ch \ a 0}f(ch) para c≠0c≠0c\neq 0

Las teorías de máxima consistencia tienen subteorías contables completas en cada sublenguaje contable.

¿Es esta una traducción adecuada de ∃x(∅∈x)∃x(∅∈x)\exists x(\emptyset \in x) en L∈L∈\mathcal{L}_{\in}?

¿Cómo se sabe si A⟹BA⟹BA \implica que B (una implicación) es verdadera sin saber si BBB (el consecuente) es verdadera?

¿Podemos definir un conjunto que contenga todos los conjuntos dentro de ZFC y luego probar que no existe?