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

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

Обычно он обозначается перевернутым символом логического оператора 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

является ложным , потому что если п замещен, например, 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 году, по аналогии с Джузеппе Пеано «s (обращенной E) для обозначения экзистенциальной квантификации и последующим использованием обозначений Пеаны по Бертрану Рассел . ^[1]${\ displaystyle \ forall}$${\ Displaystyle \ существует}$

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

${\ Displaystyle \ forall п \! \ в \! \ mathbb {N} \; P (п)}$

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

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

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

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

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

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

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

Свойства [ править ]

Отрицание [ править ]

Обратите внимание, что количественная пропозициональная функция - это утверждение; таким образом, как и утверждения, количественные функции могут быть инвертированы. Нотация большинство математиков и логики используют для обозначения отрицания: . Однако некоторые используют тильду (~).${\ Displaystyle \ lnot \}$

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

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

дано:

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

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

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

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

${\ Displaystyle \ lnot \ \ forall {х} {\ in} \ mathbf {X} \, P (x)}$.

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

${\ Displaystyle \ существует {х} {\ in} \ mathbf {X} \, \ lnot P (x)}$

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

${\ Displaystyle \ lnot \ \ forall {x} {\ in} \ mathbf {X} \, P (x) \ Equiv \ \ exists {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 {\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))}$.

Как смежный [ править ]

В категории теории и теории элементарных топосов , квантор всеобщности можно понимать как сопряженные справа от более функтора между множествами мощности , в прообразе функтором функции между множествами; аналогично квантор существования является левым сопряженным . ^[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.

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

См. Также [ править ]

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

Заметки [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

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