Т. А. Сливина математическая логика и теория алгоритмов

§ 3. Интерпретация языка теории

Под интерпретацией языка теории Т понимают всякую систему, включающую в себя:

1. Непустое множество М, называемое областью интерпретации.
2. Какое-либо соответствие, которое каждому элементу языка теории Т ставит в соответствие единственный элемент множества М, то есть функцию f с областью определения (А(Т), Е(Т)) и множеством значений, содержащимся в М.
В частности, каждой предикатной букве (А(Т), Е(Т)) ставится в соответствие некоторое n-местное отношение в М, каждой функциональной букве (А(Т), Е(Т)) ставится в соответствие некоторая n-местная операция в М, то есть функция Мⁿ М и каждой предметной постоянной а_i – некоторый элемент из М.
При заданной интерпретации предметные переменные рассматриваются как переменные, пробегающие область М, а символам логических и кванторных операций придается их обычный смысл.
Для такой интерпретации всякая формула без свободных переменных, т. е. замкнутая формула, представляет собой высказывание, которое истинно или ложно, а всякая формула со свободными переменными выражает некоторое отношение на области интерпретации. Это отношение может быть истинно для одних значений из области интерпретации и ложно для других.
Например, если взять в качестве области интерпретации множество целых положительных чисел и интерпретировать как отношение x₁ < х₂, то истинно для всех упорядоченных пар (а,b) положительных чисел таких, что а < b, а формула представляет собой отношение «для каждого целого положительного х₂, x₁< x₂», которое истинно только для одного числа 1.
И, наконец, формула утверждает существование наименьшего положительного числа и является истинной на множестве целых положительных чисел.
Определение 1. Формула А называется истинной (в данной интерпретации) тогда и только тогда, когда она выполнена на всякой последовательности из G.