Сигнатура и интерпретация
Сигнатура
При построении формальной теории сначала фиксируется её сигнатура. Для этого необходимо задать:
- \(1.\) Разновидности предметных сущностей. В арифметике все предметы одного вида (числа). В геометрии на плоскости может быть два вида предметов — точки \(\mathbb P=\{x,y,...\}\) и прямые \(\mathbb L=\{\alpha,\beta,...\}\). Если предметы одного вида, то для обозначения произвольного, но фиксированного предмета, обычно, используются латинские буквы из конца алфавита: \(x\), \(y\), \(z\). Они называются предметными переменными.
- \(2.\) Предметные константы обозначают выделенные предметы с уникальными именами. В арифметике достаточно двух таких констант: 0 и 1. В геометрии Евклида выделенных констант нет. Константы часто обозначаются буквами из начала алфавита: \(a\), \(b\), \(c\), или специальными символами типа 0 или \(\varnothing\).
- \(3.\) Предметные функции — третий и не обязательный элемент сигнатуры. Они ставят в соответствие одним предметам — другие. Если \(\mathbb X\) множество предметов, то унарная функция \(f(x)\) — это отображение \(\mathbb X\mapsto \mathbb X\), бинарная функция \(g(x,y)\) — отображение \(\mathbb X\times \mathbb X \mapsto \mathbb X\) и т.д. Часто для бинарных функций используется операционная форма: \(x+y\), \(x\cdot y\). Переменные, константы и функции называются термами. Примеры термов: \(\varnothing\), \(x\), \(f(1, g(z))\).
- \(4.\) Предикаты (отношения в которые вступают сущности) — четвёртый и обязательный элемент сигнатуры. Они зависят от термов и равны истине или лжи. Предикаты обозначаются большими буквами: \(A(x)\), \(B(x,y)\) или в операционном виде: \(x=y\), \(\mathbb A \subseteq \mathbb B\) и т.д. В геометрии есть предикат принадлежности \(x\in \alpha\): "точка \(x\) лежит на прямой \(\alpha\)" и совпадения \(\alpha=\beta\). Первый предикат — это отображение \(\mathbb P\times \mathbb L \mapsto \{\F,\T\}\), а второй — \(\mathbb L\times \mathbb L \mapsto \{\F,\T\}\).
Если \(t_i\) — термы, а \(P(x_1,x_2,...)\) — предикат сигнатуры, то \(P(t_1,t_2,...)\) называется атомарной формулой. Из атомарных формул при помощи логических связок и кванторов строиться любая формула.
Одну и ту же теорию можно формулировать в различных сигнатурах. Так, вместо функций можно использовать предикаты (скажем, в арифметике считать истинным \(A(x,y,z)\), если \(x+y=z\)). Предметная область (множество всех сущностей) на этом этапе не фиксируется. Сигнатура только вводит обозначения с которыми оперирует теория.
Интерпретация
Интерпретация теории — это придание всем символам сигнатуры содержательного (конструктивного) смысла. Для этого необходимо задать не пустое множество \(\mathbb X = \{a_1,a_2,...\}\) (конечное или бесконечное, одно или несколько), называемое носителем интерпретации. На нём определяется действие функций (например, \(f(a_1)=a_2\), \(f(a_2)=a_8\), и т.д.). Затем предикатам приписываются истинностные значения (для \(E(x,y)\) определить, что \(E(a_1, a_1)=\T\), а \(E(a_1, a_2)=\F\), и т.д.).
Формула называется общезначимой или тавтологией, если она истинна на любой интерпретации при любой оценке свободных переменных (придании им конкретных значений). Например \(\neg A(x)\vee A(x)\) — тавтология. Отметим, что если формула истинна на всех конечных интерпретациях (конечных множествах), она может оказаться ложной для бесконечных множеств (пример: существование максимального элемента в упорядоченных множествах.
Формула называется невыполнимой (= противоречивой), если она ложна в любой интерпретации. Пример: \(\neg A(x)\,\&\, A(x)\).
Формула называется выполнимой (= непротиворечивой), если существует (хотя бы одна) интерпретация, где она истинна. Пример: \(A\vee B\).
Аксиомы
Система аксиом любой формальной теории разбивается на две группы — общелогические и предметные аксиомы. Общелогические аксиомы — это тавтологии. Например \(P\,\&\,Q\equiv Q\,\&\, P\) или \(P \to ( P \vee Q )\) справедливы в любой теории. В этих аксиомах символы \(P,Q\) обозначают любые формулы. Получаемые из общелогических аксиом теоремы, справедливы во всех теориях.
Общелогические аксиомы дополняются правилами получения новых формул. К ним относятся правила с кванторами (\(\forall_x P_x~\Rightarrow \exists_x P_x\)) или без них (\(\neg P\vee Q,~P\vee S~\Rightarrow~Q\vee S\)). Понятие истинности при этом отходит на второй план и выведенные формулы считаются верными, даже если их истинность невозможно проверить при помощи таблиц.
Предметные аксиомы связаны с конкретной сигнатурой (теория чисел, геометрия и т.д.). Они накладывают ограничения на предикаты и функции, определяя тем самым их свойства. Общелогические аксиомы и правила вывода создаются "один раз", тогда как предметные аксиомы для каждой новой теории необходимо придумывать заново. Предикаты зависят только от термов, но не зависят от других предикатов. Такая сигнатура называется теорией предикатов первого порядка. Например, в арифметике выражение \((x < y)=z\) бессмысленно.
Для одной и той же системы аксиом можно построить различные интерпретации. И наоборот, на некоторых интерпретациях часть аксиом будет выполняться, а часть — нет.