Главная arrow книги arrow Копия Глава 8. Логика первого порядка arrow Числа, множества и списки
Числа, множества и списки

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

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

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

В качестве синтаксического упрощения в данном разделе будет использоваться обычный словарь теории множеств. Пустое множество представляет собой константу, которая записывается как {}. Применяется также один унарный предикат, Set, который принимает истинное значение, если его фактическим параметром является множество. Бинарными предикатами являются(х — элемент множества s) и — подмножество, не обязательно строгое, множества s2). В качестве бинарных функций применяются (пересечение двух множеств), (объединение двух множеств) и(множество, полученное в результате присоединения элемента χ к множеству s). Один из возможных наборов аксиом приведен ниже.

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