Post on 09-Aug-2015
Estudio sema ntico y sinta ctico del
Ca lculo Predicativo Cla sico Jonathan Julián Huerta y Munive1, Dr. Iván Martínez Ruiz1.
1Facultad de Ciencias Físico-Matemáticas-BUAP.INTRODUCCIÓNHistoricamente el Calculo de Predicados surge como
resultado del trabajo de Gottlob Frege en su obra
titulada Begriffsschrift (Idiografía). Posteriormente,
Giuseppe Peano y Bertrand Russell divulgaron el trabajo
de Frege a otros matemáticos y filósofos haciéndolo uno
de los padres de la lógica moderna. Conceptualmente,
la Lógica Predicativa es un enriquecimiento del Calculo
Proposicional Clasico. Es un sistema formal con mayor
poder de expresividad y, más útil para el estudio de las
teorías matemáticas. De manera general se puede decir
que el Calculo de Predicados se diferencia del
Proposicional en que añade al lenguaje de éste último
los cuantificadores universal y existencial; las
constantes y variables proposicionales, adema s de
contener un conjunto de funciones y relaciones de n-
aridad. Como consecuencia, añade axiomas y reglas para
trabajar con estos nuevos símbolos. Los beneficios que
conllevan estas adiciones no vienen sin un costo, ya que
no es tan fácil corroborar la veracidad de una fórmula
en el Cálculo Predicativo como lo es para el
Proposicional por medio de tablas de verdad.
OBJETIVOSConstruir el lenguaje formal para las Lógicas Predicativas de
Primer Orden, verificar el concepto de satisfactibilidad para
una fórmula en este tipo de estructuras, enlistar los axiomas
básicos de un Cálculo de Predicados y deducir sus
propiedades y metateoremas tipicos como el teorema de
Lindembaum-Tarski, la prueba de Henkin para el teorema de
Completitud de Gödel, y el teorema de Löwenheim-Skolem.
METODOLOGÍASe consultaron diversas fuentes bibliográficas para obtener
las definiciones básicas y así demostrar los teoremas y
propiedades clásicos de un Cálculo Predicativo.
CONCLUSIONES• Se desarrolló la construcción del lenguaje del Cálculo de
predicados y se probaron varias propiedades del mismo, entre ellas
su lectura única.
• Se analizaron los conceptos de validez lógica y satisfactibilidad en
un cálculo de predicados.
• Se estudiaron varios meta-teoremas para la obtención de teoremas
y teorías del cálculo de predicados de primer orden.
• Se demostró que la teoría matemática del cálculo de predicados
de 1º orden es completa y consistente; no obstante, a diferencia del
cálculo proposicional, no existe un procedimiento efectivo para
determinar si una fórmula es teorema o no.
RESULTADOSSe probaron los siguientes meta-teoremas:
Teorema 1. Toda tautología es teorema del Cálculo de Predicados.
Teorema 2. Todo teorema es lógicamente válido.
Teorema 3. Si 𝜓 no depende de 𝜑 en la prueba de que Γ, 𝜑 ⊢ 𝜓, entonces
existe una prueba para Γ ⊢ 𝜓.
Teorema 4. (de la deducción) Si en una prueba de Γ, 𝜑 ⊢ 𝜓 no se aplicó
generalización a una prueba que dependa de 𝜑 sobre una variable libre de
𝜑 entonces hay una prueba de Γ ⊢ 𝜑 → 𝜓 .
Teorema 5. Si t es libre para x en 𝜑 entonces ∀𝑥 𝜑 𝑥 ⊢ 𝜑 𝑡 .
A continuación se enuncian los meta-teoremas más importantes
demostrados en la realización del proyecto de investigación y se da la
prueba conjunta del segundo y tercero:
Lema de Lindenbaum: Si K es una teoría consistente, entones existe una
extensión de ésta completa y consistente.
Teorema Fundamental de los Cálculos de Predicados de Primer Orden:
Toda teoría consistente tiene un modelo numerable.
Teorema de Completitud de Gödel: En cualquier cálculo de predicados
una fórmula 𝜓 es teorema si y sólo si es lógicamente válida.
Teorema de Löwenheim-Skolem: Toda teoría con un modelo también
tiene un modelo numerable.
Demostración:
Sea K una teoría consistente, por el 1º lema de Henkin, se cumple que
existe K´, teoría con chivo expiatorio y extensión de K que tiene una
cantidad numerable de términos cerrados. Por el lema de Lindenbaum, K´
tiene una extensión K’’ completa y consistente con los mismos símbolos
que K´ y, por ende, K’’ también es teoría con chivo expiatorio. Por el 2º
lema de Henkin, K’’ admite un modelo, 𝔄, cuyo dominio es el conjunto de
términos cerrados de K’’. Al ser 𝔄 modelo numerable de K’’, extensión de
K, 𝔄 también modela a K, con lo que se ha probado el primer teorema.
No es difícil revisar que Modus Ponens y Generalización preservan validez
lógica y que los axiomas son lógicamente válidos. De este modo todo
teorema también es fórmula lógicamente válida. Por otro lado si una
fórmula lógicamente válida no fuese teorema, se podría añadir a su
negación como axioma del cálculo de predicados y la teoría resultante
sería consistente, por lo que tendría un modelo. En este modelo se
satisfacerían la fórmula y su negación, lo cual es imposible. Por lo tanto
toda fórmula lógicamente válida es teorema y con esto se demuestra el
teorema de completitud de Gödel.
DESARROLLO DE LAS NOCIONES BÁSICASEl lenguaje formal del Cálculo de Predicados de 1º Orden
estudiado utiliza los siguientes símbolos:
• Símbolos de agrupación: (,),[,]
• Variables: 𝑥1, 𝑥2, 𝑥3, …• Conectivos Lógicos: →,↔,∧,∨, ¬• Cuantificadores: ∀, ∃• Constantes: 𝑐1, 𝑐2, 𝑐3, …• Símbolos Funcionales: 𝑓1
1, 𝑓21, 𝑓3
1, … , 𝑓12, 𝑓2
2, 𝑓32, … , 𝑓1
𝑛, 𝑓2𝑛, …
• Símbolos Predicativos: 𝑃11, 𝑃2
1, 𝑃31, … , 𝑃1
2, 𝑃22, 𝑃3
2, …, 𝑃1𝑛, 𝑃2
𝑛 …
Y se construye de la siguiente forma:
i. Las variables y las constantes son términos.
ii. Un símbolo funcional de n-aridad seguido de “(“, n
términos y “)” es un término: 𝑓𝑘𝑛(𝑡1, 𝑡2, … , 𝑡𝑛).
iii. Un símbolo predicativo de n-aridad seguido de “(“, n
términos y “)” es una fórmula bien formada (wff-well
formed formula) o elemento del lenguaje: 𝑃𝑘𝑛(𝑡1, … , 𝑡𝑛).
iv. Si 𝜑, 𝜓 son wffs y 𝑥 es una variable entonces 𝜑 → 𝜓 ,
𝜑 ↔ 𝜓 , 𝜑 ∧ 𝜓 , 𝜑 ∨ 𝜓 , ¬𝜑, ∀𝑥[𝜑], y ∃𝑥[𝜑] son wffs.
v. Ninguna otra cosa es un término o una wff.
Los axiomas del cálculo de predicados son las wffs que
tengan alguna de las siguientes formas:
1. (𝜑 → 𝜓 → 𝜑 )
2. 𝜑 → 𝜓 → 𝛾 → 𝜑 → 𝜓 → 𝜑 → 𝛾
3. ¬𝜑 → ¬𝜓 → ¬𝜑 → 𝜓 → 𝜑
4. ∀𝑥 𝜑 𝑥 → 𝜑 𝑡/𝑥 donde t es término y x, libre en 𝜑.
5. ∀𝑥 𝜑 → 𝜓 → 𝜑 → ∀𝑥 𝜓 si x no es libre en 𝜑.
x1, x2, x3,...x1, x2, x3,…
Las regla de inferencia son dos:
Modus Ponens: 𝜑, (𝜑 → 𝜓) ⊢ 𝜓Generalización: 𝜑 ⊢ ∀𝑥 𝜑
De manera práctica se dirá que una fórmula del lenguaje es satisfactible si
existe un “mundo” donde lo que enuncia la fórmula es verdadero.
Análogamente se dirá que una fórmula es lógicamente válida si es
verdadera en todos los mundos posibles. Una prueba es una lista finita
generada a partir de los axiomas, usando las reglas de inferencia. A la
última fórmula de cualquier prueba se le denominará teorema y a un
conjunto de teoremas se le llama teoría. Una de éstas es consistente si no
se cumple que una fórmula y su negación son ambos elementos de la
teoría, y es completa si al menos una de las dos es parte de la teoría para
toda posible wff del lenguaje. Si existe un mundo que satisfaga todas las
fórmulas de una teoría, se dirá que éste es modelo de la misma.