Предмет математической логики

Основная идея математической логики – формализация знаний и рассуждений. Известно, что наиболее легко формализуемые знания – математические. Таким образом, математическая логика, по-существу, – наука о математике, или метаматематика. Центральным понятием математической логики является ``математическое доказательство''. Действительно, ``доказательные'' (иначе говоря, дедуктивные) рассуждения – единственный вид признаваемых в математике рассуждений. Рассуждения в математической логике изучаются с точки зрения формы, а не смысла. По-существу, рассуждения моделируются чисто ``механическим'' процессом переписывания текста ( формул). Такой процесс называют выводом. Говорят еще, что математическая логика оперирует только синтаксическими понятиями.

Однако обычно всё же важно, как соотносятся рассуждения с действительностью (или нашими представлениями). Поэтому, надо всё же иметь в виду некоторый смысл формул и вывода. При этом используют термин семантика (синоном слова ``смысл'') и чётко разделяют синтаксис и семантику.

Когда же действительно интересуются только синтаксисом, часто используют термин ``формальная система''. Мы будем использовать синоним этого термина – ``исчисление'' (используются ещё термины ``формальная теория'' и ``аксиоматика'').

Объектом формальных систем являются строки текста (последовательности символов), с помощью которых записываются формулы.

Формальная система определена, если:

1. Задан алфавит (множество символов, используемых для построения формул).

2. Определено, какие именно строки считать формулами (остальные строки считаются просто бессмысленными).

3. Выделено множество формул, называемых аксиомами. Это – стартовые точки в выводах.

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

Пример формальной системы

Рассмотрим пример простой, ``игрушечной'' формальной системы.

Пример формальной системы. Популярная формальная система (DH) определяется следующим образом:

1. Алфавит: {M,I,U}.

2. Формулы: любая последовательность символов данного алфавита.

3. Одна аксиома: MI.

4. Правила вывода:

· правило 1: из формулы вида mI можно получить mIU.

· правило 2: из формулы вида Mm можно получить Mmm.

· правило 3: подстроку III можно заменить на U.

· правило 3: подстроку UU можно заменить на пустую строку.

символом m в первом и во втором правиле обозначается произвольное слово.

Приведём пример построения вывода:

MI (аксиома), MII (правило 2), MIIII (правило 2), MIIIIU (правило 1), MIUU (правило 3), MI (правило 4).

Определите, можно ли получить формулу MU с помощью правил вывода из аксиомы.



Структура раздела

Раздел ``математическая логика'' состоит из трёх частей: по неформальному аксиоматическому методу, по логике высказываний и по логике предикатов (первого порядка).

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

По поводу используемой нотации. Текст построен на последовательности задач. Большинство задач состоит в доказательстве некоторых утверждений. Для некоторых задач имеются указания для решения. Для отдельных приведено решение. Некоторые задачи служат для подготовки читателя к следующим задачам – для номеров таких вспомогательных задач используется курсив. В тексте мы часто используем шаблон ``для <объекты> : <свойство>''. Здесь ``:'' является сокращением слов ``выполняется следующее:''.

4.6. Аксиоматический метод

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

В этой части мы исследуем применение аксиоматического метода в арифметике. Мы используем термин ``натуральные числа'' в смысле, отличающемся от обычного – ноль мы тоже включаем в натуральные числа. Такое использование этого термина обычно для зарубежных математиков. Мы пишем ``натуральные числа'' только чтобы не писать каждый раз ``целые неотрицательные числа''.

Аксиомы натуральных чисел

Мы рассматриваем множество w объектов называемых натуральными числами. Одно из натуральных чисел называется нулём и обозначается 0 . Для любого натурального числа n одно из натуральных чисел называется следующим за числом n и обозначается n' .

Множество натуральных чисел таково, что удовлетворяет следующим аксиомам:

Аксиома 1. Для любого натурального числа n: n'№ 0.

Аксиома 2. Для любых натуральных чисел m и n: если m'=n', то m = n.