Введение

Понятие, связанное с базами данных. В математике и абстрактной алгебре, алгебра отношений — это остаточная булева алгебра, расширенная инволюцией, называемой обращением, являющейся унарной операцией. Мотивирующим примером алгебры отношений является алгебра 2 X 2 всех бинарных отношений на множестве X, то есть подмножеств декартова квадрата X2, где R•S интерпретируется как обычное композиционное произведение бинарных отношений R и S, а обращение R — как обратное отношение. Алгебра отношений возникла в работах Августа Де Моргана и Чарльза Пирса в XIX веке и достигла кульминации в алгебраической логике Эрнста Шрёдера. Рассматриваемая здесь эквациональная форма алгебры отношений была разработана Альфредом Тарским и его учениками, начиная с 1940-х годов. Тарски и Гивант (1987) применили алгебру отношений к безпеременному представлению аксиоматической теории множеств, что подразумевает возможность построения математики, основанной на теории множеств, без использования переменных.

Определение

Алгебра отношений (L, ∧, ∨, ¬, 0, 1, •, 'I', ˘) — это алгебраическая структура, оснащенная булевыми операциями конъюнкции x∧y, дизъюнкции x∨y и отрицания x¬, булевыми константами 0 и 1, реляционными операциями композиции x•y и обратной x˘, и реляционной константой 'I', таким образом, что эти операции и константы удовлетворяют определенным уравнениям, составляющим аксиоматизацию исчисления отношений. Приблизительно, алгебра отношений относится к системе бинарных отношений на множестве, содержащем пустые (0), универсальные (1) и тождественные ('I') отношения и замкнутую относительно этих пяти операций, как группа относится к системе перестановок множества, содержащего тождественную перестановку и замкнутую относительно композиции и обращения. Однако теория первого порядка для алгебр отношений не является полной для таких систем бинарных отношений. Следуя Йонссону и Тсинакису (1993), удобно определить дополнительные операции x ◁ y = x • y˘ и, дуально, x ▷ y = x˘ • y. Йонссон и Тсинакис показали, что 1 = 'I' ◁ x = x ▷ 'I', и что оба выражения равны x˘. Следовательно, алгебру отношений можно также определить как алгебраическую структуру (L, ∧, ∨, ¬, 0, 1, •, 'I', ◁, ▷). Преимущество этой сигнатуры перед обычной заключается в том, что алгебру отношений можно полностью определить как остаточную булеву алгебру, для которой 'I' ◁ x является инволюцией, то есть 1 = 'I' ◁ ('I' ◁ x) = x. Последнее условие можно рассматривать как реляционный аналог уравнения 1/(1/x) = x для обычного арифметического обратного значения, и некоторые авторы используют термин "обратное значение" как синоним для "обращения". Поскольку остаточные булевы алгебры аксиоматизируются конечным числом тождеств, то же самое справедливо и для алгебр отношений. Следовательно, последние образуют вариацию, вариацию RA алгебр отношений. Развертывание вышеуказанного определения в виде уравнений дает следующую конечную аксиоматизацию.

Выражение свойств бинарных отношений в RA

В следующей таблице показано, сколько из обычных свойств бинарных отношений можно выразить как краткие RA-равенства или неравенства. Ниже, неравенство вида A ≤ B является сокращением для булевого уравнения 1=A∨B = B. Наиболее полный набор результатов такого рода представлен в главе C Carnap (1958), где обозначения значительно отличаются от используемых здесь. Глава 3.2 Suppes (1960) содержит меньше результатов, представленных в виде теорем ZFC и использующих обозначения, более близкие к используемым здесь. Ни Carnap, ни Suppes не формулировали свои результаты, используя RA, представленные здесь, или в уравнительном виде. R является, если и только если: Функциональная R˘ • R ≤ 'I' Лево-полная 'I' ≤ R • R˘ (R˘ является сюръективной) Функция функциональная и лево-полная. Инъективная R • R˘ ≤ 'I' (R˘ является функциональной) Сюръективная 'I' ≤ R˘ • R (R˘ является лево-полной) Биекция 1=R˘ • R = R • R˘ = 'I' (Инъективная сюръективная функция) Транзитивная R • R ≤ R Рефлексивная 'I' ≤ R Корефлексивная R ≤ 'I' Иррефлексивная 1=R ∧ 'I' = 0 Симметричная 1=R˘ = R Антисимметричная R ∧ R˘ ≤ 'I' Асимметричная 1=R ∧ R˘ = 0 Сильно связная 1= R ∨ R˘ = 1 Связная 1= 'I' ∨ R ∨ R˘ = 1 Идемпотентная 1=R • R = R Предотношение R является транзитивным и рефлексивным. Отношение эквивалентности R является симметричным предотношением. Отношение частичного порядка R является антисимметричным предотношением. Отношение полного порядка R является сильно связным и отношением частичного порядка. Отношение строгого частичного порядка R является транзитивным и иррефлексивным. Отношение строгого полного порядка R является связным и отношением строгого частичного порядка. Плотность R ∧ 'I'^(−) ≤ (R ∧ 'I'^(−)) • (R ∧ 'I'^(−)).

Выразительная сила

Метаматематика РА подробно рассматривается в Tarski и Givant (1987), а более кратко – в Givant (2006). РА состоит исключительно из уравнений, манипулируемых исключительно однородной заменой и заменой равного равным. Оба правила хорошо знакомы из школьной математики и общей абстрактной алгебры. Следовательно, доказательства в РА строятся способом, привычным для всех математиков, в отличие от математической логики в целом. РА может выразить любые (и, вплоть до логической эквивалентности, точно) формулы логики первого порядка (FOL), содержащие не более трех переменных. (Одной и той же переменной можно присваивать квантор несколько раз, и, следовательно, кванторы могут быть вложены произвольно глубоко путем «повторного использования» переменных.) Удивительно, но этого фрагмента FOL достаточно для выражения арифметики Пеано и почти всех когда-либо предложенных аксиоматических теорий множеств. Таким образом, РА, по сути, представляет собой способ алгебраизации почти всей математики, отказываясь от FOL и его связок, кванторов, знаков выводимости и modus ponens. Поскольку РА может выражать арифметику Пеано и теорию множеств, к нему применимы теоремы Гёделя о неполноте; РА является неполной, неполностью доказуемой и неразрешимой. (Примечание: фрагмент булевой алгебры РА является полным и разрешимым.) Представимые алгебры отношений, образующие класс RRA, – это алгебры отношений, изоморфные некоторой алгебре отношений, состоящей из бинарных отношений на некотором множестве и замкнутые относительно предполагаемой интерпретации операций РА. Легко показать, например, с помощью метода псевдоэлементарных классов, что RRA является квазиразнообразием, то есть аксиоматизируемым универсальной теорией Хорна. В 1950 году Роджер Линдон доказал существование уравнений, выполняющихся в RRA, но не выполняющихся в RA. Следовательно, сорт, порожденный RRA, является собственным подсортом сорта RA. В 1955 году Альфред Тарски показал, что сам RRA является сортом. В 1964 году Дональд Монк показал, что RRA не имеет конечной аксиоматизации, в отличие от RA, которая по определению конечно аксиоматизирована.

Примеры

Любую булеву алгебру можно превратить в РА, интерпретируя соединение как композицию (моноидное умножение •), то есть x • y определяется как x∧y. Эта интерпретация требует, чтобы конверс интерпретировал тождество (ў = y), и чтобы оба остаточных y  \ x и x /y интерпретировали условное y → x (то есть ¬y ∨ x). Мотивирующий пример алгебры отношений зависит от определения бинарного отношения R на множестве X как любого подмножества R ⊆ X^( 2), где X^( 2) является декартовым квадратом X. Множество степеней 2 X 2, состоящее из всех бинарных отношений на X, является булевой алгеброй. В то время как 2 X 2 может быть сделана алгеброй отношений, взяв 1=R • S = R ∧ S, как в примере (1) выше, стандартная интерпретация • вместо этого 1=x(R • S )z = ∃y : xRy ∧ ySz. То есть упорядоченная пара (x, z) принадлежит отношению R • S тогда и только тогда, когда существует y в X, такое что (x, y) ∈ R и (y, z) ∈ S. Эта интерпретация однозначно определяет R \ S как состоящее из всех пар (y, z), таких что для всех x ∈ X, если xRy, то xSz. Дуально, S /R состоит из всех пар (x, y) таких, что для всех z ∈ X, если yRz, то xSz. Перевод 1=ў = ¬(y\¬'I') затем устанавливает обратное R˘ как состоящее из всех пар (y, x) таких, что (x, y) ∈ R.
Важным обобщением предыдущего примера является множество степеней 2E, где E ⊆ X^( 2) является любым отношением эквивалентности на множестве X. Это обобщение, потому что X^( 2) само по себе является отношением эквивалентности, а именно полным отношением, состоящим из всех пар. Хотя 2E не является субальгеброй 2 X 2, когда 1=E ≠ X^( 2) (поскольку в этом случае оно не содержит отношения X^( 2), а верхний элемент 1 является E вместо X^( 2)), тем не менее, оно превращается в алгебру отношений с использованием тех же определений операций. Его важность заключается в определении представляемой алгебры отношений как любой алгебры отношений, изоморфной субальгебре алгебры отношений 2E для некоторого отношения эквивалентности E на некотором множестве. В предыдущем разделе говорится больше о соответствующей метаматематике. Пусть G — группа. Тогда множество степеней является алгеброй отношений с очевидными операциями булевой алгебры, композицией, заданной произведением групповых подмножеств, конверсом, заданным обратным подмножеством, и тождеством, заданным одноэлементным подмножеством. Существует вложение гомоморфизма алгебры отношений в , которое отображает каждое подмножество в отношение . Образ этого гомоморфизма представляет собой множество всех правоинвариантных отношений на G.
Если групповая сумма или произведение интерпретируют композицию, групповой обратный интерпретирует конверс, групповая единица интерпретирует 'I', и если R является взаимно однозначным соответствием, так что 1=R˘ • R = R • R˘ = 'I', то L является группой, а также моноидом. B4 и B7 становятся хорошо известными теоремами теории групп, так что РА является надлежащим расширением теории групп, а также булевой алгебры.

Исторические замечания

Де Морган основал РА в 1860 году, но К. С. Пирс значительно развил эту область и был увлечен её философским потенциалом. Работы Де Моргана и Пирса получили известность главным образом благодаря расширенному и окончательному изложению, представленному Эрнстом Шрёдером в томе 3 его «Vorlesungen» (1890–1905). «Principia Mathematica» в значительной степени опиралась на РА Шрёдера, однако признавала его лишь как изобретателя нотации. В 1912 году Альвин Корсельт доказал, что для определенной формулы с четырным уровнем вложенности кванторов не существует эквивалента в РА. Этот факт привел к снижению интереса к РА до тех пор, пока Тарский (1941) не начал писать о ней. Его ученики продолжают развивать РА и по сей день. Тарский вновь обратился к РА в 1970-х годах при содействии Стивена Гиванта; результатом этого сотрудничества стала монография Тарского и Гиванта (1987), являющаяся определяющим трудом по данной теме. Более подробную информацию об истории РА можно найти в работах Маддукса (1991, 2006).