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

Информацию о «для каждого» в компьютерной логике см. в цикле Foreach .

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

Тип	Квантор
Поле	Математическая логика
Заявление	$\forall xP(x)$ верно, когда $P(x)$ верно для всех значений $x$.
Символическое заявление	$\forall xP(x)$

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

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

Количественная оценка в целом рассматривается в статье о количественной оценке (логике) . Квантор всеобщности кодируется как U+2200 ∀ FOR ALL в Юникоде и как \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 может принимать. В частности, обратите внимание, что если область дискурса ограничена тем, что она состоит только из тех объектов, которые удовлетворяют определенному предикату, то для количественной оценки универсальности требуется логический кондиционал . Например,

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

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

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

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

Обозначения

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

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

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

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

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

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

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

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

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

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

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

Отрицание

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

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

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

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

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

написано

$\forall x\in X\,P(x)$

Это утверждение неверно. Правдиво сказано, что

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

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

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

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

$\exists x\in X\,\lnot P(x)$

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

$\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)$

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

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

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

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

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

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

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

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

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

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

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

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

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

Пустой набор

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

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

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

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

является

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

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

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

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

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

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

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

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

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

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

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

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

что верно, если $S$ не пусто и

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

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

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

См. также

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

Ссылки

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

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

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