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

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

Обычно он обозначается перевернутым символом логического оператора A (∀) , который при использовании вместе с предикатной переменной называется универсальным квантором (« $\forall$ $x$ », « $\forall ($ $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 может принимать. В частности, обратите внимание, что если область дискурса ограничена состоянием только тех объектов, которые удовлетворяют определенному предикату, то для универсальной количественной оценки это требует логического условия . Например,

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

является логическим эквивалентом для

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

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

Обозначение

В символьной логике универсальный символ квантора (повернутая « A » в шрифте без засечек , Unicode U + 2200) используется для обозначения универсального количественного определения. Впервые он был использован в этом пут Генцена в 1935 году, по аналогии с Джузеппе Пеано «s (обращенной E) для обозначения экзистенциальной квантификации и последующим использованием обозначений Пеаны по Бертрану Рассел . ${\ 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 \ forall x \; P (x) \ quad {\ text {эквивалентно}} \ 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 \ существует х \ в Икс \, \ lnot P (x)}

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

{\ Displaystyle \ lnot \ \ существует х \ в Икс \, п (х) \ эквив \ \ forall x \ в X \, \ lnot P (x) \ not \ Equiv \ \ lnot \ \ forall x \ in X \ , P (x) \ Equiv \ \ существует x \ in X \, \ lnot P (x)}

Прочие связки

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

{\ Displaystyle {\ begin {выровнен} п (х) \ земля (\ существует {у} {\ in} \ mathbf {Y} \, Q (у)) & \ эквив \ \ существует {у} {\ 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 {при условии, что}} \ 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 {при условии, что}} \ 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) \ земля (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ Equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ land Q (y)), & {\ text {при условии, что}} \ 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 {при условии, что}} \ mathbf {Y} \ neq \ emptyset \ end {выровнено} }}

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

{\ Displaystyle {\ begin {align} 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 {при условии, что}} \ 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 {при условии, что}} \ mathbf {Y} \ neq \ emptyset \\ P (x) \ получает (\ exists {y} {\ in} \ mathbf {Y} \, Q (y)) & \ Equiv \ \ forall {y} {\ in} \ mathbf {Y} \, (P (x) \ получает Q (y)) \\ P (x) \ вверх (\ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ Equiv \ \ exists {y} {\ in} \ mathbf {Y} \, (P (x) \ uparrow Q (y)), & {\ text {при условии, что}} \ 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) \ получает ( \ forall {y} {\ in} \ mathbf {Y} \, Q (y)) & \ Equiv \ \ exists {y} {\ in} \ mathbf {Y} \, (P (x) \ получает Q ( y)), & {\ text {при условии, что}} \ mathbf {Y} \ neq \ emptyset \\\ end {align}}}

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

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

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

{\ Displaystyle \ forall {x} {\ in} \ mathbf {X} \, от P (x) \ до P (c)}

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

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

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

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

Пустой набор

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

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

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

{\ Displaystyle P (y) \ земля \ существует xQ (x, z)}

является

{\ Displaystyle \ forall y \ forall z (P (y) \ земля \ существует xQ (x, z))}

.

Как примыкающий

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

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

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

{\ Displaystyle \ существует _ {е} S = \ {у \ в Y \; | \; \ существует х \ в X. \ F (х) = у \ квад \ земля \ квад х \ в S \},}

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

{\ displaystyle \ forall _ {f} S = \ {y \ in Y \; | \; \ forall x \ in X. \ f (x) = y \ quad \ подразумевает \ quad x \ in S \},}

те, чей прообраз ниже содержится в . ${\ displaystyle y}$ ${\ displaystyle f}$ ${\ displaystyle S}$

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