Языки и исчисления

Формулы и интерпретации


Начнем с примера. Пусть — некоторое непустое множество, а — бинарное отношение на нем, то есть подмножество декартова произведения . Вместо мы будем писать . Рассмотрим формулу

Эта формула выражает некоторое свойство бинарного отношения

(для любого элемента найдется элемент, находящийся с ним в отношении ) и может быть истинна или ложна. Например, если есть множество натуральных чисел , а — отношение "строго меньше" (другими словами, есть множество всех пар , для которых ), то эта формула истинна. А для отношения "строго больше" (на том же множестве) эта формула ложна.

Вопрос о том, будет ли истинна формула

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

Перейдем к формальным определениям. Пусть — непустое множество. Множество состоит из всех последовательностей длины , составленных из элементов множества . Назовем -местной функцией на множестве любое отображение в (определенное на всем ). Синонимы: "функция аргументов", "функция валентности ", "функция местности " и даже "функция арности " (последнее слово происходит от слов "унарная" для функций одного аргумента, "бинарная" (операция) для функций двух аргументов и "тернарная" для трех аргументов).

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

Мы будем рассматривать также функции и предикаты валентности нуль.
Множество одноэлементно (содержит единственную последовательность длины ). Поэтому функции

отождествляются с элементами множества , а нульместных предикатов ровно два — истинный и ложный.

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

Остается определить три вещи: что такое формула данной сигнатуры, что такое интерпретация данной сигнатуры и когда формула является истинной (в данной интерпретации).

Фиксируем некоторый набор символов, называемых индивидными переменными. Они предназначены для обозначения элементов множества, на котором определены функции и предикаты; обычно в таком качестве используют латинские буквы с индексами. В каждой формуле будет использоваться конечное число переменных, так что счетного набора переменных нам хватит. Мы предполагаем, что переменные отличны от всех функциональных и предикатных символов сигнатуры (иначе выйдет путаница).

Определим понятие терма данной сигнатуры. Термом называется последовательность переменных, запятых, скобок и символов сигнатуры, которую можно построить по следующим правилам:

  • Индивидная переменная есть терм.
  • Функциональный символ валентности есть терм.
  • Если — термы, а — функциональный символ валентности , то есть терм.


В принципе можно было не выделять функциональные символы валентности (которые также называют константами) в отдельную группу, но тогда бы после них пришлось писать скобки (как это делается в программах на языке Си).

Если — предикатный символ валентности , а — термы, то выражение

считается атомарной формулой. Кроме того, любой предикатный символ валентности считается атомарной формулой.



Формулы строятся по таким правилам:

  • Атомарная формула есть формула.
  • Если — формула, то — формула.
  • Если и — формулы, то выражения , , также являются формулами.
  • Если есть формула, а — индивидная переменная, то выражения и

    являются формулами.


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

Итак, понятие формулы в данной сигнатуре полностью определено. Иногда такие формулы называют формулами первого порядка данной сигнатуры, или формулами языка первого порядка с данной сигнатурой.

Наш следующий шаг — определение интерпретации данной сигнатуры. Пусть фиксирована некоторая сигнатура . Чтобы задать интерпретацию сигнатуры , необходимо:

  • указать некоторое непустое множество , называемое носителем интерпретации;
  • для каждого предикатного символа сигнатуры указать предикат с соответствующим числом аргументов, определенный на множестве (как мы уже говорили, -местным предикатным символам ставится в соответствие либо И, либо Л);
  • для каждого функционального символа сигнатуры

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


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

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

Сигнатура теории упорядоченных множеств включает в себя два двуместных предикатных символа (равенство и порядок) и не имеет функциональных символов. Здесь также вместо по традиции пишут .

Аксиомы порядка (рефлексивность, антисимметричность, транзитивность) могут быть записаны формулами этой сигнатуры. Например, требование антисимметричности записывается так:

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

39. Как записать с помощью формулы свойство линейной упорядоченности? свойство не иметь наибольшего элемента? свойство плотности (отсутствия соседних элементов)? свойство фундированности (отсутствия бесконечных убывающих последовательностей — или, что эквивалентно, наличия минимального элемента в любом подмножестве)? свойство полной упорядоченности? (Указание: не для всех перечисленных свойств это возможно.)



Сигнатуру теории групп можно выбирать по-разному. Можно считать, что (помимо равенства) она имеет двуместный функциональный символ (который по традиции записывают между множителями), константу (нульместный функциональный символ) и одноместный функциональный символ для обращения. Тогда аксиомы теории групп записываются с использованием лишь кванторов всеобщности:

Если не включать операцию обращения в сигнатуру, придется использовать квантор существования и переписать последнюю аксиому так:

40. Как записать аксиомы теории групп, если в сигнатуре нет константы ? (Указание: аксиома о существовании обратного станет частью аксиомы о существовании единицы.)

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

Сигнатура теории множеств содержит два двуместных предикатных символа: для принадлежности и для равенства. Аксиомы теории множеств можно записывать в виде формул этой сигнатуры. Чаще всего рассматривают вариант аксиоматической теории множеств, называемый теорией Цермело-Френкеля и обозначаемый ZF. Приведем для примера одну из аксиом теории ZF, называемую аксиомой объемности, или экстенсиональности:

42. Сформулировать словесно эту аксиому.

43. Записать в виде формулы аксиому регулярности, или фундирования, которая говорит, что у всякого множества есть минимальный (с точки зрения отношения ) элемент, то есть элемент, не пересекающийся с самим множеством.

44. Какова естественная сигнатура для теории полей? Можно ли записать в виде формулы этой сигнатуры утверждение о том, что поле имеет характеристику ? конечную характеристику? алгебраически замкнуто?


Содержание раздела