Ограниченный квантор - Bounded quantifier

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

Примеры ограниченных кванторов в контексте реального анализа включают "∀Икс>0", "∃y<0 "и" ∀Икс ∊ ℝ ". Неофициально" ∀Икс> 0 "говорит" для всех Икс где Икс больше 0 "," ∃y<0 "говорит" существует y где y меньше 0 "и" ∀Икс ∊ ℝ "говорит" за всех Икс где Икс является действительным числом ". Например, "∀Икс>0 ∃y<0 (Икс = y²)" говорит, что «каждое положительное число - это квадрат отрицательного числа».

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

Предположим, что L это язык Арифметика Пеано (язык арифметика второго порядка или арифметика для всех конечных типов тоже будет работать). Есть два типа ограниченных кванторов: ${displaystyle forall n$ и ${displaystyle существует n$Эти кванторы связывают числовую переменную. п и содержать числовой термин т который может не упоминать п но у которых могут быть другие свободные переменные. («Числовые термины» здесь означают такие термины, как «1 + 1», «2», «2 × 3», «м + 3 "и т. Д.)

Эти кванторы определяются следующими правилами (${displaystyle phi}$ обозначает формулы):

${displaystyle существует n$

${displaystyle forall n$

У этих количественных показателей есть несколько причин.

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

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

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

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

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

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

${displaystyle exists xin t (phi) Leftrightarrow exists x (xin tland phi)}$

${displaystyle forall xin t (phi) Leftrightarrow forall x (xin tightarrow phi)}$

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

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

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

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

использованная литература

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