el sistema de hilbert: lógica de primer orden
TRANSCRIPT
![Page 1: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/1.jpg)
El sistema de Hilbert: Logica de Primer Orden
El sistema de deduccion de Hilbert para la logica de primer ordenconsta de los siguientes elementos:
IIC2213 – Logica de Primer Orden 55 / 65
![Page 2: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/2.jpg)
El sistema de Hilbert: Logica de Primer Orden
El sistema de deduccion de Hilbert para la logica de primer ordenconsta de los siguientes elementos:
! Esquemas para generar formulas validas:
(a) ϕ→ (ψ → ϕ)(b) (ϕ→ (ψ → θ))→ ((ϕ→ ψ)→ (ϕ→ θ))(c) (¬ϕ→ ¬ψ)→ ((¬ϕ→ ψ)→ ϕ)(d) (∀x ϕ(x))→ ϕ(t), donde t es un termino cualquiera(e) ϕ(t)→ (∃x ϕ(x)), donde t es un termino cualquiera(f) (∃x ϕ)↔ (¬∀x ¬ϕ)
IIC2213 – Logica de Primer Orden 55 / 65
![Page 3: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/3.jpg)
El sistema de Hilbert: Logica de Primer Orden
! Axiomas para la igualdad:
(a) ∀x (x = x)(b) ∀x∀y (x = y → y = x)(c) ∀x∀y∀z ((x = y ∧ y = z)→ x = z)(d) Para todo predicado m-ario P :
∀x1 · · · ∀xm∀y1 · · ·∀ym ((P(x1, . . . , xm) ∧
x1 = y1 ∧ · · · ∧ xm = ym)→ P(y1, . . . , ym))
(e) Para toda funcion n-aria f :
∀x1 · · · ∀xn∀y1 · · ·∀yn ((x1 = y1 ∧ · · · ∧ xn = yn) →
f (x1, . . . , xn) = f (y1, . . . , yn))
IIC2213 – Logica de Primer Orden 56 / 65
![Page 4: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/4.jpg)
El sistema de Hilbert: Logica de Primer Orden
! Reglas de inferencia:
(a) Modus Ponens:
ϕ→ ψϕψ
(b) Generalizacion: Si y no aparece libre en ϕ, entonces
ϕ→ ψ(y)ϕ→ ∀yψ(y)
IIC2213 – Logica de Primer Orden 57 / 65
![Page 5: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/5.jpg)
El sistema de Hilbert: Logica de Primer Orden
DefinicionDado un conjunto de formulas Σ ∪ {ϕ}, una deduccion formal de ϕdesde Σ es una secuencia de formulas ϕ1, ϕ2, . . ., ϕn tal que:
! Para cada i ≤ n:
! ϕi ∈ Σ o! ϕi es un axioma logico o! existen j , k < i tales que ϕi es obtenido desde ϕj y ϕk usando
modus ponens o! existe j < i tal que ϕi es obtenido desde ϕj usando la regla de
generalizacion
! ϕn = ϕ
IIC2213 – Logica de Primer Orden 58 / 65
![Page 6: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/6.jpg)
El sistema de Hilbert: Logica de Primer Orden
DefinicionDado un conjunto de formulas Σ ∪ {ϕ}, una deduccion formal de ϕdesde Σ es una secuencia de formulas ϕ1, ϕ2, . . ., ϕn tal que:
! Para cada i ≤ n:
! ϕi ∈ Σ o! ϕi es un axioma logico o! existen j , k < i tales que ϕi es obtenido desde ϕj y ϕk usando
modus ponens o! existe j < i tal que ϕi es obtenido desde ϕj usando la regla de
generalizacion
! ϕn = ϕ
NotacionΣ ⊢H ϕ
IIC2213 – Logica de Primer Orden 58 / 65
![Page 7: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/7.jpg)
El sistema de Hilbert: Propiedades
Teorema (Correccion)
Dado un conjunto de formulas Σ ∪ {ϕ}, si Σ ⊢H ϕ, entoncesΣ |= ϕ.
IIC2213 – Logica de Primer Orden 59 / 65
![Page 8: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/8.jpg)
El sistema de Hilbert: Propiedades
Teorema (Correccion)
Dado un conjunto de formulas Σ ∪ {ϕ}, si Σ ⊢H ϕ, entoncesΣ |= ϕ.
Ejercicio
Demuestre el teorema.
IIC2213 – Logica de Primer Orden 59 / 65
![Page 9: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/9.jpg)
El sistema de Hilbert: Propiedades
Teorema (Completidad de Godel)
Dado un conjunto de formulas Σ ∪ {ϕ}, si Σ |= ϕ, entoncesΣ ⊢H ϕ.
IIC2213 – Logica de Primer Orden 60 / 65
![Page 10: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/10.jpg)
El sistema de Hilbert: Propiedades
Teorema (Completidad de Godel)
Dado un conjunto de formulas Σ ∪ {ϕ}, si Σ |= ϕ, entoncesΣ ⊢H ϕ.
Corolario (Compacidad)
Un conjunto de formulas Σ es satisfacible si y solo si Σ esfinitamente satisfacible.
IIC2213 – Logica de Primer Orden 60 / 65
![Page 11: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/11.jpg)
El sistema de Hilbert: Propiedades
Teorema (Completidad de Godel)
Dado un conjunto de formulas Σ ∪ {ϕ}, si Σ |= ϕ, entoncesΣ ⊢H ϕ.
Corolario (Compacidad)
Un conjunto de formulas Σ es satisfacible si y solo si Σ esfinitamente satisfacible.
Ejercicio
Demuestre el corolario.
IIC2213 – Logica de Primer Orden 60 / 65
![Page 12: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/12.jpg)
Teorema de compacidad y el problema de definibilidad
Sea L un vocabulario y Struct[L] el conjunto de lasL-estructuras
Una propiedad P sobre las L-estructuras es un subconjunto deStruct[L]
IIC2213 – Logica de Primer Orden 61 / 65
![Page 13: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/13.jpg)
Teorema de compacidad y el problema de definibilidad
Sea L un vocabulario y Struct[L] el conjunto de lasL-estructuras
Una propiedad P sobre las L-estructuras es un subconjunto deStruct[L]
! Ejemplo: {A | A ∈ Struct[L] y el dominio de A tiene almenos dos elementos}
IIC2213 – Logica de Primer Orden 61 / 65
![Page 14: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/14.jpg)
Teorema de compacidad y el problema de definibilidad
Una propiedad P se dice definible en logica de primer orden siexiste una L-oracion Φ tal que:
A ∈ P si y solo si A |= Φ
IIC2213 – Logica de Primer Orden 62 / 65
![Page 15: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/15.jpg)
Teorema de compacidad y el problema de definibilidad
Una propiedad P se dice definible en logica de primer orden siexiste una L-oracion Φ tal que:
A ∈ P si y solo si A |= Φ
Ejercicio
¿Que propiedad define la L-oracion ∃x∃y ¬(x = y)?
IIC2213 – Logica de Primer Orden 62 / 65
![Page 16: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/16.jpg)
Teorema de compacidad y el problema de definibilidad
¿Que herramientas podemos usar para demostrar que unapropiedad no es definible?
! Podemos usar el teorema de compacidad
IIC2213 – Logica de Primer Orden 63 / 65
![Page 17: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/17.jpg)
Teorema de compacidad y el problema de definibilidad
¿Que herramientas podemos usar para demostrar que unapropiedad no es definible?
! Podemos usar el teorema de compacidad
Veamos un ejemplo: Sea L un vocabulario arbitrario y
FIN = {A | A ∈ Struct[L] y el dominio de A es finito}
IIC2213 – Logica de Primer Orden 63 / 65
![Page 18: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/18.jpg)
Teorema de compacidad y el problema de definibilidad
¿Que herramientas podemos usar para demostrar que unapropiedad no es definible?
! Podemos usar el teorema de compacidad
Veamos un ejemplo: Sea L un vocabulario arbitrario y
FIN = {A | A ∈ Struct[L] y el dominio de A es finito}
Vamos a demostrar que FIN no es definible en logica de primerorden.
IIC2213 – Logica de Primer Orden 63 / 65
![Page 19: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/19.jpg)
Teorema de compacidad y el problema de definibilidad
Por contradiccion, suponemos que FIN es definible en logica de primerorden.
IIC2213 – Logica de Primer Orden 64 / 65
![Page 20: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/20.jpg)
Teorema de compacidad y el problema de definibilidad
Por contradiccion, suponemos que FIN es definible en logica de primerorden.
! Existe L-oracion Φ: A |= Φ si y solo si el dominio de A es finito
IIC2213 – Logica de Primer Orden 64 / 65
![Page 21: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/21.jpg)
Teorema de compacidad y el problema de definibilidad
Por contradiccion, suponemos que FIN es definible en logica de primerorden.
! Existe L-oracion Φ: A |= Φ si y solo si el dominio de A es finito
Para cada n ≥ 2, defina la L-oracion λn de la siguiente forma:
λn = ∃x1 · · · ∃xn
!"
1≤i<j≤n
¬(xi = xj )
#
IIC2213 – Logica de Primer Orden 64 / 65
![Page 22: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/22.jpg)
Teorema de compacidad y el problema de definibilidad
Por contradiccion, suponemos que FIN es definible en logica de primerorden.
! Existe L-oracion Φ: A |= Φ si y solo si el dominio de A es finito
Para cada n ≥ 2, defina la L-oracion λn de la siguiente forma:
λn = ∃x1 · · · ∃xn
!"
1≤i<j≤n
¬(xi = xj )
#
Ademas, defina Σ como el siguiente conjunto (infinito) de L-oraciones:
Σ = {Φ} ∪ {λn | n ≥ 2}
IIC2213 – Logica de Primer Orden 64 / 65
![Page 23: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/23.jpg)
Teorema de compacidad y el problema de definibilidad
Tenemos que cada subconjunto finito de Σ es satisfacible.
! ¿Por que?
IIC2213 – Logica de Primer Orden 65 / 65
![Page 24: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/24.jpg)
Teorema de compacidad y el problema de definibilidad
Tenemos que cada subconjunto finito de Σ es satisfacible.
! ¿Por que?
Por teorema de compacidad: Σ es satisfacible
! Existe una L-estructura A que satisface a Σ
IIC2213 – Logica de Primer Orden 65 / 65
![Page 25: El sistema de Hilbert: Lógica de Primer Orden](https://reader034.vdocumento.com/reader034/viewer/2022051007/586f50521a28ab14178bc0fc/html5/thumbnails/25.jpg)
Teorema de compacidad y el problema de definibilidad
Tenemos que cada subconjunto finito de Σ es satisfacible.
! ¿Por que?
Por teorema de compacidad: Σ es satisfacible
! Existe una L-estructura A que satisface a Σ
Entonces: A tiene un dominio infinito y A |= Φ
! Obtenemos una contradiccion
IIC2213 – Logica de Primer Orden 65 / 65