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

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

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

• 1 Определение
  • 1.1 Аксиомы
• 2 Выражение свойств бинарных отношений в RA
• 3 Выразительная сила
  • 3.1 Алгебры Q-отношений
• 4 Примеры
• 5 Исторические замечания
• 6 Программное обеспечение
• 7 См. Также
• 8 Сноски
• 9 Ссылки
• 10 Внешние ссылки

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

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

Аксиомы

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

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

B1: A ∨ B = B ∨ A

B2: A ∨ (B ∨ C) = (A ∨ B) ∨ C

B3: (A ∨ B) ∨ (A ∨ B) = A

Эта аксиоматизация булевой алгебры обусловлена Хантингтон (1933). Обратите внимание, что встреча подразумеваемой булевой алгебры не является оператором • (даже несмотря на то, что она распределяет по $\vee \; \{\backslash \; displaystyle\; \backslash \; vee\}$, как это делает встреча), и не является 1 в булевой алгебре константа I .

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

B4: A • (B • C) = ( A • B) • C

B5: A • I = A

Унарный converse () ˘ - инволюция по отношению к композиции :

B6: A ˘˘ = A

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

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

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

B8: (A∨B) ˘ = A˘∨B˘

B9: (A∨B) • C = (A • C) ∨ (B • C)

B10 - эквациональная форма Тарского факта, открытого Огастесом Де Морганом, что A • B ≤ C $\leftrightarrow \; \{\backslash \; displaystyle\; \backslash \; leftrightarrow\}$A˘ • C ≤ B $\leftrightarrow \; \{\backslash \; displaystyle\; \backslash \; leftrightarrow\}$C • B˘ ≤ A.

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

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

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

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

метаматематика из RA подробно обсуждается в Tarski and Givant (1987) и более кратко в Givant (2006).

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

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

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

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

RA является алгеброй Q-отношений (QRA ), если в дополнение к B1-B10, существуют A и B такие, что (Tarski and Givant 1987: §8.4):

Q0: A˘ • A ≤ I

Q1: B˘ • B ≤ I

Q2: A˘ • B = 1

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

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

1. Любую булеву алгебру можно превратить в RA, интерпретируя конъюнкцию как композицию (моноидное умножение •), то есть x • y определяется как x∧y. Эта интерпретация требует, чтобы тождество обратной интерпретации (ў = y), и чтобы оба остатка y \ x и x / y интерпретировали условное y → x (т.е. ¬y∨x).

2. Мотивающий пример алгебры отношений зависит от определения бинарного отношения R на множестве X как любое подмножество R ⊆ X², где X² - ​​декартов квадрат X. Множество степеней 2, состоящее из всех двоичных отношения на X - булева алгебра. В то время как 2 можно сделать алгеброй отношений, взяв R • S = R∧S, как в примере (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. Перевод ў = ¬ (y \ ¬ I ) затем устанавливает, что R˘, обратное R, состоит из всех пар (y, x) таких, что (x, y) ∈ R.

3. Важным обобщением предыдущего примера является набор степеней 2, где E ⊆ X² - ​​любое отношение эквивалентности на множестве X. Это обобщение, потому что X² само по себе является отношением эквивалентности, а именно полным отношением, состоящим из всех пары. Хотя 2 не является подалгеброй 2, когда E ≠ X² (поскольку в этом случае он не содержит отношения X², а верхний элемент 1 является E вместо X²), тем не менее он превращается в алгебру отношений с использованием тех же определений операции. Его важность заключается в определении представимой алгебры отношений как любой алгебры отношений, изоморфной подалгебре алгебры отношений 2 для некоторого отношения эквивалентности E на некотором множестве. В предыдущем разделе рассказывается больше о соответствующей метаматематике.

4. Пусть $G\; \{\backslash \; displaystyle\; G\}$будет группой. Тогда набор степеней $2\; G\; \{\backslash \; displaystyle\; 2\; ^\; \{G\}\}$представляет собой алгебру отношений с очевидными операциями логической алгебры, состав которых задается произведением групповых подмножеств, обратное - обратным подмножеством ($A\; -\; 1\; =\; \{a\; -\; 1\; \mid \; a\; \in \; A\}\; \{\backslash \; displaystyle\; A\; ^\; \{-\; 1\}\; =\; \backslash \; \{a\; ^\; \{-\; 1\}\; \backslash \; mid\; a\; \backslash \; in\; A\; \backslash \}\}$), а идентичность - подмножеством одноэлементов $\{e\}\; \{\backslash \; displaystyle\; \backslash \; \{e\; \backslash \}\}$. Существует вложение гомоморфизма алгебры отношений $2\; G\; \{\backslash \; displaystyle\; 2\; ^\; \{G\}\}$в $2\; G\; \times \; G\; \{\backslash \; displaystyle\; 2\; ^\; \{G\; \backslash \; times\; G\}\}$, которое отправляет каждое подмножество $A\; \subset \; G\; \{\backslash \; displaystyle\; A\; \backslash \; subset\; G\}$в отношение $RA\; =\; \{(g,\; h)\; \in \; G\; \times \; G\; \mid \; h\; \in \; A\; g\; \}\; \{\backslash \; displaystyle\; R\_\; \{A\}\; =\; \backslash \; \{(g,\; h)\; \backslash \; in\; G\; \backslash \; times\; G\; \backslash \; mid\; h\; \backslash \; in\; Ag\; \backslash \}\}$. Образ этого гомоморфизма - это множество всех правоинвариантных отношений на $G\; \{\backslash \; displaystyle\; G\}$.

5. Если групповая сумма или произведение интерпретирует состав, групповое обратное интерпретирует обратное, групповая идентичность интерпретирует I, и если R является взаимно-однозначным соответствием, так что R˘ • R = R • R˘ = I, тогда L является группой, а также моноидом. B4-B7, ставшими хорошо известными теоремами группы теория, так что RA становится правильным расширением как теории групп, так и булевой алгебры.

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

• RelMICS / реляционные методы в компьютерных науках, поддерживаемое Вольфрамом Калем
• Карстен Синц: ARA / автоматическое средство доказательства теорем для алгебр отношений
• Стеф Йустен, Алгебра отношений как язык программирования с использованием компилятора амперсанда, Журнал логических и алгебраических методов в программировании, том 100, апрель 2018 г., страницы 113-129. (см. также https://ampersandtarski.gitbook.io/documentat ion )

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

• Карнап, Рудольф (1958). Введение в символическую логику и ее приложения. Dover Publications.
• Гивант, Стивен (2006). «Исчисление отношений как основа математики». Журнал автоматизированных рассуждений. 37 (4): 277–322. doi : 10.1007 / s10817-006-9062-x.
• Халмос, П. Р. (1960). Наивная теория множеств. Ван Ностранд.
• Хенкин, Леон ; Тарский, Альфред ; Монк, Дж. Д. (1971). Цилиндрические алгебры, часть 1. Северная Голландия.
• Хенкин, Леон ; Тарский, Альфред ; Монк, Дж. Д. (1985). Цилиндрические алгебры, часть 2. Северная Голландия.
• Hirsch, R.; Ходкинсон, И. (2002). Алгебра отношений по играм. Исследования по логике и основам математики. 147 . Elsevier Science.
• Йонссон, Бьярни ; Цинакис, Константин (1993). «Алгебры отношений как булевы алгебры с делениями». Универсальная алгебра. 30 (4): 469–78. doi : 10.1007 / BF01195378.
• Мэддакс, Роджер (1991). «Происхождение алгебр отношений в развитии и аксиоматизации исчисления отношений» (PDF). Studia Logica. 50 (3–4): 421–455. CiteSeerX 10.1.1.146.5668. doi : 10.1007 / BF00370681.
• Мэддакс, Роджер (2006). Алгебры отношений. Исследования по логике и основам математики. 150 . Elsevier Science. ISBN 9780444520135.
• Шейн, Борис М. (1970) «Алгебры отношений и полугруппы функций», Форум полугруппы 1: 1–62
• Шмидт, Гюнтер (2010). Реляционная математика. Издательство Кембриджского университета.
• Суппес, Патрик (1972) [1960]. "Глава 3". Аксиоматическая теория множеств (переиздание Дувра). Ван Ностранд.
• Тарский, Альфред (1941). «Об исчислении отношений». Журнал символической логики. 6 (3): 73–89. DOI : 10.2307 / 2268577. JSTOR 2268577.
• Тарский, Альфред; Гивант, Стивен (1987). Формализация теории множеств без переменных. Провиденс Р.И.: Американское математическое общество. ISBN 9780821810415.

• Йоджи АКАМА, Ясуо Кавахара и Хитоши Фурусава, «Построение аллегории на основе алгебры отношений и теорем представления. "
• Ричард Берд, Oege de Мур, Пол Хугендейк, "Универсальное программирование с помощью отношений и функторов. "
• RP де Фрейтас и Виана, "Результат полноты для алгебры отношений со связующими. "
• Питер Джипсен :
  • Алгебры отношений
  • "Основы отношений и алгебра Клини. "
  • "Компьютерные исследования алгебр отношений. "
  • "Система Генцена и разрешимость для остаточных решеток. "
• Воган Пратт :
  • "Истоки исчисления бинарных отношений. " Исторический анализ.
  • "Второе исчисление бинарных отношений. "
• Присс, Uta:
  • "Интерпретация алгебры соотношений FCA. "
  • "Алгебра отношений и FCA «Ссылки на публикации и программное обеспечение
• Каль, Вольфрам и Гюнтер Шмидт : Изучение (конечных) алгебр отношений с помощью инструментов, написанных на Haskell. и Инструменты алгебры отношений с помощью Haskell из Университета Макмастера.