Элементы математической логики. Теория моделей

Теория моделей — раздел математической логики, который занимается изучением связи между формальными языками и их интерпретациями, или моделями. Название теория моделей было впервые предложено Альфредом Тарским в 1954 году. Основное развитие теория моделей получила в работах Тарского, Мальцева и Робинсона.

Форма́льный язы́к в математической логике, информатике и лингвистике — множество конечных слов (строк, цепочек) над конечным алфавитом. Понятие языка чаще всего используется в теории автоматов, теории вычислимости и теории алгоритмов. Научная теория, которая имеет дело с этим объектом, называется теорией формальных языков.
В теории моделей язык строится из множеств символов, функций и отношений вместе с их арностью, а также множества переменных. Каждое из этих множеств может быть бесконечным. Из языка вместе с универсальными логическими символами составляются логические высказывания.

Классическая теория моделей первого порядка
Теория моделей для классической логики первого порядка является исторически первым и наиболее развитым примером теоретико-модельного подхода. В роли моделей здесь выступают множества, представляющие область возможных значений переменных. Функциональные символы интерпретируются как операции соответствующей арности над ними, а предикаты — как отношения (более подробно, см. Логика первого порядка, интерпретация).

Логика первого порядка — формальное исчисление, допускающее высказывания относительно переменных, фиксированных функций и предикатов. Расширяет логику высказываний.
Помимо логики первого порядка существуют также логики высших порядков, в которых кванторы могут применяться не только к переменным, но и к множествам. Термины логика предикатов и исчисление предикатов могут означать как логику первого порядка, так и логики первого и высшего порядка вместе; в первом случае иногда говорится о чистой логике предикатов или чистом исчислении предикатов.