Lógica de predicados · Definición

Orden de cuantificadores

lógicapredicados

Antes de empezar necesitas conocer

El orden de los cuantificadores cambia el significado de una fórmula. Aquí veremos por qué \(\forall x\,\exists y\,P(x,y)\) y \(\exists y\,\forall x\,P(x,y)\) no son lo mismo.

Definición

Para un predicado \(P(x,y)\), el orden de los cuantificadores puede cambiar el valor de verdad de una fórmula.

\[\begin{gathered}\forall x\,\exists y\,P(x,y)\\\not\equiv\exists y\,\forall x\,P(x,y)\end{gathered}\]

Cuando aparecen varios cuantificadores, su orden puede cambiar el significado de la fórmula. En general, \(\forall x\,\exists y\,P(x,y)\) no equivale a \(\exists y\,\forall x\,P(x,y)\).

La primera fórmula permite que el testigo y dependa del x elegido. La segunda exige un mismo y que funcione para todos los x.

Leer el orden como una secuencia de compromisos ayuda a evitar una confusión frecuente: tener un objeto para cada caso no implica tener un único objeto para todos.

Para pensar

¿Qué diferencia hay entre un testigo dependiente y uno global?

El dependiente puede cambiar con x; el global debe servir para todos los x a la vez.

Ejercicios 10

  1. En general, cambiar el orden de ∀ y ∃...
  2. ∀x ∃y P(x,y) permite que...
  3. ∃y ∀x P(x,y) afirma que...
  4. ¿Cuál par no es equivalente en general?
  5. El orden de cuantificadores importa especialmente cuando...
  6. En general, ∀x∃y R(x,y) y ∃y∀x R(x,y)...
  7. ∀x∃y R(x,y) permite que...
  8. ∃y∀x R(x,y) afirma que...
  9. Selecciona afirmaciones verdaderas sobre el orden.
  10. Si cada estudiante tiene algún libro, no se sigue que...

Referencias

  • Frederic P. Schuller, Lectures on the Geometrical Anatomy of Theoretical Physics · Lecture 1, Introduction / Logic of Propositions and Predicates, YouTube, 2015.