Cuantificador acotado

Cuantificación lógica que abarca un subconjunto del universo del discurso.

En el estudio de las teorías formales en lógica matemática , los cuantificadores acotados (también conocidos como cuantificadores restringidos ) se incluyen a menudo en un lenguaje formal además de los cuantificadores estándar "∀" y "∃". Los cuantificadores acotados se diferencian de "∀" y "∃" en que los cuantificadores acotados restringen el rango de la variable cuantificada. El estudio de los cuantificadores acotados está motivado por el hecho de que determinar si una oración con solo cuantificadores acotados es verdadera a menudo no es tan difícil como determinar si una oración arbitraria es verdadera.

Ejemplos

Algunos ejemplos de cuantificadores acotados en el contexto del análisis real incluyen:

• ${\displaystyle \forall x>0}$- para todos los x donde x es mayor que 0
• ${\displaystyle \exists y<0}$- existe una y donde y es menor que 0
• ${\displaystyle \forall x\in \mathbb {R} }$- para todo x donde x es un número real
• ${\displaystyle \forall x>0\quad \exists y<0\quad (x=y^{2})}$- todo número positivo es el cuadrado de un número negativo

Cuantificadores acotados en aritmética

Supongamos que L es el lenguaje de la aritmética de Peano (el lenguaje de la aritmética de segundo orden o la aritmética en todos los tipos finitos también funcionaría). Hay dos tipos de cuantificadores acotados: y . Estos cuantificadores vinculan la variable numérica n utilizando un término numérico t que no contiene n pero que puede tener otras variables libres. ("Términos numéricos" aquí significa términos como "1 + 1", "2", "2 × 3", " m + 3", etc.) ${\displaystyle \forall n<t}$ ${\displaystyle \exists n<t}$

Estos cuantificadores se definen mediante las siguientes reglas ( denota fórmulas): ${\displaystyle \phi }$

${\displaystyle \exists n<t\,\phi \Leftrightarrow \exists n(n<t\land \phi )}$

${\displaystyle \forall n<t\,\phi \Leftrightarrow \forall n(n<t\rightarrow \phi )}$

Hay varias motivaciones para estos cuantificadores.

• En las aplicaciones del lenguaje a la teoría de la recursión , como la jerarquía aritmética , los cuantificadores acotados no añaden complejidad. Si es un predicado decidible , entonces y también lo son. ${\displaystyle \phi }$ ${\displaystyle \exists n<t\,\phi }$ ${\displaystyle \forall n<t\,\phi }$
• En aplicaciones al estudio de la aritmética de Peano , el hecho de que un conjunto particular pueda definirse únicamente con cuantificadores acotados puede tener consecuencias para la computabilidad del conjunto. Por ejemplo, existe una definición de primalidad que utiliza únicamente cuantificadores acotados: un número n es primo si y solo si no hay dos números estrictamente menores que n cuyo producto sea n . Sin embargo, no existe una definición de primalidad libre de cuantificadores en el lenguaje . El hecho de que exista una fórmula de cuantificador acotado que defina la primalidad muestra que la primalidad de cada número puede decidirse computacionalmente. ${\displaystyle \langle 0,1,+,\times ,<,=\rangle }$

En general, una relación sobre números naturales se puede definir mediante una fórmula acotada si y solo si es computable en la jerarquía de tiempo lineal, que se define de manera similar a la jerarquía polinómica , pero con límites de tiempo lineales en lugar de polinómicos. En consecuencia, todos los predicados definibles mediante una fórmula acotada son elementales de Kalmár , sensibles al contexto y recursivos primitivos .

En la jerarquía aritmética , una fórmula aritmética que contiene solo cuantificadores acotados se denomina , , y . El superíndice 0 a veces se omite. ${\displaystyle \Sigma _{0}^{0}}$ ${\displaystyle \Delta _{0}^{0}}$ ${\displaystyle \Pi _{0}^{0}}$

Cuantificadores acotados en la teoría de conjuntos

Supongamos que L es el lenguaje de la teoría de conjuntos de Zermelo-Fraenkel , donde la elipsis puede reemplazarse por operaciones de formación de términos, como un símbolo para la operación de conjunto potencia . Hay dos cuantificadores acotados: y . Estos cuantificadores vinculan la variable de conjunto x y contienen un término t que puede no mencionar x pero que puede tener otras variables libres. ${\displaystyle \langle \in ,\ldots ,=\rangle }$ ${\displaystyle \forall x\in t}$ ${\displaystyle \exists x\in t}$

La semántica de estos cuantificadores está determinada por las siguientes reglas:

${\displaystyle \exists x\in t\ (\phi )\Leftrightarrow \exists x(x\in t\land \phi )}$

${\displaystyle \forall x\in t\ (\phi )\Leftrightarrow \forall x(x\in t\rightarrow \phi )}$

Una fórmula ZF que contiene solo cuantificadores acotados se denomina , , y . Esto forma la base de la jerarquía de Lévy , que se define de manera análoga a la jerarquía aritmética. ${\displaystyle \Sigma _{0}}$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \Pi _{0}}$

Los cuantificadores acotados son importantes en la teoría de conjuntos de Kripke-Platek y la teoría de conjuntos constructivos , donde solo se incluye la separación Δ 0. Es decir, incluye la separación para fórmulas con solo cuantificadores acotados, pero no la separación para otras fórmulas. En KP, la motivación es el hecho de que si un conjunto x satisface una fórmula de cuantificador acotado solo depende de la colección de conjuntos que son cercanos en rango a x (ya que la operación de conjunto potencia solo se puede aplicar un número finito de veces para formar un término). En la teoría de conjuntos constructivos, está motivada por motivos predicativos .

Véase también

• Subtipificación : cuantificación acotada en la teoría de tipos
• Sistema F _<: — un cálculo lambda tipificado polimórfico con cuantificación acotada

Referencias

• Hinman, P. (2005). Fundamentos de lógica matemática . AK Peters. ISBN 1-56881-262-0.
• Kunen, K. (1980). Teoría de conjuntos: una introducción a las pruebas de independencia . Elsevier. ISBN 0-444-86839-9.