Алгебра отношений - Relation algebra

В математике и абстрактной алгебре , А отношение алгебра является residuated Булева алгебра расширен с инволюцией называется обратным , одноместный операцией. Мотивирующим примером алгебры отношений является алгебра 2 X ² всех бинарных отношений на множестве X , то есть подмножества декартового квадрата X 2 , где RS интерпретируется как обычная композиция бинарных отношений R и S , и с обратным к R как обратным соотношением .

Связь алгебра возникла в работе 19-го века Августа Де Моргана и Чарльза Пирса , который завершился в алгебраической логики от Эрнста Шрёдера . Рассматриваемая здесь эквациональная форма алгебры отношений была разработана Альфредом Тарски и его учениками, начиная с 1940-х годов. Тарский и Гивант (1987) применили алгебру отношений к без переменных трактовке аксиоматической теории множеств , подразумевая, что математика, основанная на теории множеств, сама может вестись без переменных.

Определение

Отношение алгебра ( L , ∧, ∨, - , 0, 1, •, я , ˘) является алгебраической структурой оснащен булевыми операциями конъюнкции ху , дизъюнкции ху и отрицание х - , булевы константы 0 и 1, реляционные операции композиции xy и обратного x ˘, а также реляционная константа I , так что эти операции и константы удовлетворяют определенным уравнениям, составляющим аксиоматизацию исчисления отношений . Грубо говоря, отношение алгебры к системе бинарных отношений на множестве , содержащем пустые (0), полном (1), а также идентичность ( я ) отношения и закрытый в рамках этих пяти операций , как группа , является системой перестановок из а множество, содержащее тождественную перестановку и замкнутое по композиции и инверсии. Однако теория алгебр отношений первого порядка не является полной для таких систем бинарных отношений.

Следуя Йонссону и Цинакису (1993), удобно определить дополнительные операции xy = xy ˘ и, соответственно, xy = x ˘ • y . Йонссон и Цинакис показали, что Ix = xI , и что оба они равны x ˘. Следовательно, алгебру отношений также можно определить как алгебраическую структуру ( L , ∧, ∨, - , 0, 1, •, I , ◁, ▷) . Преимущество этой сигнатуры по сравнению с обычной состоит в том, что алгебра отношений может быть определена полностью просто как делимая булева алгебра, для которой Ix является инволюцией, то есть I ◁ ( Ix ) = x . Последнее условие можно рассматривать как относительный аналог уравнения 1 / (1 / x ) = x для обычного арифметического обратного , и некоторые авторы используют обратное как синоним обратного.

Поскольку аппроксимируемые булевы алгебры аксиоматизируются конечным числом тождеств, то же самое касается алгебр отношений. Следовательно, последние образуют многообразие , многообразие алгебр отношений RA . Расширение приведенного выше определения в виде уравнений дает следующую конечную аксиоматизацию.

Аксиомы

Приведенные ниже аксиомы B1-B10 адаптированы из Givant (2006: 283) и впервые были изложены Тарским в 1948 году.

L - булева алгебра относительно двоичной дизъюнкции , ∨ и унарного дополнения () - :

B1 : AB = BA
B2 : A ∨ ( BC ) = ( AB ) ∨ C
B3 : ( A -B ) - ∨ ( A -B - ) - = A

Эта аксиоматизация булевой алгебры принадлежит Хантингтону (1933). Обратите внимание, что точка пересечения подразумеваемой булевой алгебры не является оператором • (даже если она распределяется по ∨, как это происходит), а единица булевой алгебры не является константой I.

L является моноидом относительно двоичной композиции (•) и нулевого тождества I :

B4 : A • ( BC ) = ( AB ) • C
B5 : AI = A

Унарная обратная () ˘ инволюция относительно композиции :

B6 : A ˘˘ = A
B7 : ( AB ) ˘ = B ˘ • A ˘

Аксиома B6 определяет преобразование как инволюцию , тогда как B7 выражает антидистрибутивное свойство преобразования относительно композиции.

Converse и композиция распределяются по дизъюнкции:

B8 : ( AB ) ˘ = A ˘∨ B ˘
B9 : ( AB ) • C = ( AC ) ∨ ( BC )

B10 - это эквациональная форма Тарского факта, открытого Августом Де Морганом , что ABC - A ˘ • CB - CB ˘ ≤ A - .

B10 : ( A ˘ • ( AB ) - ) ∨ B - = B -

Эти аксиомы являются теоремами ZFC ; для чисто булевых B1-B3 этот факт тривиален. После каждой из следующих аксиом показан номер соответствующей теоремы в главе 3 Suppes (1960), изложение ZFC: B4 27, B5 45, B6 14, B7 26, B8 16, B9 23.

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

В следующей таблице показано, сколько обычных свойств бинарных отношений можно выразить в виде кратких RA- равенств или неравенств. Ниже неравенство вида  ≤  B представляет собой сокращенное булевое уравнение B = B .

Наиболее полный набор результатов такого рода - это глава C Карнапа (1958), где обозначения довольно далеки от обозначений в этой статье. Глава 3.2 Suppes (1960) содержит меньше результатов, представленных в виде теорем ZFC и использующих обозначения, которые больше напоминают обозначения этой статьи. Ни Карнап, ни Суппес не сформулировали свои результаты, используя RA в этой записи или эквациональным способом.

R - это Если и только если :
Функциональный R ˘ • RI
Итого слева IRR ˘ ( R ˘ сюръективно)
Функция функциональные и лево-тотальные.
Инъективный
RR ˘ ≤ I ( R ˘ функциональный)
Сюръективный IR ˘ • R ( R ˘ является тотальным слева)
Биекция R ˘ • R = RR ˘ = I (инъективная сюръективная функция)
Переходный RRR
Рефлексивный IR
Coreflexive RI
Нерефлексивный RI = 0
Симметричный R ˘ = R
Антисимметричный RR ˘ ≤ I
Асимметричный RR ˘ = 0
Сильно связан RR ˘ = 1
Связаны IRR ˘ = 1
Идемпотент RR = R
Предзаказ R транзитивен и рефлексивен.
Эквивалентность R - симметричный предпорядок.
Частичный заказ R - антисимметричный предпорядок.
Общий заказ R - сильно связный и частичный порядок.
Строгий частичный заказ R транзитивен и иррефлексивен.
Строгий общий порядок R связный и строгий частичный порядок.
Плотный RI - ≤ ( RI - ) • ( RI - ) .

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

В метаматематике из РА подробно рассматриваются в Тарском и Givant (1987), и более кратко в Givant (2006).

RA полностью состоит из уравнений, управляемых с использованием не более чем равномерной замены и замены равных равных. Оба правила хорошо знакомы из школьной математики и из абстрактной алгебры в целом. Следовательно, доказательства RA выполняются способом, знакомым всем математикам, в отличие от случая в математической логике в целом.

РА не может выразить любые (и до логической эквивалентности , в точности) первого порядка логика (Fol) формулы , содержащие не более чем трех переменных. (Данная переменная может быть определена количественно несколько раз, и, следовательно, кванторы могут быть вложены произвольно глубоко за счет «повторного использования» переменных.) Удивительно, но этого фрагмента FOL достаточно для выражения арифметики Пеано и почти всех когда-либо предложенных аксиоматических теорий множеств . Следовательно, RA - это, по сути, способ алгебраизации почти всей математики без использования FOL и его связок , квантификаторов , турникетов и modus ponens . Поскольку RA может выражать арифметику Пеано и теорию множеств, к нему применимы теоремы Гёделя о неполноте ; RA является неполным , incompletable и неразрешимой . (NB. Фрагмент булевой алгебры RA полон и разрешим.)

В представимых алгебрах отношений , образующий класс RRA , являются теми отношениями алгебр изоморфны некоторым отношение алгебры , состоящей из бинарных отношений на некотором множестве и замкнуты относительно предполагаемой интерпретации РА операций. Легко показать, например, с помощью метода псевдоэлементарных классов , что RRA является квазимногообразием , т. Е. Аксиоматизируемым универсальной теорией Хорна . В 1950 году Роджер Линдон доказал существование уравнений , выполняемых в RRA, которые не выполнялись в RA . Следовательно, многообразие, порожденное RRA, является собственным подмногообразием многообразия RA . В 1955 году Альфред Тарски показал, что RRA сама по себе является разновидностью. В 1964 году Дональд Монк показал, что RRA не имеет конечной аксиоматизации, в отличие от RA , которая конечно аксиоматизируется по определению.

Q-отношения алгебры

РА является Q-алгебра отношение ( КОР ) , если в дополнение к B1-B10 , существуют некоторые и В такие , что (Тарский и Givant 1987: §8.4):

Q0 : A ˘ • AI
Q1 : B ˘ • BI
Q2 : A ˘ • B = 1

По существу эти аксиомы подразумевают , что вселенная имеет (несюръективное) спаривание отношения которого проекция A и B . Это теорема, что каждый QRA является RRA (Доказательство Маддукса, см. Tarski & Givant 1987: 8.4 (iii)).

Каждый QRA представим (Tarski and Givant 1987). То, что не всякая алгебра отношений представима, является фундаментальным отличием RA от QRA и булевых алгебр , которые, согласно теореме Стоуна о представлении булевых алгебр , всегда могут быть представлены как множества подмножеств некоторого множества, замкнутых относительно объединения, пересечения и дополнения.

Примеры

  1. Любую булеву алгебру можно превратить в RA , интерпретируя конъюнкцию как композицию (моноидное умножение •), т.е. xy определяется как xy . Эта интерпретация требует, чтобы тождество обратной интерпретации ( ў = y ), и чтобы оба остатка y \ x и x / y интерпретировали условное yx (т.е. ¬ yx ).
  2. Мотивации пример соотношения алгебры зависит от определения бинарного отношения R на множество X как любое подмножество RX ² , где Х ² представляет собой декартов квадрат из X . Множество степеней 2 X ², состоящее из всех бинарных отношений на X, является булевой алгеброй. Хотя 2 X ² можно сделать алгеброй отношений, взяв RS = RS , как в примере (1) выше, стандартная интерпретация • вместо этого x ( RS ) z = ∃ y : xRy.ySz . То есть, упорядоченная пара ( х , г ) принадлежит отношение RS только тогда , когда существует уX такие , что ( х , у ) ∈ R и ( у , г ) ∈ S . Эта интерпретация однозначно определяет R \ S как состоящее из всех пар ( y , z ) таких, что для всех xX , если xRy, то xSz . Двойственно S / R состоит из всех пар ( x , y ) таких, что для всех zX , если yRz, то xSz . Перевод ў = ¬ (у \ ¬ я ) затем устанавливает обратное R ˘ из R как состоящий из всех пар ( у , х ), что ( х , у ) ∈ R .
  3. Важное обобщение предыдущего примера сила набор 2 Е , где ЕX ² любое отношение эквивалентности на множестве X . Это обобщение , потому что Х ² это само отношение эквивалентности, а именно полное отношение , состоящее из всех пар. Хотя 2 E не является подалгеброй 2 X ², когда EX ² (поскольку в этом случае он не содержит отношения X ² , а верхний элемент 1 является E вместо X ² ), он, тем не менее, превращается в алгебру отношений используя те же определения операций. Его важность заключается в определении представимой алгебры отношений как любой алгебры отношений, изоморфной подалгебре алгебры отношений 2 E для некоторого отношения эквивалентности E на некотором множестве. В предыдущем разделе рассказывается больше о соответствующей метаматематике.
  4. Пусть G группа. Тогда набор степеней - это алгебра отношений с очевидными операциями булевой алгебры, композиция, заданная произведением подмножеств групп , обратное - обратным подмножеством ( ), а тождество - одноэлементным подмножеством . Существует вложение гомоморфизма алгебры отношений, при котором каждое подмножество соотносится с отношением . Образ этого гомоморфизма является множество всех правоинвариантных отношений на G .
  5. Если групповая сумма или произведение интерпретируют композицию, групповая инверсия интерпретирует обратное, групповая идентичность интерпретирует I , и если R является взаимно однозначным соответствием , так что R ˘ • R = R • R ˘ = I , то L является группой как ну как моноид . B4 - B7 стали хорошо известные теоремы теории групп , так что RA становится правильное расширение из теории групп , а также булевой алгебры.

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

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

Программное обеспечение

Смотрите также

Сноски

  1. ^ Альфред Тарский (1948) "Аннотация: Проблемы представления для алгебр отношений", Бюллетень AMS 54: 80.
  2. ^ Крис Бринк; Вольфрам Каль; Гюнтер Шмидт (1997). Реляционные методы в информатике . Springer. стр. 4 и 8. ISBN 978-3-211-82971-4.
  3. Перейти ↑ Tarski, A. (1941), p. 87.
  4. ^ Korselt не опубликовал его открытие. Впервые он был опубликован в Leopold Loewenheim (1915) «Über Möglichkeiten im Relativkalkül», Mathematische Annalen 76: 447–470. Переведено как «Возможности в исчислении родственников» Жана ван Хейеноорта , 1967. Справочник по математической логике, 1879–1931 . Гарвардский унив. Пресс: 228–251.

использованная литература

внешние ссылки