Ограниченный квантификатор

Логическая квантификация, охватывающая подмножество вселенной дискурса

При изучении формальных теорий в математической логике ограниченные квантификаторы (они же ограниченные квантификаторы ) часто включаются в формальный язык в дополнение к стандартным квантификаторам «∀» и «∃». Ограниченные квантификаторы отличаются от «∀» и «∃» тем, что ограниченные квантификаторы ограничивают диапазон квантифицированной переменной. Изучение ограниченных квантификаторов мотивировано тем фактом, что определение того, является ли предложение только с ограниченными квантификаторами истинным, часто не так сложно, как определение того, является ли произвольное предложение истинным.

Примеры

Примеры ограниченных квантификаторов в контексте реального анализа включают в себя:

• ${\displaystyle \forall x>0}$- для всех x , где x больше 0
• ${\displaystyle \exists y<0}$- существует y , где y меньше 0
• ${\displaystyle \forall x\in \mathbb {R} }$- для всех x, где x — действительное число
• ${\displaystyle \forall x>0\quad \exists y<0\quad (x=y^{2})}$- каждое положительное число является квадратом отрицательного числа

Ограниченные квантификаторы в арифметике

Предположим, что L — язык арифметики Пеано (язык арифметики второго порядка или арифметики во всех конечных типах также подойдет). Существует два типа ограниченных квантификаторов: и . Эти квантификаторы связывают числовую переменную n с помощью числового терма t, не содержащего n, но который может иметь другие свободные переменные. («Числовые термы» здесь означают такие термы, как «1 + 1», «2», «2 × 3», « m + 3» и т. д.) ${\displaystyle \forall n<t}$ ${\displaystyle \exists n<t}$

Эти квантификаторы определяются следующими правилами ( обозначает формулы): ${\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 )}$

Существует несколько мотивов для использования этих квантификаторов.

• В приложениях языка к теории рекурсии , например, к арифметической иерархии , ограниченные квантификаторы не добавляют сложности. Если — разрешимый предикат, то и также разрешимы. ${\displaystyle \phi }$ ${\displaystyle \exists n<t\,\phi }$ ${\displaystyle \forall n<t\,\phi }$
• В приложениях к изучению арифметики Пеано тот факт, что определенное множество может быть определено только с ограниченными кванторами, может иметь последствия для вычислимости множества. Например, существует определение простоты, использующее только ограниченные кванторы: число n является простым тогда и только тогда, когда нет двух чисел, строго меньших n , произведение которых равно n . Однако в языке нет определения простоты без кванторов . Тот факт, что существует формула с ограниченными кванторами, определяющая простоту, показывает, что простота каждого числа может быть вычислимо определена. ${\displaystyle \langle 0,1,+,\times ,<,=\rangle }$

В общем случае отношение на натуральных числах определяется ограниченной формулой тогда и только тогда, когда оно вычислимо в иерархии линейного времени, которая определяется аналогично полиномиальной иерархии , но с линейными временными ограничениями вместо полиномиальных. Следовательно, все предикаты, определяемые ограниченной формулой, являются элементарными по Кальмару , контекстно-зависимыми и примитивно рекурсивными .

В арифметической иерархии арифметическая формула, содержащая только ограниченные квантификаторы, называется , , и . Верхний индекс 0 иногда опускается. ${\displaystyle \Sigma _{0}^{0}}$ ${\displaystyle \Delta _{0}^{0}}$ ${\displaystyle \Pi _{0}^{0}}$

Ограниченные кванторы в теории множеств

Предположим, что L — это язык теории множеств Цермело–Френкеля , где многоточие может быть заменено операциями формирования термов, такими как символ для операции powerset . Существуют два ограниченных квантификатора: и . Эти квантификаторы связывают переменную множества x и содержат термин t, который может не упоминать x, но который может иметь другие свободные переменные. ${\displaystyle \langle \in ,\ldots ,=\rangle }$ ${\displaystyle \forall x\in t}$ ${\displaystyle \exists x\in t}$

Семантика этих квантификаторов определяется следующими правилами:

${\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 )}$

Формула ZF, которая содержит только ограниченные квантификаторы, называется , , и . Это составляет основу иерархии Леви , которая определяется аналогично арифметической иерархии. ${\displaystyle \Sigma _{0}}$ ${\displaystyle \Delta _{0}}$ ${\displaystyle \Pi _{0}}$

Ограниченные квантификаторы важны в теории множеств Крипке–Платека и конструктивной теории множеств , где включено только разделение Δ 0. То есть, оно включает разделение для формул только с ограниченными квантификаторами, но не разделение для других формул. В КП мотивацией является тот факт, что удовлетворяет ли множество x формуле ограниченного квантификатора, зависит только от набора множеств, которые близки по рангу к x (поскольку операция powerset может быть применена только конечное число раз для формирования терма). В конструктивной теории множеств это мотивируется предикативными основаниями.

Смотрите также

• Подтипирование — ограниченная квантификация в теории типов
• Система F _<: — полиморфное типизированное лямбда-исчисление с ограниченной квантификацией

Ссылки

• Хинман, П. (2005). Основы математической логики . AK Peters. ISBN 1-56881-262-0.
• Кунен, К. (1980). Теория множеств: Введение в доказательства независимости . Elsevier. ISBN 0-444-86839-9.