Изомофизм моделей. Категоричные теории

Пусть T —теория первого порядка с языком L. Пусть A и B структу-

ры для языка L с универсумами A и B соответственно. По определению

структуры каждого n-арного функционального символа f из L определе-

на n-арныя функция fA из A в A и n-арная функция fB из B в B. Также

для каждого n-арного предикатного символа f из L определены n-арные

предикаты pA на A и n-арные предикаты pB на B.

ОПРЕДЕЛЕНИЕ 13 Биективное отображение ϕ универсума A в

универсум B является изоморфизмом структуры A на B, если для

любых элементов a1, a2, . . . , an из A для b1 = ϕ(a1), b2 = ϕ(a2), . . . , bn =

ϕ(an) имеем

fB(b1, b2, . . . , bn) = fA(a1, a2, an) и pB(b1, b2, . . . , bn) = pA(a1, a2, an),

Cтруктуры A и B называются изоморфными, если существует изомор-

физм из A в B.

Скажем, что теория T категорична, если любые две модели A и B тео-

рии T изоморфны.

Пример. Пусть T —теория без нелогических символов и с единствен-

ной нелогической аксиомой = . Тогда каждая модель теории T содержит

только один индивид, и любые две такие модели изоморфны. Можно дать

и более сложные примеры, но все такие примеры имеют только конечные

модели.

Пусть m некоторая мощность.

Определение. Теория T называется m–теорией, если она в ее языке

L мощность нелогических символов не выше m.

ТЕОРЕМА 17 (о мощности, А.Тарский). Пусть m –бесконечная

мощность и T —m-теория, имеющая бесконечную модель. Тогда T

имеет модель мощности m.

Если T имеет бесконечную модель, то теорема о мощности показывает,

что T имеет модели многих разных мощностей, а две модели с различными

мощностями не могут быть изоморфными.

Теория T называется частью теории T_, если T и T_ имеют один и тот

же язык и каждая нелогическая аксиома теории T является нелогической

аксиомой теории T_ .

Теория Т называется конечно аксиоматизируемой, если она имеет

только конечное число нелогических аксиом.

ТЕОРЕМА 18 ( теорема компактности, А.И.Мальцев) Формула

A теории T является истинной в T тогда и только тогда, когда A

является истинной в некоторой конечно аксиоматизируемой ча-

сти теории T.

Доказательство. Ввиду теоремы полноты нам нужно показать лишь,

что формула есть теорема теории T тогда и только тогда, когда эта фор-

мула есть теорема в некоторой конечно аксиоматизируемой части теории

T. Это очевидно, так как в любом доказательстве может использоваться

лишь конечное число нелогических аксиом.

Следствие. Теория T имеет модель тогда и только тогда, когда каждая

конечно аксиоматизируемая часть теории T имеет модель.

Доказательство. Беря в качестве теоремы формулу x _= x, замечаем,

что x _= x в любой структуре не является истинной

Лекция 12. Алгоритмы и машина Тьюринга

Понятие алгоритма является одним из основных понятий современ-

ной математики, имеющим тесную связь с логикой. С интуитивной точки

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

процедуру. Эта процедура начинается с некоторого набора данных и на-

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

этом должно быть совершено конечное число шагов по заранее заданным

правилам. Эти правила — точные инструкции (т.е. программа) конечной

длины. Они не должны предполагать никакой догадки и вероятностных

соображений со стороны человека или машины, нужно только точно ис-

полнять инструкции.

Алгоритмом является, например, сложение натуральных чисел, запи-

санных в десятичной системе счисления. В алгебре известен алгоритм

Евклида для нахождения НОД целых чисел или многочленов.

Слова «вычислительная процедура» нужно понимать в широком

смысле, не как только цифровых вычисления. Исходными данными и ре-

зультатами вычислительного процесса являются конструктивные объ-

екты. Они характеризуются как последовательности некоторого набора

символов—алфавита.

Вообще говоря, не предполагается, что в результате процедуры будет

обязательно получен результат. Если процедуре дана последователь-

ность символов символами из алфавита , то или

1) процедура вычислений должно закончиться после конечного числа

дискретных шагов и выдать результат; или

2) вычисления не заканчиваются после конечного числа шагов; также

же возможно, что процедура застревает в некоторой точке, и это нельзя

истолковать как выдачу значения результата вычислений.

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

произвольному набору данных распознает, будет получен выдан резуль-

тат вычислений или нет.

Говоря об алгоритме, подчеркивают такое его свойство, как массо-

вость — требовании найти единый алгоритм для решения не отдельной

задачи (например, сложения двух конкретных чисел), а серии отдельных,

единичных задач (сложения двух любых чисел).

58

Если требуемый алгоритм для решения задачи не не существует, то го-

ворят, что рассматриваемая задача алгоритмически неразрешима.

Понятия алгоритма всегда занимало важное место в науке. С древней-

ших времен многие задачи математики заключались в нахождении того

или иного алгоритма. Само слово «алгоритм» происходит от латинской

транслитерации арабского имени хорезмийского математика 9 в. аль-

Хорезми.

Длительное время интуитивного понятия алгоритма было вполне до-

статочно для задач математики и логики. Пусть имеется некоторая ал-

горитмическая проблема, т.е. необходимо найти алгоритм для решения

определенного класса задач. Если такой алгоритм найден, то предложен-

ный способ для решения задачи «признается всеми как алгоритм, исходя

из их собственного интуитивного представления об алгоритме». Поэтому

не требует точного понятия алгоритма.

Однако ситуация становится противоположной, если у нас после дли-

тельных, безуспешных попыток нахождения алгоритма возникает гипо-

теза, что такого алгоритма не существует. Для доказательства несуще-

ствования алгоритма необходимо его точное определение.

Разработка точного определения алгоритма—одно из самых замеча-

тельных достижений в логике и математике. Оно получено в 30 годах 20

в. в трудах Э.Поста, Э.Тьюринга, А.А.Маркова. Основная задача данной

лекции—формулировка точного определения алгоритма.