Экзистенциальная квантификация

Математическое использование выражения «существует»

В логике предикатов экзистенциальная квантификация — это тип квантификатора , логическая константа , которая интерпретируется как «существует», «существует по крайней мере один» или «для некоторых». Обычно обозначается символом логического оператора ∃, который при использовании вместе с предикатной переменной называется экзистенциальным квантификатором (« ∃ x » или « ∃( x ) » или « (∃ x )» ^[1] ). Экзистенциальная квантификация отличается от универсальной квантификации («для всех»), которая утверждает, что свойство или отношение выполняется для всех членов домена. ^{[2] [3]} Некоторые источники используют термин экзистенциализация для обозначения экзистенциальной квантификации. ^[4]

Квантификация в целом рассматривается в статье о квантификации (логике) . Экзистенциальный квантификатор кодируется как U+2203 ∃ THERE EXISTS в Unicode , а также \existsв LaTeX и связанных с ним редакторах формул.

Основы

Рассмотрим формальное предложение

Для некоторого натурального числа , . ${\displaystyle n}$ ${\displaystyle n\times n=25}$

Это одно утверждение, использующее экзистенциальную квантификацию. Оно примерно аналогично неформальному предложению «Или , или , или , или... и так далее», но точнее, поскольку не требует от нас выводить значение фразы «и так далее». (В частности, предложение явно указывает областью своего дискурса натуральные числа, а не, например, действительные числа .) ${\displaystyle 0\times 0=25}$ ${\displaystyle 1\times 1=25}$ ${\displaystyle 2\times 2=25}$

Этот конкретный пример верен, потому что 5 — натуральное число, и когда мы подставляем 5 вместо n , мы получаем истинное утверждение . Неважно, что « » верно только для этого единственного натурального числа 5; существование единственного решения достаточно, чтобы доказать истинность этой экзистенциальной квантификации. ${\displaystyle 5\times 5=25}$ ${\displaystyle n\times n=25}$

Напротив, "Для некоторого четного числа , " ложно, потому что нет четных решений. Область дискурса , которая определяет значения, которые может принимать переменная n , поэтому имеет решающее значение для истинности или ложности утверждения. Логические союзы используются для ограничения области дискурса для выполнения заданного предиката. Например, предложение ${\displaystyle n}$ ${\displaystyle n\times n=25}$

Для некоторого положительного нечетного числа , ${\displaystyle n}$ ${\displaystyle n\times n=25}$

логически эквивалентно предложению

Для некоторого натурального числа является нечетным и . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n\times n=25}$

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

Обозначение

В символической логике "∃" (перевернутая буква " E " в шрифте без засечек , Unicode U+2203) используется для обозначения экзистенциальной квантификации. Например, нотация представляет (истинное) утверждение ${\displaystyle \exists {n}{\in }\mathbb {N} :n\times n=25}$

В множестве натуральных чисел существует такое, что . ${\displaystyle n}$ ${\displaystyle n\times n=25}$

Считается, что первым этот символ использовал Джузеппе Пеано в Formulario mathematico (1896). Впоследствии Бертран Рассел популяризировал его использование в качестве квантификатора существования. Благодаря своим исследованиям в теории множеств Пеано также ввел символы и для обозначения пересечения и объединения множеств соответственно. ^[5] ${\displaystyle \cap }$ ${\displaystyle \cup }$

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

Отрицание

Квантифицированная пропозициональная функция является утверждением; таким образом, подобно утверждениям, квантифицированные функции могут быть отрицаемы. Символ используется для обозначения отрицания. ${\displaystyle \lnot \ }$

Например, если P ( x ) — это предикат « x больше 0 и меньше 1», то для области дискурса X всех натуральных чисел экзистенциальная квантификация «Существует натуральное число x, которое больше 0 и меньше 1» может быть символически сформулирована как:

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

Можно доказать, что это ложно. По правде говоря, следует сказать: «Не существует натурального числа x, которое больше 0 и меньше 1», или, символически:

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

Если нет элемента области дискурса, для которого утверждение истинно, то оно должно быть ложным для всех этих элементов. То есть отрицание

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

логически эквивалентно «Для любого натурального числа x , x не больше 0 и меньше 1», или:

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

(Это обобщение законов Де Моргана на логику предикатов.)

Распространенной ошибкой является утверждение «не все лица состоят в браке» (т. е. «не существует ни одного лица, состоящего в браке»), когда подразумевается «не все лица состоят в браке» (т. е. «существует лицо, не состоящее в браке»):

${\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 \nexists {x}{\in }\mathbf {X} \,P(x)\equiv \lnot \ \exists {x}{\in }\mathbf {X} \,P(x)}$

В отличие от квантора всеобщности, квантор существования распределяется по логическим дизъюнкциям:

${\displaystyle \exists {x}{\in }\mathbf {X} \,P(x)\lor Q(x)\to \ (\exists {x}{\in }\mathbf {X} \,P(x)\lor \exists {x}{\in }\mathbf {X} \,Q(x))}$

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

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

Экзистенциальное введение (∃I) заключает, что если известно, что пропозициональная функция истинна для определенного элемента области дискурса, то должно быть верно, что существует элемент, для которого пропозициональная функция истинна. Символически,

${\displaystyle P(a)\to \ \exists {x}{\in }\mathbf {X} \,P(x)}$

Экзистенциальная инстанциация , проводимая в стиле вывода Fitch, продолжается путем ввода нового подвывода, заменяя экзистенциально квантифицированную переменную на субъект, который не появляется ни в одном активном подвыводе. Если заключение может быть достигнуто в этом подвыводе, в котором заменяемый субъект не появляется, то можно выйти из этого подвывода с этим заключением. Рассуждение, лежащее в основе экзистенциального исключения (∃E), следующее: если дано, что существует элемент, для которого функция предложения истинна, и если заключение может быть достигнуто путем присвоения этому элементу произвольного имени, то это заключение обязательно истинно , пока оно не содержит имени. Символически, для произвольного c и для предложения Q, в котором c не появляется:

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

${\displaystyle P(c)\to \ Q}$должно быть истинным для всех значений c в одной и той же области X ; в противном случае логика не соблюдается: если c не является произвольным, а представляет собой определенный элемент области дискурса, то утверждение P ( c ) может неоправданно дать больше информации об этом объекте.

Пустой набор

Формула всегда ложна, независимо от P ( x ). Это происходит потому, что обозначает пустое множество , а в пустом множестве нет x любого описания — не говоря уже о x, удовлетворяющем заданному предикату P ( x ). См. также Vacous truth для получения дополнительной информации. ${\displaystyle \exists {x}{\in }\varnothing \,P(x)}$ ${\displaystyle \varnothing }$

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

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

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

• Экзистенциальное предложение
• Теорема существования
• Логика первого порядка
• Квантификатор Линдстрема
• Список логических символов – для символа юникода ∃
• Дисперсия квантификатора
• Количественная оценка уникальности

Примечания

1. Бергманн, Мерри (2014). Книга логики . McGraw Hill. ISBN 978-0-07-803841-9.
2. "Предикаты и квантификаторы". www.csm.ornl.gov . Получено 2020-09-04 .
3. "1.2 Квантификаторы". www.whitman.edu . Получено 2020-09-04 .
4. Аллен, Колин; Хэнд, Майкл (2001). Логический учебник. МТИ Пресс. ISBN 0262303965.
5. Стивен Уэбб (2018). Столкновение символов. Springer Cham. стр. 210–211. doi :10.1007/978-3-319-71350-2. ISBN 978-3-319-71349-6.
6. Saunders Mac Lane , Ieke Moerdijk, (1992): Пучки в геометрии и логике Springer-Verlag ISBN 0-387-97710-4 . См. стр. 58 . 

Ссылки

• Хинман, П. (2005). Основы математической логики . AK Peters. ISBN 1-56881-262-0.