Примеры аксиоматических теорий

Приведем два примера аксиоматических теорий.

Пример 3.1. Теория аффинных плоскостей. Первичными понятиями этой теории являются точка и прямая, характеризующие принадлежность объектов аксиоматической теории некоторым множествам (множеству точек и множеству прямых). Третьим первичным понятием теории является инцидентность, характеризующее определенное соответствие между точками и прямыми. Если точка A связана соответствием инцидентности с прямой a, то говорят, что точка A инцидентна прямой a, и пишут A I a.

Все свойства прямых, точек и отношения инцидентности описываются тремя аксиомами.

A1. Существуют три точки не инцидентные одной прямой.

A2. Любые две различные точки инцидентны единственной прямой.

Прежде чем сформулировать третью аксиому, введем определение.

Определение D1. Две прямые l и m, не имеющие ни одной общей точки или полностью совпадающие, называются параллельными (обозначение: l m).

A3 (аксиома параллельных). Для любой точки A и прямой l существует единственная прямая m такая, что A I m и m l.

Поразительно, что такая бедная аксиоматика приводит к содержательной теории.

Пример 3.2. Теория эквивалентности. В качестве простого примера аксиоматической теории рассмотрим теорию, описывающую отношение эквивалентности. Эта теория имеет дело с одним типом объектов, множество которых будем обозначать буквой X. Для этих объектов не вводится специальное название (но можно было бы, конечно, назвать их как угодно). Объекты связаны единственным бинарным отношением a. При этом требуется выполнение трех аксиом B1-B3.

B1. Отношение a транзитивно, то есть для любых трех объектов из a a b и b a c следует a a c.

B2. Отношение a симметрично, то есть для любых двух объектов из a a b следует b a a.

B3. Отношение a рефлексивно, то есть для любого объекта выполняется условие a a a.

Для читателей, не знакомых с бинарными отношениями, ниже приводятся необходимые определения и примеры. Более подробное изложение вопросов, связанных с бинарными отношениями, можно найти в одной из предыдущих лекций [1].

Определение 3.1. Бинарным отношением на множестве X называется любая совокупность упорядоченных пар (x, y), где x, y Î X.

Например, пусть X = { a, b, c, d, e }. Тогда множество кортежей a = {(a, b), (a, c), (b, d), (c, e), (e, e), (e, b)} является отношением на множестве X.

Обычно отношения задаются не перечислением элементов множества a, а путем указания свойства пар (x, y), принадлежащих этому множеству. Например, отношение a = {(4, 4), (3, 3), (2, 2), (4, 2)} на множестве X = { 4, 3, 2 } можно определить как свойство «делится» на этом подмножестве целых чисел.

Хорошо известными примерами отношений из школьного курса математики являются:

· на множестве целых чисел Z отношения «делится», «делит», «равно», «больше», «меньше», «взаимно просты»;

· на множестве прямых пространства отношения «параллельны», «взаимно перпендикулярны», «скрещиваются», «пересекаются», «совпадают»;

· на множестве окружностей плоскости «пересекаются», «касаются», «концентричны».

Факт принадлежности кортежа (x, y) отношению a, часто обозначают с помощью так называемой инфиксной формы записи: x a y. Типичными примерами таких записей из курса математики являются: x > y, a = b, 8 4, m l, a b и т. п.

Широко распространен способ представления отношений, основанный на использовании ориентированных графов. При таком представлении элементы множества X изображаются вершинами графа (точками плоскости), а элементы (x, y) отношения a дугами (стрелками), соединяющими первую компоненту x отношения со второй компонентой y. Граф бинарного отношения a из приведенного выше примера изображен на рисунке 3.1.

Рис. 3.1. Граф бинарного отношения
на множестве { a, b, c, d, e }

Очевидно, что произвольные бинарные отношения изучать в общем плане не особенно интересно, о них можно сказать очень мало. Однако, если отношения удовлетворяют некоторым дополнительным условиям, относительно них можно делать более содержательные утверждения. В аксиомах были перечислены три свойства бинарных отношений: транзитивность, рефлексивность и симметричность.

Примерами транзитивных отношений служат:

· отношение «делится» на множестве действительных чисел;

· отношение «больше» на множестве действительных чисел;

· отношение «старше» на множестве людей игрушек;

· отношение «иметь одинаковый цвет» на множестве детских игрушек;

· отношение «быть потомком» на множестве людей.

Отношение «быть похожим» на множестве людей не обладает свойством транзитивности.

Примерами симметричных отношений являются:

· отношение перпендикулярности на множестве прямых;

· отношение касания на множестве окружностей;

· отношение «быть похожим» на множестве людей;

· отношение «иметь одинаковый пол» на множестве животных.

Отношение «x брат y» на множестве всех людей не является симметричным. В то же время отношение «x брат y» на множестве мужчин симметричным является.

В графе симметричного отношения для каждой дуги из вершины x в вершину y имеется дуга из y в x.

В графе рефлексивного отношения в каждой вершине графа обязательно имеется петля.

Определение 3.2. Бинарное отношение a на X называется антирефлексивным, если ни для одного не выполняется условие a a a.

Определение 3.3. Бинарное отношение a на множестве X называется антисимметричным, если для любых различных элементов условия a a b и b a a не выполняются одновременно.

Например, отношение «делится» на множестве натуральных чисел является антисимметричным, так как из следует, что a = b. Однако на множестве целых чисел отношение «делится» антисимметричным не является, так как , но -2 ¹ 2.

Отношения «выше», «тяжелее», «старше» антисимметричны на множестве людей. Отношение «быть сестрой» на множестве всех людей антисимметричным не является.

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

Определение 3.4. Бинарное отношение a на множестве X называется связным, если для любых двух различных элементов a и b имеет место a a b, либо b a a.

Примером связного отношения является отношение «больше» на множестве действительных чисел. Отношение «делится» на множестве целых чисел связным не является.