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

В математике и абстрактной алгебре — алгебра отношений это остаточная булева алгебра, расширенная инволюцией , называемой обратной , унарной операцией . Мотивирующим примером алгебры отношений является алгебра 2 ^{Х ²} всех бинарных отношений на множестве X , то есть подмножествах декартова квадрата X ², где R • S интерпретируется как обычная композиция бинарных отношений R и S , а обратное отношение R - как обратное отношение .

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

Определение [ править ]

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

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

Аксиомы [ править ]

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

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

B1 :

А \lor B = B \lor А

B2 :

А \lor (B \lor C) знак равно (А \lor B) \lor C

Б3 :

(А - \lor Б) - \lor (А - \lor Б -) - = А

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

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

B4 :

А • (В • С) = (А • В) • С

B5 :

А • Я = А

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

B6 :

А ​​˘˘ = А

B7 :

(A • B)˘ = B ˘ • A ˘

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

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

B8 :

(А \lor B)˘ = А ˘ \lor B ˘

B9 :

(А \lor B) • C знак равно (А • C) \lor (B • C)

B10 — это эквациональная форма Тарского того факта, открытого Огастесом Де Морганом , что A • B ≤ C ⁻ $\leftrightarrow$ А ˘ • C ≤ B ⁻ $\leftrightarrow$ С • В ˘ ≤ А ⁻.

B10 :

(A ˘ • (A • B) -) \lor Б - = Б -

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

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

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

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

R это	Если и только если :
Функциональный	$Р ˘ • Р \leq Я$
Левый итог	$I \leq R • R ˘$ ( R ˘ сюръективен)
Функция	функциональный и левототальный.
инъективный	$R • R ˘ \leq I$ ( R ˘ функционален)
Сюръективный	$I \leq R ˘ • R$ ( R ˘ — тотально слева)
Биекция	$R ˘ • R = R • R ˘ = I$ (Инъективная сюръективная функция)
Переходный	$Р • Р \leq Р$
Рефлексивный	$я \leq Р$
Coreflexive	$р \leq я$
Бездумный	$р \land я = 0$
Симметричный	$Р ˘ = Р$
антисимметричный	$Р \land Р ˘ \leq Я$
Асимметричный	$р \land р ˘ = 0$
Сильно связаны	$р \lor р ˘ знак равно 1$
Подключено	$я \lor р \lor р ˘ знак равно 1$
Идемпотент	$Р • Р = Р$
Предварительный заказ	R транзитивен и рефлексивен.
Эквивалентность	R — симметричный предпорядок.
Частичный заказ	R — антисимметричный предпорядок.
Общий заказ	R сильно связен и имеет частичный порядок.
Строгий частичный порядок	R транзитивен и иррефлексивен.
Строгий общий порядок	R связен и имеет строгий частичный порядок.
Плотный	$Р \land Я - \leq (Р \land I -) • (R \land I -)$ .

Выразительная сила [ править ]

Метаматематика . РА ) подробно обсуждается в работах Тарского и Гиванта (1987) и более кратко в Гиванте (2006

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

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

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

Алгебры Q-отношений [ править ]

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

Q0 :

А ˘ • А \leq I

Q1 :

B ˘ • B \leq I

Q2 :

А ˘ • B = 1

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

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

Примеры [ править ]

Любую булеву алгебру можно превратить в RA, интерпретируя конъюнкцию как композицию (моноидное умножение •), т.е. x • y определяется как x ∧ y . Эта интерпретация требует, чтобы обратная интерпретация тождества ( ў = y ) и чтобы обе остатки y \ x и x / y интерпретировали условное y → x (т. е. ¬ y ∨ x ).
Мотивирующий пример алгебры отношений зависит от определения бинарного отношения R на множестве X как любого подмножества $R \subseteq X. 2$ , где $Х 2$ является квадратом X . декартовым Силовой набор 2 ^{Х ²} состоящая из всех бинарных отношений на X, является булевой алгеброй. Пока 2 ^{Х ²} можно сделать алгеброй отношений, взяв $R • S = R \land S$ , как в примере (1) выше, стандартная интерпретация • вместо $x (R • S) z = \exists y : xRy.ySz$ . То есть упорядоченная пара $(x, z)$ принадлежит отношению R • S только тогда, когда существует $y$ в $X$ такой, что $x, y) \in R$ и $(y, z) \in S.$ ( Эта интерпретация однозначно определяет R \ S как состоящую из всех пар $(y, z)$ таких, что для всех $x \in X$ , если xRy , то xSz . Двойственным образом S / R состоит из всех пар $(x, y)$ таких, что для всех z в X , если yRz , то xSz . Тогда перевод $ў = ¬( y \¬ I )$ устанавливает обратное R ˘ к R как состоящее из всех пар $(y, x)$ таких, что $(x, y) \in R$ .
Важным обобщением предыдущего примера является набор мощности 2. ^И где $E \subseteq X 2$ любое отношение эквивалентности на множестве X. — Это обобщение, поскольку $X 2$ само по себе является отношением эквивалентности, а именно полным отношением, состоящим из всех пар. Пока 2 ^И не является подалгеброй 2 ^{Х ²} когда $Е \neq X 2$ (поскольку в этом случае оно не содержит отношения $X 2$ , верхний элемент 1 — E вместо $X 2$ ), тем не менее, она превращается в алгебру отношений с использованием тех же определений операций. Ее важность заключается в определении представимой алгебры отношений как любой алгебры отношений, изоморфной подалгебре алгебры отношений 2. ^И для некоторого отношения эквивалентности E на некотором множестве. В предыдущем разделе больше говорится о соответствующей метаматематике.
Пусть $G$ — группа . Тогда набор мощности $2^{G}$ — алгебра отношений с очевидными операциями булевой алгебры, композиция задается произведением групповых подмножеств , обратное — обратным подмножеством ( $A^{-1}=\{a^{-1}\!:a\in A\}$ ) и идентичность по одноэлементному подмножеству $\{e\}$ . Существует вложение гомоморфизма алгебры отношений $2^{G}$ в $2^{G\times G}$ который отправляет каждое подмножество $A\subset G$ к отношению $R_{A}=\{(g,h)\in G\times G:h\in Ag\}$ . Образом этого гомоморфизма является множество всех правоинвариантных отношений на $G$ .
Если групповая сумма или произведение интерпретирует композицию, обратная группа интерпретирует обратную интерпретацию, групповая идентичность интерпретирует $I$ , и если R является взаимно-однозначным соответствием , так что $R ˘ • R = R • R ˘ = I$ , ^[3] тогда L — группа и моноид . B4 – B7 становятся хорошо известными теоремами теории групп , так что RA становится собственным расширением теории групп , а также булевой алгебры.

Исторические замечания [ править ]

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

Программное обеспечение [ править ]

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

См. также [ править ]

Сноски [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

[1] Альфред Тарский (1948) «Резюме: проблемы представления алгебр отношений», Бюллетень AMS 54: 80.

[BrinkKahl1997-2] Крис Бринк; Вольфрам Каль; Гюнтер Шмидт (1997). Реляционные методы в информатике . Спрингер. стр. 4 и 8. ISBN 978-3-211-82971-4 .

[3] Тарский, А. (1941), с. 87.

[4] Корсельт не опубликовал свое открытие. Впервые он был опубликован Леопольдом Левенхаймом (1915) «Über Möglichkeiten im Relativkalkül», Mathematische Annalen 76: 447–470. Переведено как «О возможностях исчисления родственников» у Жана ван Хейеноорта , 1967. Справочник по математической логике, 1879–1931 . Гарвардский университет. Пресса: 228–251.

[1]

[2]

[3]

[4]