Download Lógicas de Orden Superior

Lógicas para la Informática y la
Inteligencia Artificial
Lógicas de Orden Superior
Universidad de Salamanca
Departamento de Informática y Automática.
Ingeniería Superior Informática.
César Barrado Fernández
76128018-L
2
ÍNDICE:
1.- INTRODUCCIÓN ...................................................................................................... 5
2.- LÓGICA Y TEORÍA DE CONJUNTOS ................................................................... 5
3.- SEMÁNTICA ESTÁNDAR PARA SOL ................................................................... 7
4.- INCOMPLETUD DE LA LÓGICA DE SEGUNDO ORDEN .................................. 8
5.- COMPLETUD DE SOL CON SEMÁNTICA GENERAL ........................................ 9
6.- CONCLUSIÓN ........................................................................................................... 9
3
4
1.- INTRODUCCIÓN
La lógica de segundo orden es una extensión de la lógica de primer orden y para
poder hablar sobre ella será necesario comentar primero aquello en lo que se sustenta, la
teoría de conjuntos.
2.- LÓGICA Y TEORÍA DE CONJUNTOS
En un principio, la noción de clase pertenecía a la lógica, pero con la aparición de
la teoría de conjuntos de Cantor ésta tuvo que replantearse ciertos conceptos como el de
conjunto o el de clase, así como distinguir entre otros como la sintaxis y la semántica, el
lenguaje y el metalenguaje, niveles de cuantificación y por lo tanto, lógicas de primer y
segundo orden.
Existen dos maneras de fundamentar una teoría matemática. La primera es definir
sus conceptos empleando los de otra disciplina ya fundamentada y la segunda es
considerar que los conceptos básicos son primitivos y por lo tanto no se definen, por lo
que los teoremas se derivarán de estos conceptos básicos. Esta última fue la que
finalmente se impuso aunque en ambos casos existieron problemas con la elección del
lenguaje lógico o la incapacidad de caracterizar categóricamente a ninguna teoría que
posea modelos infinitos. Otros problemas pudieron solucionarse introduciendo algunas
distinciones, como la que existe entre la sintaxis y la semántica, o entre lógica de primer
orden y lógicas de orden superior.
Para fundamentar esta teoría de conjuntos es necesario definir dos conceptos
básicos, clase y conjunto.
Para Cantor, un conjunto es “cualquier colección de objetos bien determinados y
distintos que sin contradicción pueda ser tomada como una unidad, reuniendo los
objetos en un todo”. Esta definición posibilita que existan colecciones que no pueden
considerarse completas sin generar inconsistencias, las denominadas colecciones
absolutamente infinitas.
5
Sin embargo, para von Neumann todos los conjuntos son clases y con ellos se
generarán nuevos conjuntos y clases, pero hay algunas clases que no podrán ser
miembros de ningún conjunto: las clases últimas.
Tomando la definición de conjunto de Cantor aparece el problema de las paradojas
de la teoría de conjuntos. Esto imposibilitaría fundamentar sobre la lógica la teoría de
conjuntos, ya que es imprescindible para ello que la primera no tenga contradicciones.
Para erradicar las paradojas en la teoría de conjuntos se propusieron varias
soluciones, como por ejemplo la axiomática. También Russell, con la teoría de tipos que
impide que se reproduzcan porque el propio lenguaje impide su formulación, consiguió
erradicarlas.
Las paradojas podrían clasificarse en dos grandes grupos: paradojas lógicas o
matemáticas y paradojas semánticas o epistemológicas.
Para evitar las paradojas del primer grupo utilizamos conceptos como el de
cardinalidad, clase o número, mientras que para evitar las del segundo grupo es
necesario realizar una distinción entre el lenguaje y el metalenguaje, utilizando
conceptos como el de verdad o definibilidad en el lenguaje objeto.
Como paradojas matemáticas más conocidas se pueden destacar la de Russell
sobre la definición de clase y la de Cantor sobre la cardinalidad de la clase universal.
Como paradojas semánticas más conocidas podemos destacar la del mentiroso de
Epiménides sobre la definición de verdad en el lenguaje objeto y la de Richard sobre la
cardinalidad de los números reales.
Como se ha comentado anteriormente, la teoría de tipos evita que se produzcan las
paradojas en la teoría intuitiva de conjuntos, aunque su existencia no se debe
únicamente a ello, sino que además proporciona una fundamentación simple y
razonablemente segura para la mayor parte de las matemáticas clásicas.
Esta teoría de tipos simple se estructura jerárquicamente y se utiliza para evitar las
paradojas lógicas o matemáticas, pero para eludir las paradojas semánticas es necesario
emplear la teoría ramificada de tipos, o la distinción entre lenguaje y metalenguaje.
Como soporte de este metalenguaje se seguirá usando la teoría de conjuntos.
6
Volviendo a los ejemplos de paradojas antes mencionados, la teoría de tipos
simple evita la paradoja lógica de Russell en la que U={X | X ∉ X}, ya que X ∉ X no
es una sucesión de símbolos válida y el axioma de definición de clases no se aplica para
ella, eliminando así la paradoja. En cuanto a la paradoja de Cantor, no puede
reproducirse en teoría de tipos ya que un conjunto y el de sus partes están en tipos
distintos. En las paradojas semánticas y aplicando la teoría de tipos finitos, al hacer una
distinción entre lenguaje y metalenguaje, las fórmulas paradójicas no podrían pertenecer
nunca al lenguaje objeto y por lo tanto no podrían darse en las fórmulas de la teoría, así
como no podrían darse tampoco ni la autorreferencia ni la reflexividad.
Estas paradojas podrían evitarse también utilizando la teoría axiomática de
conjuntos, aunque es menos intuitiva ya que tanto los conjuntos como la teoría de tipos
tienen una construcción jerárquica.
La idea intuitiva más extendida nos dice que el universo matemático constituye
una jerarquía de conjuntos, la jerarquía de Zermelo. Esta jerarquía será utilizada como
sustrato para definir la semántica de las fórmulas lógicas, por lo que los axiomas de la
teoría de conjuntos se convierten en la justificación formal de las demostraciones que se
realizan en el metalenguaje. Tomaremos por lo tanto la teoría axiomática de ZermeloFraenkel como fundamentación matemática de las pruebas que realizamos en el
metalenguaje, y utilizaremos por ello como parte del metalenguaje de la lógica de orden
superior el lenguaje de primer orden L∈, cuyas fórmulas serán consideradas como
abreviaturas de las expresiones correspondientes en castellano.
3.- SEMÁNTICA ESTÁNDAR PARA SOL
A diferencia de la lógica de primer orden, la lógica de segundo orden posee
variables relacionales además de las individuales, y ambas pueden cuantificarse.
Podemos por tanto utilizar expresiones como “para toda propiedad se verifica ϕ” o
“para todas las relaciones binarias se cumple ϕ” que no están permitidas en la lógica de
primer orden.
7
Es por ello que deberemos considerar unas nuevas variables relacionales binarias
que tomarán su valor del conjunto de las partes del producto cartesiano que se esté
considerando. Así, en la semántica estándar y para un modelo cuyo universo de
individuos sea A, el universo de conjuntos será ℘(A) y el de relaciones binarias ℘(A2).
Se dice que A es estándar si A = 〈 A, 〈An〉 n≥1 , 〈CA〉 C ∈ OPER.CONS 〉 donde:
-
A ≠ ∅ es el conjunto no vacío como universo de individuos.
-
An = ℘(A) el conjunto de todas las relaciones n-arias como universo de
relaciones n-arias.
-
Si C:=R es un relator n-ario, entonces RA ⊆ A x … x A es una relación sobre
A, y si C:=f es un functor n-ario, entonces fA: A x … x A → A es una
función sobre A.
Al adoptar la semántica estándar para la lógica de segundo orden tomamos la
teoría de conjuntos como metalenguaje.
La lógica de segundo orden tiene un gran poder expresivo debido a la
cuantificación sobre todos los conjuntos y relaciones del dominio de individuos. Por
ello conceptos que en lógica de primer orden son primitivos (se toman directamente de
la metateoría) en la lógica de segundo orden pueden introducirse por definición.
Sin embargo, el poder expresivo de la lógica de segundo orden puede resultar
excesivo, debido a que la validez de ciertas fórmulas de segundo orden no puede
establecerse ni refutarse en la teoría de conjuntos, y un lenguaje que pueda expresar más
de lo que la teoría de conjuntos pueda decidir no es estable, y no se puede encontrar un
cálculo deductivo completo para la lógica asociada a dicha semántica.
4.- INCOMPLETUD DE LA LÓGICA DE SEGUNDO
ORDEN
Sabemos, por lo tanto, que en la lógica de segundo orden y utilizando semántica
estándar no existe ningún cálculo correcto y completo, ya que no pueden tenerse a la
vez un gran poder expresivo y buenas propiedades lógicas.
8
Sin embargo, podemos razonar que la incompletud de lógica de segundo orden
con semántica estándar no tiene que ver con la naturaleza del razonamiento de segundo
orden, sino con el modo en el que ha sido construido el modelo de razonamiento de
segundo orden en esta semántica, ligando la metateoría de conjuntos de ZFC a la
semántica de segundo orden. Por lo tanto podremos hacer que la lógica de segundo
orden sea una lógica completa modificando la semántica.
5.- COMPLETUD DE SOL CON SEMÁNTICA
GENERAL
Para que el cálculo para la lógica de segundo orden sea correcto, necesitamos la
semántica de modelos generales en la que los universos de la estructura deben estar
cerrados bajo definibilidad.
Cambiando la semántica de modelos estándar por la de modelos generales hemos
cambiado la lógica, ya que el conjunto de fórmulas válidas no es el mismo. No obstante,
la nueva semántica es más natural y razonable que la estándar porque tomamos como
conjunto de elementos de A a los que son definibles en A. El resultado es que en la
lógica de segundo orden estándar la balanza se inclina del lado del poder expresivo, en
detrimento de las cualidades lógicas mientras que en la no-estándar la balanza se
equilibra.
6.- CONCLUSIÓN
Para finalizar este comentario se podría concluir que, siempre que se pueda, se
debería usar una lógica de primer orden, ya que sus propiedades lógicas son mejores.
Sin embargo, cuando la capacidad expresiva de ésta sea insuficiente, se podrá recurrir a
la lógica de segundo orden, que ofrecerá un mayor abanico de posibilidades, a costa de
unas peores propiedades lógicas.
9
10