Предикат

Определение

Высказывание — это предложение, которое истинно или ложно: «7 простое» истинно, «8 простое» ложно.

У предиката такого свойства нет. «$x$x простое» не истинно и не ложно: оно зависит от $x$x. Это предложение с пробелом, которое возвращает истинностное значение, как только пробел заполнен.

Свободная переменная, связанная переменная

Пока переменная остаётся свободной, у предложения нет истинностного значения. Закрывают её две операции:

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

Порядок кванторов

Два квантора разной природы не перестановочны. На целых числах, где $S(x, y)$S(x,y) означает «$y$y больше $x$x»:

$\forall x\, \exists y,\ S(x, y) \quad \text{истинно}$∀x∃y, S(x,y)истинно

$\exists y\, \forall x,\ S(x, y) \quad \text{ложно}$∃y∀x, S(x,y)ложно

Первое говорит: для каждого целого найдётся большее — и $y$y вправе зависеть от $x$x. Второе говорит: существует целое, большее всех, — наибольшее целое, которого не существует.

Те же символы в обратном порядке утверждают истину и ложь. Тот же механизм делает неперестановочным определение предела.

Отрицание квантифицированного высказывания

Отрицание проходит сквозь кванторы, меняя их местами:

$\neg\,\forall x,\ P(x) \iff \exists x,\ \neg P(x)$¬∀x, P(x)⟺∃x, ¬P(x)

$\neg\,\exists x,\ P(x) \iff \forall x,\ \neg P(x)$¬∃x, P(x)⟺∀x, ¬P(x)

Отрицание «все простые» даёт не «ни одно не простое», а «существует непростое». Одного контрпримера довольно, чтобы опровергнуть всеобщее; чтобы опровергнуть существование, нужно перебрать всю область.

Область входит в само высказывание

Предикат оценивается лишь на объявленной области. «$\exists x,\ x^2 = 2$∃x, x2=2» ложно на $\mathbb{Q}$Q и истинно на $\mathbb{R}$R: формула не изменилась, изменился универсум.

Опустить область — значит оставить высказывание неопределённым: не двусмысленным по смыслу, а лишённым истинностного значения.

Итог

Предикат становится высказыванием, когда его переменные закреплены или квантифицированы на объявленной области.