Lógica de primer orden

El lenguaje de primer orden

La mayoría de los enunciados matemáticos que nos encontraremos a lo largo de la carrera no son tan simples como para ser escritos en términos de lógica de proposiciones. Estos enunciados tienden ser de la forma “para toda \(x\) existe \(y\) …”. La cuantificación universal y existencial no puede ser capturada con proposiciones. Así, hay que extender el lenguaje para capturar estos enunciados.

De nuevo, como en proposiciones, una fórmula de primer orden será una expresión que pueda ser juzgada de verdadera o falsa. Así, empezaremos con las expresiones más simples y luego formaremos otras más complejas usando conectivos y cuantificadores.

Un comentario antes de la definición es que el lenguaje de primer orden nos permite hablar de elementos y propiedades de una estructura. Por ejemplo, en \(\langle\mathbb{Z},+,\cdot,0,1,\leq\rangle\) podemos hablar de los elementos que son parte de la estructura, los que están dentro de los paréntesis triangulares, estos son \(0\) y \(1\). Además, podremos hablar de elementos de manera “indirecta”, como \(2x+1\). Cuando \(x=5\), la expresión \(2x+1\) se vuelve \(11\) o cuando \(x=-2\), la expresión es \(-3\). También es posible hablar de relaciones, como \(1+1=2\) o \(3x-5\leq x^2 +1\).

Las expresiones, como \(2x+1\), que se vuelven elementos de una estructura se llaman términos. La definición formal de término se puede consultar en (Mendelson, 2015) o en (Enderton, 2021), para nosotros lo importante es que es una forma (sintáctica) de hablar de elementos de una estructura.

Definición

Las fórmulas de primer orden son el menor conjunto que contiene a:

1. Igualdades de términos, \(t_1 = t_2\),
2. Relaciones aplicadas a términos, \(r(t_1, t_2)\) o \(R(t_1,\dots,t_n)\),
3. Si \(\alpha\) y \(\beta\) son fórmulas, entonces las siguientes también lo son
   • \(\neg\alpha\),
   • \(\alpha\land\beta\), \(\alpha\lor\beta\), \(\alpha\to\beta\) y \(\alpha\leftrightarrow\beta\),
   • \(\forall x\;\alpha\) y \(\exists x\;\alpha\).

La satisfacción de fórmulas de primer orden, en una estructura dada, no tiene un algoritmo que nos permita verificar si eso sucede o no. Contrario a las tablas de verdad para la lógica de proposiciones. Así, no profundizaremos más en este lenguaje y cómo tratarlo.

Formalizando enunciados

En este momento, lo importante es que las fórmulas de primer orden nos permiten escribir enunciados matemáticos en un lenguaje más formal y preciso. Algunos enunciados conocidos que se pueden escribir en este lenguaje son:

---

Enunciado	Fórmula de primer orden
Todo número real tiene un inverso multiplicativo	\(\forall x\in\mathbb{R}\;\exists y\in\mathbb{R}\; (x\cdot y = 1)\)
Todo número real es mayor que cero o igual a cero o menor que cero	\(\forall x\in\mathbb{R}\; (x>0\lor x=0\lor x<0)\)
Todo número real tiene un cuadrado	\(\forall x\in\mathbb{R}\;\exists y\in\mathbb{R}\; (y * y = x)\)
La suma de dos números reales es conmutativa	\(\forall x,y\in\mathbb{R}\; (x+y = y+x)\)
La suma de dos números reales es asociativa	\(\forall x,y,z\in\mathbb{R}\; (x+(y+z) = (x+y)+z)\)
\(0\) es el elemento neutro de la suma	\(\forall x\in\mathbb{R}\;( x+0 = x)\)
El producto distribuye sobre la suma	\(\forall x,y,z\in\mathbb{R}\; (x\cdot(y+z) = x\cdot y + x\cdot z)\)

---

Aunque estos enunciados fueron escritos haciendo referencia a los números reales, es posible enunciarlos para cualquier estructura matemática que tenga suma, producto, cero, uno y orden. Por ejemplo, en los números naturales. En los naturales y los enteros es común hablar de número pares o impares. Sabemos que un número es par si es divisible entre dos, o bien, si es un múltiplo de dos. Así, una fórmula de primer orden que dice “\(n\) es par” es \(\exists k\in\mathbb{N}\;(n=2k)\).

Ahora, una observación importante es que en las fórmulas de la tabla anterior todas las variables están bajo “el alcance” de los cuantificadores, mientras que en la fórmula pra decir que un número es par, la variable \(n\) no está bajo el alcance de ningún cuantificador. En este caso, la variable \(n\) se llama variable libre y la fórmula dice algo acerca de ella.

Un ejemplo para ver cómo cambia el significado de una fórmula al cuantificar variables es el siguiente. Consideremos las fórmulas

\[\begin{align} & \exists y\;(x\cdot y=1), \label{eq:xinv} \\ & \forall x\;\exists y\;(x\cdot y=1). \label{eq:inv} \end{align}\]

La fórmula \eqref{eq:xinv} dice que \(x\) tiene un inverso multiplicativo. Por ejemplo, en \(\mathbb{Z}\) es cierta si interpretamos a \(x\) como \(1\) o \(-1\), pero falsa si la interpretamos como cualquier otro número. Por otro lado, la fórmula \eqref{eq:inv} dice que todo número tiene un inverso multiplicativo. En \(\mathbb{Z}\) es falsa, pero en \(\mathbb{Q}\) es cierta.

Cómo demostrar enunciados con cuantificadores

Generalmente las cosas que nos pedirán demostrar serán enunciados con cuantificadores. Así, saber cómo demostrarlos es importante. Si queremos demostrar un enunciado de la forma \(\forall x\;\varphi(x)\), en alguna estructura \(A\), lo que debemos hacer es tomar un elemento arbitrario de \(A\), digamos \(a\), y demostrar que \(\varphi(a)\) es verdadero. Si queremos demostrar un enunciado de la forma \(\exists x\;\varphi(x)\), lo que debemos hacer es encontrar un elemento de \(A\), digamos \(a\), tal que \(\varphi(a)\) es verdadero.

En general, la demostración de un universal o un existencial es tan simple como el método del párrafo anterior. Sin embargo, cuando se esta trabajando en alguna estructura particular, seguramente habrá que usar propiedades de la estructura. Por ejemplo, un método para demostrar un universal en los números naturales es inducción. También es común demostrar existenciales por contradicción, es decir, suponer que no existe un objeto con la propiedad que queremos y llegar a una contradicción.

Algo que va un poco más en la dirección de tener alternativas para demostrar enunciados con cuantificadores es tratar de ver cómo se compartan los cuantificadores con los conectivos. El comportamiento con la negación seguramente será el más recurrente. En este archivo se escribirán equivalencias e implicaciones con cuantificadores y la demostración de su validez en L∃∀N.