1. Relación de Consecuencia en Lógica de Primer Orden

La relación de consecuencia no solo pertenece a la Lógica de Primer Orden, sino que ya en la lógica proposicional previamente vista aparecía como uno de los conceptos más importantes.

Definimos relación de consecuencia como la correspondencia entre un conjunto de fórmulas (representadas por medio del símbolo Γ) y una fórmula concreta (denominada como A). Esto, expresado en lenguaje de símbolos, queda del siguiente modo: Γ⊨A si y solo si para todo M y σ, si M,σ⊨Γ entonces M,σ⊨A.

La definición de relación de consecuencia para la Lógica de Primer Orden cambia un poco respecto de la lógica proposicional. En esta, M y σ son los que deben satisfacer todas las fórmulas que pertenezcan a Γ. Cabe precisar que el símbolo ⊨ es usado tanto para representar el concepto de satisfacción como para representar la propia relación de consecuencia. Estos dos conceptos, pese a estar relacionados, no son equivalentes.

Con lo cual podemos concluir que lo que anteriormente hemos definido como relación de consecuencia, a saber, Γ⊨A si y solo si para todo M y σ, si M,σ⊨Γ entonces M,σ⊨A, puede ser también definido de este modo: Γ⊨A si y solo si no existen M y σ tales que M,σ⊨Γ pero M,σ⊭A.

Además de esto, dos sentencias A y B son equivalentes (A≡B) si son satisfechas exactamente por los mismos modelos. Un ejemplo de esto son las fórmulas ∀xA≡¬∃x¬A.

2. Teorema de Compacidad en Lógica de Primer Orden: Enunciado e Importancia

El teorema de Compacidad dice, a grandes rasgos, que dados cualquier conjunto de fórmulas Γ y cualquier fórmula A, Γ⊨A si y solo si existe un subconjunto finito de Γ (Γ’) tal que Γ’⊨A. El teorema de Compacidad es, realmente, la extensión del teorema semántico de la deducción que se hace para conjuntos infinitos. El teorema semántico de la deducción dice que para cualquier conjunto de fórmulas Γ y para cualesquiera fórmulas A y B, Γ,A⊨B si y solo si Γ⊨A→B.

Lo que el teorema de Compacidad dice es que, si de un conjunto finito Γ podemos sacar una cierta conclusión, entonces no es necesario un conjunto infinito para llegar a alguna otra conclusión, con lo cual, nunca son necesarias infinitas premisas. Podemos formular el teorema de Compacidad también del siguiente modo: todo conjunto de fórmulas finitamente satisfacible es satisfacible, lo cual implica que, suponiendo un conjunto infinito de fórmulas Γ, para cada uno de sus subconjuntos finitos podemos encontrar un modelo y una asignación que satisfagan las fórmulas de Γ’. Esto puede darse, aunque cada modelo y asignación que satisfagan cada subconjunto sean diferentes y aunque ningún modelo y asignación satisfagan más de un subconjunto. Esto es posible ya que el teorema de Compacidad dice que siempre habrá algún modelo y asignación que satisfagan el conjunto Γ completo.

Es importante porque su existencia significa que existen sistemas deductivos correctos y completos, y es la clave para determinar todos los límites de la Lógica de Primer Orden y además permite descubrir y demostrar la existencia de los modelos no estándar.

3. Límites de la Lógica de Primer Orden y el Teorema de Compacidad

Existen ciertas cosas relacionadas con el tamaño de los modelos que nos es imposible expresar en lenguaje de primer orden con identidad. Para demostrar estos límites que posee la capacidad explicativa de la lógica de primer orden es necesario emplear el teorema de compacidad. Estos límites son sentencias que podemos hacer en otros lenguajes como el castellano sin aparente problema, pero que no existe ninguna fórmula posible en el lenguaje de primer orden que pueda ser equivalente.

Algunos de los límites que este lenguaje posee son la expresión mediante una fórmula el de la infinitud (una única sentencia que diga “hay infinitos elementos”), la finitud y la descripción completa del conjunto de los números naturales. El teorema de compacidad tiene especial relevancia en este respecto ya que es por su culpa por lo que existen estos límites, es decir, el lenguaje de primer orden con identidad no puede expresar ninguna de estas tres cosas ya que el teorema de compacidad conduce a una contradicción irresoluble por este lenguaje.

4. Diferencias entre la Lógica de Primer Orden y la Lógica de Segundo Orden

La lógica de segundo orden, realmente, es una extensión de la de primer orden que nace con el objetivo de incrementar la capacidad expresiva de esta. El lenguaje de segundo orden es resultado de añadir al lenguaje de primer orden la posibilidad de cuantificar también sobre propiedades y relaciones (y no solo sobre individuos). Esto permite formular proposiciones del tipo “para toda relación binaria…” o “existe una propiedad que…”, etc. Estas variables predicativas permiten construir fórmulas atómicas de la misma manera que las correspondientes constantes predicativas n-arias. Estas nuevas variables se conocen como variables de segundo orden. De esta manera, en la lógica de segundo orden los cuantificadores de primer orden cuantifican sobre elementos del dominio y los de segundo orden (o monádicos) cuantifican sobre subconjuntos de D.

La semántica de la lógica de segundo orden es similar a la de primer orden, añadiendo el tratamiento adecuado para las nuevas variables que, en todo caso, se maneja de modo muy similar a las variables de primer orden. Los modelos del lenguaje de segundo orden son iguales que los de primer orden: un dominio y la función que interpreta las constantes individuales y los símbolos relacionales (que en la lógica de segundo orden se llaman constantes de predicado y de relación). Las funciones de asignación tendrán ahora que asignar también valores adecuados a las variables predicativas, con lo que una asignación ahora es una función “σ” tal que:

• Para cada variable individual x, σ (x)∈D (igual que antes)
• Para cada variable predicativa n-aria Xⁿ, σ (Xⁿ)⊆Dⁿ

5. Superación de los Límites de la Lógica de Primer Orden por la Lógica de Segundo Orden y la Ausencia de Compacidad

El teorema de compacidad viene derivado del teorema de corrección y del teorema de completud. Debido a que ninguno de estos dos se cumple en la lógica de segundo orden, el teorema de compacidad tampoco lo hace. El problema está en que en la lógica de segundo orden es imposible reducir la relación de consecuencia a un conjunto de reglas de la misma manera que se hace en la lógica proposicional o en la de primer orden. No puede haber, entonces, un sistema deductivo correcto y completo tal que en cada deducción aparezca sólo una cantidad finita de premisas porque con esos se demostraría la compacidad. Con lo que ningún sistema deductivo de la lógica de segundo orden nos puede permitir extraer de un conjunto de premisas todas sus consecuencias.

Esta ausencia de compacidad es la que permite a la lógica de segundo orden ampliar las fronteras de la de primer orden. Esto significa que en la lógica de segundo orden es posible expresar tanto la finitud como la infinitud mediante una sola fórmula. La imposibilidad de hacerlo en la lógica de primer orden se debe a la contradicción que se produce a introducir el teorema de compacidad y la lógica de segundo orden carece de este problema.

6. Posibilidades en la Definición de Modelos Modales de Primer Orden

Existen muchas posibilidades porque:

• El dominio de objetos puede ser el mismo en todos los mundos posibles o no.
• La interpretación de las constantes debe ser la misma en todos los mundos posibles o puede variar de un mundo posible a otro.
• Cuando los dominios son variables, los cuantificadores se refieren en cada mundo posible a los objetos que existen en ese mundo posible. La cuestión ahora es si nos puede interesar admitir que en los mundos posibles se puede hablar de objetos que no existen en ellos, en el sentido de que la interpretación de una constante en un mundo posible pueda ser un objeto que no existen en ese mundo (es decir, que no está en su dominio, aunque si el dominio de algún otro mundo del modelo) y que la interpretación de las propiedades, relaciones, etc. En un mundo puedan incluir igualmente objetos no existentes en él.
• Las variables representan objetos (se dice, por eso, que la cuantificación es objetual) mientras que las constantes (no rígidas) representan diferentes objetos en diferentes mundos posibles, es decir, cierto tipo de intensiones. Intuitivamente, eso representa cierto tipo de conceptos, conceptos individuales. Otra posibilidad que se nos presenta entonces es la de ver que las variables también representen intensiones (o conceptos individuales) en lugar de presentar objetos. En ese caso los cuantificadores ya no se refieren a individuos sino a funciones de mundos a individuos.

7. Origen y Descripción de la Paradoja de Russell

La paradoja de Russell (llamada así porque fue formulada por Bertrand Russell) nace del postulado de la teoría de conjuntos propuesta por Cantor y Frege que dice que toda propiedad ha de poseer un conjunto de elementos que la cumpla. Russell percibe un problema en esta teoría y se centra en la propiedad de»no pertenecer a sí mism» y plantea un conjunto definido por esa propiedad: R={x: x es un conjunto que no pertenece a sí mismo}. Se presentan dos posibilidades:

a) R pertenece a sí mismo b) R no pertenece a sí mismo

Ambas posibilidades son absurdas.

A) Si R pertenece a sí mismo, entonces pertenece a R, pero para hacerlo debe cumplir la condición que define a R: no pertenecer a sí mismo, lo cual es absurdo. B) Si R no pertenece a sí mismo, no pertenece a R porque no cumple la condición para ello, porque pertenece a sí mismo, lo cual también es absurdo.

Esto significa que una teoría que toma como axiomas los principios citados (extensionalidad y comprensión) permite deducir contradicciones. De una contradicción se sigue cualquier cosa, en una teoría así se puede demostrar absolutamente todo, lo que la convierte en inútil.

8. Teoría Axiomática de Conjuntos: Origen, Objetivo y Descripción

La teoría de conjuntos nació entre 1873 y 1897 de la mano de los trabajos de Georg Cantor. En un principio fue rechazada por las grandes eminencias matemáticas de la época, pero finalmente se tomó como una de las partes fundamentales de las matemáticas y base sobre la que estas se pueden seguir construyendo, pero sobre todo como principal acceso al concepto de infinito.

Cuenta con unos conceptos básicos muy intuitivos: un conjunto es una agrupación de cosas que se conocen como sus elementos. Estos elementos no son entidades externas a los conjuntos, sino más bien son a su vez otros conjuntos cuyos elementos son también conjuntos y así sucesivamente. Otro de los conceptos básicos de esta teoría es el de pertenencia, que indica cuando una cosa está contenida en un conjunto. Además de esto existen varias formas de definir un conjunto, por ejemplo, del conjunto V={a,e,i,o,u} podemos decir o bien que está compuesto por las letras a, e, i, o, u o bien que es el conjunto formado por todas las vocales. De esta manera se pueden definir también conjuntos infinitos como ω, el cual está formado por todos los números naturales.

9. Definición de los Números Naturales en la Teoría de Conjuntos

Los primeros intentos de definir los números naturales en la teoría de conjuntos pensaron que podría hacerse definiendo como el número n mediante todos los conjuntos que contengan n elementos, pero esto resulta contradictorio para la teoría axiomática. Con lo cual se llegó a la conclusión de que una correcta manera de hacerlo era representar cada número n por un conjunto que tenga exactamente n elementos. Como el conjunto 0 no posee ningún elemento entonces 0=∅. El conjunto 1 deberá tener un elemento (el cual puede ser el que ya tenemos definido, es decir, el 0) con lo cual 1={0} o 1={∅}. De esta misma forma se define el conjunto 2, formado por los dos elementos ya definidos, o lo que es lo mismo 2={0,1}={∅,{∅}}. Así sucesivamente con el resto de infinitos números naturales. Este proceso de construcción de conjuntos se considera recursivo ya que a partir de algo dado (0=∅) y un proceso que aplicamos una y otra vez obtenemos todos los números. Con lo cual podemos resumir esta definición recursiva de los números naturales en la dada por Von Neumann:

• 0=∅
• n+1=n∪{n}

10. Axioma del Infinito: Enunciado e Importancia

Una vez que ya existe una representación finita de cada número natural, el siguiente paso es lograr formular un conjunto infinito cuyos elementos fueran todos los números naturales. Todos los axiomas que ya pertenecían a la teoría de conjuntos no son suficientes para conseguir expresar un conjunto infinito. Con lo cual es necesario formular un axioma que nos permita por lo menos tener un conjunto infinito mediante el cual construir los demás. De esta manera nace el axioma del infinito.

Este axioma dice, en líneas generales, que existe un conjunto del que son elementos todos los números naturales. Realmente no es necesario especificar si este conjunto es exactamente el conjunto que contiene únicamente todos los números naturales o si además de ellos contiene más cosas ya que gracias al axioma de separación podríamos aislar el conjunto que contenga únicamente los números. Este conjunto suele llamarse w o ℕ. Tanto los números naturales como el propio w tienen la propiedad de ser todos ellos transitivos (los elementos de sus elementos también son elementos suyos).

11. Axioma de Elección: Enunciado, Particularidades e Importancia

El axioma de elección puede formularse de varias formas. En reglas generales lo que dice es que dado cualquier conjunto y cuyos elementos son conjuntos no vacíos, existe siempre una función f tal que para cada x ∈ y f(x) ∈ x, o lo que es lo mismo, f asigna a cada uno de los conjuntos x que están en y uno de sus elementos, elige un elemento de cada uno de esos conjuntos x. Es por esto que se le denomina “de elección”.

Este axioma es especialmente importante porque es equivalente a muchas otras afirmaciones matemáticas importantes y además es necesario para demostrar muchas cosas. Existen muchas equivalencias en cualquier rama matemática, dos de las más conocidas son la del principio de buena ordenación y la del lema de Zorn. La primera dice que todo conjunto tiene un buen orden, es decir, que existe una relación binaria R para todo conjunto x que permite que en cualquier subconjunto que cojamos de un conjunto ordenado hay siempre uno que es menor que los demás. El lema de Zorn lo que dice es, a grandes rasgos, que cuando en un conjunto se dan ciertas circunstancias debe existir un elemento con ciertas propiedades.

12. Ordinales: Definición y Propiedades

Para definir los ordinales es necesario comenzar por los números naturales, cada uno de los cuales es un conjunto transitivo, y además como sus elementos son otros números, es un conjunto transitivo cuyos elementos también son transitivos. Además de esto cada conjunto correspondiente a un número natural es un conjunto bien ordenado. Una vez que teníamos la definición de cada número natural podíamos definir w (el conjunto de todos los números naturales) por medio del axioma del infinito. Este conjunto w (o ℕ) es también un conjunto transitivo bien cuyos elementos son también transitivos.

Por medio de ciertas operaciones (n∪{n}) se puede encontrar el número n+1. De esta misma manera se puede operar con el conjunto w, obteniendo así w+1=w∪{w} o lo que es lo mismo {0,1,2,3…w}, que también es un conjunto transitivo y bien ordenado cuyos elementos son transitivos. Y así podemos continuar hasta el infinito (w2, w3, w², w^w…)

Todos los conjuntos que se obtienen por medio de este proceso repetitivo son los ordinales. A modo de definición más concisa: un ordinal es cualquier conjunto transitivo cuyos elementos son transitivos y que está bien ordenado por ∈. Todo ordinal es un conjunto de todos los demás ordinales anteriores a él y además representan todos los patrones posibles de buen orden.

Además de esta definición de los ordinales existen otros aspectos a tener en cuenta:

• Los ordinales son una generalización transfinita de los números naturales por lo que permiten hacer generalizaciones en base a estos como las definiciones recursivas.
• Existen dos tipos de ordinales (además del 0):
  • Ordinales sucesores: ordinales que suceden a otro inmediatamente anterior
  • Ordinales límite: que son siempre el primero de una secuencia nueva
• No puede existir un conjunto que englobe a todos los ordinales ya que caería en contradicción. Si ese conjunto fuera O, al tener las mismas características que cualquier otro ordinal podría pensarse O+1…
• Siempre, sea cual sea el grupo de ordinales, se cumple la propiedad fundamental de que siempre hay entre ellos uno menor que los demás (un elemento mínimo).

13. Comparación de Tamaños de Conjuntos Infinitos y el Principio de Tricotomía

Existen tres posibilidades a la hora de comparar los tamaños de los conjuntos que son infinitos:

• Si existe una función biyectiva (si cada elemento de Y aparece en la segunda posición de un par exactamente) entre X e Y decimos que X e Y son equipotentes y eso indica que ambos conjuntos son del mismo tamaño, o lo que es lo mismo, que X e Y tienen el mismo cardinal.
• Si no hay una biyección entonces:
  • O bien existe una función inyectiva (si cada elemento de Y aparece en la segunda posición de un par como mucho) de X a Y, entonces X es más pequeño que Y, es decir, el cardinal de X es menor que el de Y.
  • O entonces existe una función suprayectiva (si cada elemento de Y aparece en la segunda posición de un par como mínimo) de X a Y, entonces X es mayor que Y, o sea, el cardinal de X es mayor que el de Y.

Esto nos lleva, dados X e Y, a suponer que estos o son iguales o bien uno es más grande que el otro. Esto es lo mismo que decir que bien existe entre ellos una biyección, una inyección o una suprayección. El principio que afirma esto es el llamado principio de tricotomía. No obstante, para demostrar este principio de tricotomía es necesario emplear el axioma de elección y no solo eso, sino que este principio es una de las muchas equivalencias con las que cuenta este axioma.

14. Cardinales: Definición y Propiedades

Los cardinales son los números infinitos que emplea la teoría de conjuntos para “contar” la cantidad de elementos que tiene un conjunto. En otras palabras, los cardinales son los conjuntos usamos como representantes (o medida) de todos los conjuntos de un cierto tamaño (o sea, de todos los que son equipotentes con él).

Un cardinal no es más que un ordinal que no es equipotente con ninguno de los ordinales anteriores, por lo que son cardinales todos los números naturales y algunos de los ordinales infinitos.

A la pregunta de si los conjuntos que hemos definido como cardinales son suficiente para medir los tamaños de todos los conjuntos la respuesta es sí si empleamos el axioma de elección, sino es imposible demostrarlo.

Cabe mencionar el teorema de Cantor, el cual dice que dado cualquier conjunto X su conjunto potencia P(X) siempre cuenta con un cardinal mayor que el de X.

15. Teorema de Cantor: Enunciado e Importancia en la Teoría de Conjuntos

El Teorema de Cantor dice, a grandes rasgos, que el conjunto potencia de cualquier conjunto es mayor que este.

Axiomáticamente todo conjunto posee un conjunto potencia correspondiente no sólo se da un conjunto potencia de un conjunto normal, sino que de este conjunto potencia existe también otro conjunto potencia mayor que él y de este otro conjunto potencia mayor que él y así sucesiva e infinitamente. Esto es lo que da lugar al universo conjuntista, por esto es esencial el teorema de Cantor para la teoría de conjuntos.

16. Conjuntos Enumerables: Definición y Ejemplos

Un conjunto es enumerable cuando es del mismo tamaño que w, es decir, cuando sus elementos pueden emparejarse con los números naturales.

De los conjuntos propuestos:

• El conjunto de los números pares sí es enumerable porque al ser este un conjunto de los números naturales puede realizarse una biyección.
• El conjunto de los números primos sí es enumerable porque al ser este un subconjunto de los naturales es posible realizar una función biyectiva entre ambos.
• El conjunto de los números enteros sí es enumerable porque como incluye el conjunto de los números naturales es posible realizar una biyección entre ambos.
• El conjunto de los números racionales sí es enumerable porque como el conjunto de los números racionales incluye (entre otros) el conjunto de los números naturales es posible realizar una biyección entre ambos.
• El conjunto de los números reales no es enumerable porque hay más conjuntos de números reales que de números naturales.