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

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

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

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

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

Основы

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

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

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

Для всех натуральных чисел 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 .

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

Обозначения

В символической логике символ квантора универсальности (перевернутая буква « А » в шрифте без засечек , 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)}$

Другие соединения

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

${\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 — совершенно произвольный элемент вселенной дискурса.

Универсальное обобщение приходит к выводу, что пропозициональная функция должна быть универсально истинной, если она верна для любого произвольного элемента вселенной дискурса. Символически для произвольного 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))}$.

Как сопряженный

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

Для множества обозначим его powerset . Для любой функции между множествами и существует функтор обратного образа между наборами степеней, который возвращает подмножества кодомена 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.

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

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

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

Примечания

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

Рекомендации

1. Миллер, Джефф. «Самое раннее использование символов теории множеств и логики». Древнейшие варианты использования различных математических символов .
2. Сондерс Мак Лейн , Ике Мурдейк, (1992) Пучки в геометрии и логике Springer-Verlag. ISBN 0-387-97710-4 См. стр. 58. 

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

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

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