Универсальная количественная оценка - Википедия - Universal quantification

В логика предикатов, а универсальная количественная оценка это тип квантификатор, а логическая константа который интерпретированный как «дано любому» или «для всех». Он заявляет, что пропозициональная функция возможно довольный каждым член из область дискурса. Другими словами, это предикация из свойство или же связь каждому члену домена. Это утверждает что предикат внутри объем универсального квантора верно для каждого ценить из переменная предиката.

Обычно обозначается повернулся (∀) логический оператор символ, который при использовании вместе с переменной-предикатом называется универсальный квантор (" $\forall Икс$ ", " $\forall(Икс)$ ", а иногда и" ${ Displaystyle (х)}$ "только). Универсальная количественная оценка отличается от экзистенциальный количественная оценка («существует»), который только утверждает, что свойство или отношение выполняется по крайней мере для одного члена домена.

Количественная оценка в целом рассматривается в статье о количественная оценка (логика). Символы закодированы U + 2200 ∀ ДЛЯ ВСЕХ (HTML∀ · & ForAll ;, & forall; · как математический символ).

Основы

Предположим, что дано

2 · 0 = 0 + 0, и 2 · 1 = 1 + 1, и 2 · 2 = 2 + 2 и т. Д.

Казалось бы, это логическое соединение из-за многократного использования «и». Однако "и т. Д." нельзя интерпретировать как союз в формальная логика. Вместо этого утверждение следует перефразировать:

Для всех натуральных чисел п, 2·п = п + п.

Это единое утверждение с использованием универсальной количественной оценки.

Это утверждение можно назвать более точным, чем исходное. Хотя "и т. Д." неофициально включает натуральные числа, и не более того, это не было дано строго. С другой стороны, в универсальной квантификации натуральные числа упоминаются явно.

Этот конкретный пример истинный, потому что любое натуральное число можно заменить на п и утверждение «2 ·п = п + п"было бы правдой. Напротив,

Для всех натуральных чисел п, 2·п > 2 + п

является ложный, потому что, если п заменяется, например, 1, утверждение «2 · 1> 2 + 1» неверно. Неважно, что «2 ·п > 2 + п"верно для наиболее натуральные числа п: даже наличие единственного контрпример достаточно, чтобы доказать ложность универсальной количественной оценки.

С другой стороны, для всех составные числа п, 2·п > 2 + пверно, потому что ни один из контрпримеров не является составным числом. Это указывает на важность область дискурса, который указывает, какие значения п может взять.^{[примечание 1]} В частности, обратите внимание, что если область дискурса ограничена, чтобы состоять только из тех объектов, которые удовлетворяют определенному предикату, то для универсальной количественной оценки это требует логическое условное. Например,

Для всех составных чисел п, 2·п > 2 + п

является логически эквивалентный к

Для всех натуральных чисел п, если п составно, то 2 ·п > 2 + п.

Здесь конструкция «если ... то» указывает на логическое условие.

Обозначение

В символическая логика, универсальный символ квантора ${ displaystyle forall}$ (превратили "А " в без засечек шрифт Unicode U + 2200) используется для обозначения универсального количественного определения. Впервые он был использован таким образом Герхард Гентцен в 1935 г., по аналогии с Джузеппе Пеано с ${ Displaystyle существует}$ (повернутая E) обозначение для экзистенциальная количественная оценка и более позднее использование обозначений Пеано Бертран Рассел.^[1]

Например, если п(п) является предикатом "2 ·п > 2 + п" и N это набор натуральных чисел, то:

{ Displaystyle forall п ! в ! mathbb {N} ; P (п)}

это (ложное) утверждение:

Для всех натуральных чисел п, 2·п > 2 + п.

Аналогично, если Q(п) является предикатом "п составное ", то

{ Displaystyle forall п ! в ! mathbb {N} ; { bigl (} Q (n) rightarrow P (n) { bigr)}}

является (истинным) утверждением:

Для всех натуральных чисел п, если п составно, то 2 ·п > 2 + п

и с тех пор "п является составным "означает, что п уже должно быть натуральным числом, мы можем сократить это выражение до эквивалента:

{ Displaystyle forall п ; { bigl (} Q (n) rightarrow P (n) { bigr)}}

Для всех составных чисел п, 2·п > 2 + п.

Несколько вариантов обозначений для количественной оценки (которые применимы ко всем формам) можно найти в количественная оценка статья. Существует специальное обозначение, используемое только для универсальной количественной оценки, которое дается:

{ Displaystyle (п { in} mathbb {N}) , P (п)}

По умолчанию круглые скобки обозначают универсальную количественную оценку.

Характеристики

Отрицание

Обратите внимание, что количественно пропозициональная функция это заявление; таким образом, как и утверждения, количественные функции можно отрицать. Обозначения, которые большинство математиков и логиков используют для обозначения отрицания, следующие: ${ Displaystyle lnot }$ . Однако некоторые используют тильда (~).

Например, если P (Икс) - пропозициональная функция "x женат", то для a вселенная дискурса X всех живых людей, универсальная количественная оценка

Учитывая любого живого человека Икс, этот человек женат

дано:

{ Displaystyle forall {x} { in} mathbf {X} , P (x)}

Видно, что это безвозвратно ложно. По правде говоря, утверждается, что

Это не тот случай, когда любой живой человек Икс, этот человек женат

или, символически:

{ Displaystyle lnot forall {х} { in} mathbf {X} , P (x)}

.

Если утверждение не верно для каждый элемент вселенной дискурса, тогда, если предположить, что вселенная дискурса непуста, должен быть хотя бы один элемент, для которого утверждение ложно. То есть отрицание ${ Displaystyle forall {x} { in} mathbf {X} , P (x)}$ логически эквивалентно "Существует живой человек Икс не состоящий в браке ", или:

{ Displaystyle существует {х} { in} mathbf {X} , lnot P (x)}

В общем, отрицание универсальной квантификации пропозициональной функции является экзистенциальная количественная оценка отрицания этой пропозициональной функции; символически,

{ Displaystyle lnot forall {x} { in} mathbf {X} , P (x) Equiv exists {x} { in} mathbf {X} , lnot P (x )}

Ошибочно утверждать, что «все люди не состоят в браке» (т.е. «не существует человека, который состоит в браке»), когда имеется в виду, что «не все люди состоят в браке» (т.е. «существует человек, который не состоит в браке»):

{ displaystyle lnot exists {x} { in} mathbf {X} , P (x) Equiv forall {x} { in} mathbf {X} , lnot P (x ) not Equiv lnot forall {x} { in} mathbf {X} , P (x) Equiv exists {x} { in} mathbf {X} , lnot P (x)}

Прочие связки

Универсальный (и экзистенциальный) квантор остается неизменным по всему миру. логические связки ∧, ∨, →, и ↚, пока не затрагивается другой операнд; то есть:

{ Displaystyle { begin {выровненный} п (х) земля ( существует {у} { in} mathbf {Y} , Q (у)) & эквив существует {у} { in} mathbf {Y} , (P (x) land Q (y)) P (x) lor ( exists {y} { in} mathbf {Y} , Q (y)) & Equiv exists {y} { in} mathbf {Y} , (P (x) lor Q (y)), & { text {при условии, что}} mathbf {Y} neq emptyset P (x) to ( exists {y} { in} mathbf {Y} , Q (y)) & Equiv exists {y} { in} mathbf {Y} , (P (x) to Q (y)), & { text {при условии, что}} mathbf {Y} neq emptyset P (x) nleftarrow ( exists {y} { in} mathbf {Y} , Q (y)) & Equiv exists {y} { in} mathbf {Y} , (P (x) nleftarrow Q (y)) P (x) земля ( forall {y} { in} mathbf {Y} , Q (y)) & Equiv forall {y} { in} mathbf {Y} , (P (x) land Q (y)), & { text {при условии, что}} mathbf {Y} neq emptyset P (x) lor ( forall {y} { in} mathbf {Y} , Q (y)) & Equiv forall {y} { in} mathbf {Y} , (P (x) lor Q (y)) P (x) to ( forall {y} { in} mathbf {Y} , Q (y)) & Equiv forall {y} { in} mathbf {Y} , (P (x) to Q (y)) P (x) nleftarrow ( forall {y} { in} mathbf {Y} , Q (y)) & Equiv forall {y} { in} mathbf {Y} , (P (x) nleftarrow Q (y)), & { text {при условии, что}} mathbf {Y} neq emptyset end {выровнено} }}

И наоборот, для логических связок ↑, ↓, ↛, и ←, кванторы меняются местами:

{ Displaystyle { begin {align} P (x) uparrow ( exists {y} { in} mathbf {Y} , Q (y)) & Equiv forall {y} { in} mathbf {Y} , (P (x) uparrow Q (y)) P (x) downarrow ( exists {y} { in} mathbf {Y} , Q (y)) & Equiv forall {y} { in} mathbf {Y} , (P (x) downarrow Q (y)), & { text {при условии, что}} mathbf {Y} neq emptyset P (x) nrightarrow ( exists {y} { in} mathbf {Y} , Q (y)) & Equiv forall {y} { in} mathbf {Y} , (P (x) nrightarrow Q (y)), & { text {при условии, что}} mathbf {Y} neq emptyset P (x) получает ( exists {y} { in} mathbf {Y} , Q (y)) & Equiv forall {y} { in} mathbf {Y} , (P (x) получает Q (y)) P (x) uparrow ( forall {y} { in} mathbf {Y} , Q (y)) & Equiv exists {y} { in} mathbf {Y} , (P (x) uparrow Q (y)), & { text {при условии, что}} mathbf {Y} neq emptyset P (x) downarrow ( forall {y} { in} mathbf {Y} , Q (y)) & Equiv exists {y} { in} mathbf {Y} , (P (x) downarrow Q (y)) P (x) nrightarrow ( forall {y} { in} mathbf {Y} , Q (y)) & Equiv exists {y} { in} mathbf {Y} , (P (x) nrightarrow Q (y)) P (x) получает ( forall {y} { in} mathbf {Y} , Q (y)) & Equiv exists {y} { in} mathbf {Y} , (P (x) получает Q ( y)), & { text {при условии, что}} mathbf {Y} neq emptyset end {align}}}

Правила вывода

А правило вывода это правило, оправдывающее логический шаг от гипотезы к заключению. Есть несколько правил вывода, в которых используется универсальный квантор.

Универсальный экземпляр приходит к выводу, что, если известно, что пропозициональная функция универсально истинна, то она должна быть истинной для любого произвольного элемента универсума дискурса. Символически это представлено как

{ Displaystyle forall {x} { in} mathbf {X} , P (x) to P (c)}

куда c является совершенно произвольным элементом универсума дискурса.

Универсальное обобщение приходит к выводу, что пропозициональная функция должна быть универсально истинной, если она верна для любого произвольного элемента универсума дискурса. Символически для произвольного c,

{ Displaystyle P (c) to forall {x} { in} mathbf {X} , P (x).}

Элементc должно быть абсолютно произвольным; иначе логика не следует: если c не является произвольным, а вместо этого представляет собой конкретный элемент универсума дискурса, то P (c) подразумевает только экзистенциальную количественную оценку пропозициональной функции.

Пустой набор

Условно формула ${ Displaystyle forall {х} { in} emptyset , P (x)}$ всегда верно, независимо от формулы п(Икс); видеть пустая правда.

Универсальное закрытие

В универсальное закрытие формулы φ - это формула без свободные переменные полученный добавлением универсального квантора для каждой свободной переменной в φ. Например, универсальное закрытие

{ Displaystyle P (y) земля существует xQ (x, z)}

является

{ Displaystyle forall y forall z (P (y) земля существует xQ (x, z))}

.

Как примыкающий

В теория категорий и теория элементарные топои универсальный квантор можно понимать как правый смежный из функтор между комплекты питания, то обратное изображение функтор функции между множествами; аналогично, экзистенциальный квантор это левый смежный.^[2]

Для набора ${ displaystyle X}$ , позволять ${ displaystyle { mathcal {P}} X}$ обозначить его powerset. Для любой функции ${ displaystyle f: от X до Y}$ между сетами ${ displaystyle X}$ и ${ displaystyle Y}$ , существует обратное изображение функтор ${ displaystyle f ^ {*}: { mathcal {P}} Y to { mathcal {P}} X}$ между наборами степеней, который занимает подмножества кодомена ж вернуться к подмножествам своего домена. Левый сопряженный к этому функтору квантор существования ${ displaystyle exists _ {f}}$ а правый сопряженный - универсальный квантор ${ displaystyle forall _ {f}}$ .

То есть, ${ displaystyle exists _ {f} двоеточие { mathcal {P}} X to { mathcal {P}} Y}$ является функтором, который для каждого подмножества ${ Displaystyle S подмножество X}$ , дает подмножество ${ displaystyle exists _ {f} S подмножество Y}$ данный

{ Displaystyle существует _ {е} S = {у в Y ; | ; существует х в X. F (x) = у четырехугольник земля четырехугольник х в S }}

,

те ${ displaystyle y}$ в образе ${ displaystyle S}$ под ${ displaystyle f}$ . Точно так же универсальный квантор ${ displaystyle forall _ {f} двоеточие { mathcal {P}} X to { mathcal {P}} Y}$ является функтором, который для каждого подмножества ${ Displaystyle S подмножество X}$ , дает подмножество ${ displaystyle forall _ {f} S subset Y}$ данный

{ Displaystyle forall _ {f} S = {y in Y ; | ; forall x in X. f (x) = y quad подразумевает quad x in S }}

,

те ${ displaystyle y}$ чей прообраз под ${ displaystyle f}$ содержится в ${ displaystyle S}$ .

Более знакомая форма квантификаторов, используемых в логика первого порядка получается взятием функции ж быть уникальной функцией ${ displaystyle!: от X до 1}$ так что ${ Displaystyle { mathcal {P}} (1) = {T, F }}$ это двухэлементный набор, содержащий значения true и false, подмножество S это то подмножество, для которого предикат ${ Displaystyle S (х)}$ держит, и