Квантор загальності

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

Він зазвичай позначається символом логічного оператора «Обернена А» ( $\forall$ ), який, коли використовується разом зі змінною предикатом, називається квантором загальності ( $\forall {x}$ , $\forall {\left(x\right)}$ чи іноді сам $\left(x\right)$ ). Квантор загальності відрізняється від квантора існування («існує»), який лише припускає, що властивість або відношення виконується для принаймні одного члена області.

Квантифікація загалом покрита у статті квантор. Символи кодуються U+2200 ∀ FOR ALL (як математичний символ).

Основи

Припустімо, дано, що

2\cdot 0=0+0

, і

2\cdot 1=1+1

, і

2\cdot 2=2+2

, і т. д.

Це, здавалося б, є логічною кон'юнкцією через повторюване використання «і». Проте, «і т. д.» не може бути інтерпретоване як кон'юнкція у формальній логіці. Натомість, судження повинно бути перефразовано:

Для всіх натуральних чисел n,

2\cdot n=n+n

Це одиночне судження, що використовує квантор загальності.

Це судження, можна сказати, точніше за початкове. Поки «і т. д.» неформально включає натуральні числа і нічого більше, це не дано суворо. У кванторі загальності, з іншого боку, натуральні числа згадуються явно.

Цей конкретний приклад є істиною, оскільки будь-яке натуральне число може бути замінено на n і судження « $2\cdot n=n+n$ » буде істинним. На противагу,

Для всіх натуральних чисел n,

2\cdot n>2+n

є хибою, оскільки якщо n замінюється, наприклад, 1, судження « $2\cdot 1>2+1$ » є хибним. Несуттєво, що « $2\cdot n>2+n$ » є істинним для більшості натуральних чисел n: навіть існування єдиного контрприкладу достатньо для доведення хибності квантора загальності.

З іншого боку, для всіх складених чисел n, $2\cdot n>2+n$ є істиною, оскільки жоден із контрприкладів не є складеним числом. Це показує важливість області дискурсу, що вказує, які значення n можна брати[1]. Зокрема, варто зазначити, що якщо область дискурсу обмежено для вмісту лише тих об'єктів, які задовольняють певному предикатові, то для квантора загальності це вимагає логічної умови. Наприклад,

Для всіх складених чисел n,

2\cdot n>2+n

є логічним еквівалентом до

Для всіх натуральних чисел n, якщо n складене, то

2\cdot n>2+n

Тут конструкція «якщо … то» позначає логічну умову.

Нотація

У символічній логіці, символ квантора загальності $\forall$ (обернена «A» у гротескному шрифті, Юнікод U+2200) використовується для позначення квантора загальності[2].

Наприклад, якщо $P\left(n\right)$ є предикатом $2\cdot n>2+n$ , а $\mathbb {N}$ — множиною натуральних чисел, то:

\forall {n\in \mathbb {N} }\;P\left(n\right)

є (хибним) судженням:

Для всіх натуральних чисел n,

2\cdot n>2+n

Аналогічно, якщо $Q\left(n\right)$ є предикатом «n складене», то

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

є (істинним) судженням:

Для всіх натуральних чисел n, якщо n складене, то

2\cdot n>2+n

а оскільки «n складене» має на увазі, що n повинно вже бути натуральним числом, ми можемо скоротити це судження до еквіваленту:

\forall {n}\;{\bigl (}Q\left(n\right)\rightarrow P\left(n\right){\bigr )}

Для всіх складених чисел n,

2\cdot n>2+n

Деякі варіації у нотації для кванторів (які застосовуються до всіх форм) можуть бути знайдені у статті квантор. Ця особлива нотація використовується лише для кванторів загальності, як дано:

\left(n\in \mathbb {N} \right)P\left(n\right)

Дужки позначають квантор загальності за замовчуванням.

Властивості

Заперечення

Слід зазначити, що квантифікована пропозиційна функція є судженням; таким чином, подібно до суджень, квантифіковані функції можуть бути заперечені. Нотація, яку більшість математиків і логіків використовують на позначення заперечення, це: $\lnot$ . Проте, деякі використовують тильду (~).

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

Дано будь-яку живу особу x, ця особа одружена

дано:

\forall {x}\in \mathbf {X} P\left(x\right)

Можна побачити, що це безповоротно хибно. По правді, воно говорить, що

Це не випадок, що для даної будь-яку живу особу x, ця особа одружена

або, символічно:

\lnot \forall {x}\in \mathbf {X} P\left(x\right)

.

Якщо судження неістинне для кожного елементу Універсуму дискурсу, то, припускаючи, що універсум дискурсу непорожній, повинен бути принаймні один елемент, для якого судження хибне. Тобто, заперечення $\forall {x}\in \mathbf {X} P\left(x\right)$ логічно еквівалентно «Існує жива особа x, яка неодружена», або:

\exists {x}\in \mathbf {X} \lnot P\left(x\right)

Загалом, тоді заперечення квантора загальності пропозиційної функції є квантором існування заперечення тієї ж пропозиційної функції; символічно,

\lnot \forall {x}\in \mathbf {X} P\left(x\right)\equiv \exists {x}\in \mathbf {X} \lnot P\left(x\right)

Помилково стверджувати «всі особи неодружені» (тобто «не існує особи, яка одружена») коли це означає, що «не всі особи одружені» (тобто «існує особа, яка неодружена»):

\lnot \exists {x}\in \mathbf {X} P\left(x\right)\equiv \forall {x}\in \mathbf {X} \lnot P\left(x\right)\not \equiv \ \lnot \forall {x}\in \mathbf {X} P\left(x\right)\equiv \exists {x}\in \mathbf {X} \lnot P\left(x\right)

Інші сполучники

Квантор загальності (й існування) переміщується без змін через логічні сполучники $\land$ , $\lor$ , $\to$ і $\nleftarrow$ так довго, доки інший операнд не зазнає впливу; тобто:

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)),~\mathrm {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)),~\mathrm {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)),~\mathrm {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)),~\mathrm {provided~that} ~\mathbf {Y} \neq \emptyset

Навпаки, для логічних сполучників $|$ , $\downarrow$ , $\nrightarrow$ і $\gets$ квантори перевертаються:

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)),~\mathrm {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)),~\mathrm {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)),~\mathrm {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)),~\mathrm {provided~that} ~\mathbf {Y} \neq \emptyset

Правило висновування

Правило висновування — це правило, що виправдовує логічний крок від гіпотези до висновку. Існують декілька правил висновувань, які використовують квантор загальності.

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

\forall {x}\in \mathbf {X} P\left(x\right)\to P\left(c\right)

де c є цілком довільним елементом універсуму дискурсу.

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

P\left(c\right)\to \forall {x}\in \mathbf {X} P\left(x\right)

Елемент c повинен бути цілком довільним; інакше логіка не виконується: якщо c не довільний, і є натомість конкретний елемент універсуму дискурсу, то P(c) лише має на увазі квантор існування пропозиційної функції.

Порожня множина

За конвенцією, формула $\forall {x}\in \emptyset P\left(x\right)$ завжди істинна незалежно від формули $P\left(x\right)$ ; див. порожня істина.

Універсальне замикання

Універсальним замиканням формули $\phi$ є формула без вільних змінних, отримана додаванням квантора загальності до кожної вільної змінної у $\phi$ . Наприклад, універсальним замиканням

P\left(y\right)\land \exists {x}Q\left(x,z\right)

є

\forall {y}\forall {z}{\bigl (}P\left(y\right)\land \exists {x}Q\left(x,z\right){\bigr )}

.

Як приєднання

У теорії категорій і теорії елементарних топосів, квантор загальності може розумітися як праве приєднання функтора між булеанами, функтора оберненого образу функції між множинами; також, квантор існування є лівим приєднанням[3].

Для множини $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 як унікальної функції ${\displaystyle$ так, що ${\mathcal {P}}(1)=\{T,F\}$ є двохелементною множиною, маючи значення істини та хиби, підмножина S є тією підмножиною, для якої предикат $S\left(x\right)$ виконується, і

{\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\left(x\right)

,

яка є істиною, якщо S непорожня, і

\forall _{!}S=\forall x.S\left(x\right)

,

яка є хибністю, якщо S не є X.

Квантори загальності й існування, наведені вище, узагальнюються до категорії передпучка.

Див. також

Квантор існування
Логіка першого порядку
Список логічних символів — для Юнікодного символу $\forall$

Примітки

Подальша інформація про використання областей дискурсу з квантифікованими судженнями може бути знайдена у статті Квантор.
Обернену А було використано у XIX сторіччі Чарлзом Сандерсом Пірсом як логічний символ для «не-Американський» («неамериканський»). Діперт, Рендалл (2004). Peirce's deductive logic (вид. The Cambridge Companion to Peirce). Cheryl Misak. с. 320.
Маклейн, Саундерс; Мордійк, Айк (1992). Sheaves in Geometry and Logic. Springer-Verlag. с. 58. ISBN 0-387-97710-4.

Джерела

Гінман, П. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-56881-262-0.
Франклін, Джеймс; Дауд, А. (2011). 2. Proof in Mathematics: An Introduction. Kew Books. ISBN 978-0-646-54509-7.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Подальша інформація про використання областей дискурсу з квантифікованими судженнями може бути знайдена у статті Квантор.

[2] Обернену А було використано у XIX сторіччі Чарлзом Сандерсом Пірсом як логічний символ для «не-Американський» («неамериканський»). Діперт, Рендалл (2004). Peirce's deductive logic (вид. The Cambridge Companion to Peirce). Cheryl Misak. с. 320.

[3] Маклейн, Саундерс; Мордійк, Айк (1992). Sheaves in Geometry and Logic. Springer-Verlag. с. 58. ISBN 0-387-97710-4.