Универсальная количественная оценка

Математическое использование «для всех»

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

Обычно он обозначается перевернутым символом логического оператора A (∀) , который при использовании вместе с предикатной переменной называется универсальным квантификатором (« ∀ x », « ∀( x ) » или иногда просто « ( x ) »). Универсальная квантификация отличается от экзистенциальной квантификации («существует»), которая утверждает только, что свойство или отношение имеет место по крайней мере для одного члена домена.

Квантификация в целом рассматривается в статье о квантификации (логике) . Универсальный квантификатор кодируется как U+2200 ∀ FOR ALL в Unicode , а также \forallв LaTeX и связанных с ним редакторах формул.

Основы

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

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

Это, казалось бы, логическое соединение из-за повторного использования "and". Однако "etc." не может быть интерпретировано как соединение в формальной логике . Вместо этого утверждение следует перефразировать:

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

Это единое утверждение, использующее универсальную квантификацию.

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

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

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

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

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

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

логически эквивалентно​

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

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

Обозначение

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

Например, если P ( n ) — предикат «2· n > 2 + n », а N — множество натуральных чисел, то

${\displaystyle \forall n\!\in \!\mathbb {N} \;P(n)}$

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

«для всех натуральных чисел n имеем 2· n > 2 + n ».

Аналогично, если Q ( n ) — предикат « n является составным», то

${\displaystyle \forall n\!\in \!\mathbb {N} \;{\bigl (}Q(n)\rightarrow P(n){\bigr )}}$

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

«для всех натуральных чисел n , если n — составное число, то 2· n > 2 + n ».

Несколько вариантов обозначений квантификации (применимых ко всем формам) можно найти в статье «Квантификатор» .

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

Отрицание

Отрицание универсально квантифицированной функции получается путем замены универсального квантификатора на экзистенциальный квантификатор и отрицания квантифицированной формулы. То есть,

${\displaystyle \lnot \forall x\;P(x)\quad {\text{is equivalent to}}\quad \exists x\;\lnot P(x)}$

где обозначает отрицание . ${\displaystyle \lnot }$

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

Для любого живого человека x этот человек женат.

написано

${\displaystyle \forall x\in X\,P(x)}$

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

Неправильно считать, что любой живущий человек x женат.

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

${\displaystyle \lnot \ \forall x\in X\,P(x)}$.

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

${\displaystyle \exists x\in X\,\lnot P(x)}$

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

${\displaystyle \lnot \ \exists x\in X\,P(x)\equiv \ \forall x\in X\,\lnot P(x)\not \equiv \ \lnot \ \forall x\in X\,P(x)\equiv \ \exists x\in X\,\lnot P(x)}$

Другие связки

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

${\displaystyle {\begin{aligned}P(x)\land (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\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{provided that }}\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{provided that }}\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)\land (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\land Q(y)),&{\text{provided that }}\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{provided that }}\mathbf {Y} \neq \emptyset \end{aligned}}}$

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

${\displaystyle {\begin{aligned}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{provided that }}\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{provided that }}\mathbf {Y} \neq \emptyset \\P(x)\gets (\exists {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \forall {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y))\\P(x)\uparrow (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\uparrow Q(y)),&{\text{provided that }}\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)\gets (\forall {y}{\in }\mathbf {Y} \,Q(y))&\equiv \ \exists {y}{\in }\mathbf {Y} \,(P(x)\gets Q(y)),&{\text{provided that }}\mathbf {Y} \neq \emptyset \\\end{aligned}}}$

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

Правило вывода — это правило, обосновывающее логический шаг от гипотезы к заключению. Существует несколько правил вывода, которые используют квантификатор всеобщности.

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

${\displaystyle \forall {x}{\in }\mathbf {X} \,P(x)\to P(c)}$

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

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

${\displaystyle P(c)\to \ \forall {x}{\in }\mathbf {X} \,P(x).}$

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

Пустой набор

По соглашению, формула всегда истинна, независимо от формулы P ( x ); см. пустая истина . ${\displaystyle \forall {x}{\in }\emptyset \,P(x)}$

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

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

${\displaystyle P(y)\land \exists xQ(x,z)}$

является

${\displaystyle \forall y\forall z(P(y)\land \exists xQ(x,z))}$.

Как присоединенный

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

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

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

${\displaystyle \exists _{f}S=\{y\in Y\;|\;\exists x\in X.\ f(x)=y\quad \land \quad x\in S\},}$

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

${\displaystyle \forall _{f}S=\{y\in Y\;|\;\forall x\in X.\ f(x)=y\quad \implies \quad x\in S\},}$

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

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

${\displaystyle {\begin{array}{rl}{\mathcal {P}}(!)\colon {\mathcal {P}}(1)&\to {\mathcal {P}}(X)\\T&\mapsto X\\F&\mapsto \{\}\end{array}}}$

${\displaystyle \exists _{!}S=\exists x.S(x),}$

что верно, если не пусто, и ${\displaystyle S}$

${\displaystyle \forall _{!}S=\forall x.S(x),}$

что ложно, если S не является X.

Приведенные выше квантификаторы всеобщности и существования обобщаются до категории предпучка .

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

• Экзистенциальная квантификация
• Логика первого порядка
• Список логических символов — для символа Unicode ∀

Примечания

1. Дополнительную информацию об использовании областей дискурса с количественными утверждениями можно найти в статье Квантификация (логика) .

Ссылки

1. Миллер, Джефф. «Ранние применения символов теории множеств и логики». Ранние применения различных математических символов .
2. то есть, если переменная не встречается свободно в формуле в эквивалентностях ниже ${\displaystyle y}$ ${\displaystyle P(x)}$
3. Saunders Mac Lane , Ieke Moerdijk, (1992) Пучки в геометрии и логике Springer-Verlag. ISBN 0-387-97710-4 См. стр. 58 

• Хинман, П. (2005). Основы математической логики . AK Peters . ISBN 1-56881-262-0.
• Франклин, Дж. и Дауд, А. (2011). Доказательство в математике: Введение. Kew Books. ISBN 978-0-646-54509-7.{{cite book}}: CS1 maint: multiple names: authors list (link)(гл. 2)

Внешние ссылки

• Словарное определение слова every в Викисловаре