Cuantificador acotado

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

En el estudio de teorías formales en lógica matemática , los cuantificadores acotados (también conocidos como cuantificadores restringidos ) a menudo se incluyen 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 que sólo tiene cuantificadores acotados es verdadera a menudo no es tan difícil como determinar si una oración arbitraria es verdadera.

Ejemplos

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

• ${\displaystyle \forall x>0}$- para todo 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 y contienen un término numérico t que puede no mencionar 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 aplicaciones del lenguaje a la teoría de la recursividad , 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 sólo con cuantificadores acotados puede tener consecuencias para la computabilidad del conjunto. Por ejemplo, existe una definición de primalidad que utiliza sólo cuantificadores acotados: un número n es primo si y sólo si no hay dos números estrictamente menores que n cuyo producto sea n . Sin embargo, no existe en el lenguaje una definición de primalidad libre de cuantificadores . El hecho de que exista una fórmula cuantificadora acotada que defina la primalidad muestra que la primalidad de cada número se puede decidir de forma computable. ${\displaystyle \langle 0,1,+,\times ,<,=\rangle }$

En general, una relación entre números naturales se puede definir mediante una fórmula acotada si y sólo 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 polinomios. 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 sólo cuantificadores acotados se llama , y . A veces se omite el superíndice 0. ${\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 las elipsis pueden reemplazarse por operaciones de formación de términos, como un símbolo para la operación de conjunto de potencias . Hay dos cuantificadores acotados: y . Estos cuantificadores vinculan la variable establecida 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 sólo 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 en la teoría de conjuntos constructivos , donde solo se incluye la separación Δ _{0 .} Es decir, incluye la separación de fórmulas que sólo tienen cuantificadores acotados, pero no la separación de otras fórmulas. En KP, la motivación es el hecho de que si un conjunto x satisface una fórmula cuantificadora acotada solo depende de la colección de conjuntos que tienen un rango cercano a x (ya que la operación de conjunto de potencias solo se puede aplicar un número finito de veces para formar un término). En la teoría constructiva de conjuntos, está motivado por motivos predicativos .

Ver también

• Subtipificación : cuantificación limitada en teoría de tipos
• Sistema F _<: - un cálculo lambda tipado polimórfico con cuantificación limitada

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.