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

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

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

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

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

Следуя Йонссону и Цинакису (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 году. ^[1]

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

B1 : A ∨ B = B ∨ A

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

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

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

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

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

B5 : A • I = A

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

B6 : A ˘˘ = A

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

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

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

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

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

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

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 [ править ]

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

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

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

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

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

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

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

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

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

Q0 : A ˘ • A ≤ I

Q1 : B ˘ • B ≤ I

Q2 : A ˘ • B = 1

По существу эти аксиомы подразумевают , что вселенная имеет (несюръективное) спаривание отношения которого проекция A и B . Это теорема, что каждый QRA является RRA (Доказательство Маддукса, см. 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 . Набор мощности 2 ^{X ²} , состоящий из всех бинарных отношений на X является булевой алгеброй. Хотя 2 ^{X ²} можно сделать алгеброй отношений, взяв R • S = R ∧ S , как в примере (1) выше, стандартная интерпретация • вместо x (R • S ) z = ∃ y : xRy.ySz . То есть, упорядоченная пара ( х , г ) принадлежит отношение R • S только тогдакогда существует у ∈ X такиечто ( х , у ) ∈ R и ( у , г ) ∈ S . Эта интерпретация однозначно определяет R \ S как состоящее из всех пар ( y , z ) таких, что для всех x∈ X , если xRy, то xSz . Двойственно S / R состоит из всех пар ( x , y ) таких, что для всех z ∈ X , если yRz, то xSz . Перевод ў = ¬ (у \ ¬ я ) затем устанавливает обратное R ˘ из R как состоящий из всех пар ( у , х ), что ( х , у ) ∈ R .
3. Важное обобщение предыдущего примера сила набор 2 ^Е , где Е ⊆ X ² любое отношение эквивалентности на множестве X . Это обобщение , потому что Х ² это само отношение эквивалентности, а именно полное отношение , состоящее из всех пар. Хотя 2 ^E не является подалгеброй 2 ^{X ²,} когда E ≠ X ² (поскольку в этом случае он не содержит отношения X ² , верхним элементом 1 является E вместо X ²), тем не менее, она превращается в алгебру отношений с использованием тех же определений операций. Его важность заключается в определении представимой алгебры отношений как любой алгебры отношений, изоморфной подалгебре алгебры отношений 2 ^E для некоторого отношения эквивалентности E на некотором множестве. В предыдущем разделе рассказывается больше о соответствующей метаматематике.
4. Пусть G группа. Тогда набор степеней - это алгебра отношений с очевидными операциями логической алгебры, композиция, заданная произведением подмножеств групп , обратное - обратным подмножеством ( ) и тождество - одноэлементным подмножеством . Существует вложение гомоморфизма алгебры отношений, при котором каждое подмножество соотносится с отношением . Образ этого гомоморфизма является множество всех правоинвариантных отношений на G .${\ displaystyle 2 ^ {G}}$${\displaystyle A^{-1}=\{a^{-1}\mid a\in A\}}$${\displaystyle \{e\}}$${\displaystyle 2^{G}}$${\displaystyle 2^{G\times G}}$${\displaystyle A\subset G}$${\displaystyle R_{A}=\{(g,h)\in G\times G\mid h\in Ag\}}$
5. Если групповая сумма или произведение интерпретируют композицию, групповая инверсия интерпретирует обратное, групповая идентичность интерпретирует I , и если R является взаимно однозначным соответствием , так что R ˘ • R = R • R ˘ = I , ^[3] тогда L является группы , а также моноид . B4 - B7 стали хорошо известные теоремы теории групп , так что RA становится правильное расширение из теории групп , а также булевой алгебры.

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

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

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

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

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

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

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

• Карнап, Рудольф (1958). Введение в символическую логику и ее приложения . Dover Publications.
• Гивант, Стивен (2006). «Исчисление отношений как основа математики». Журнал автоматизированных рассуждений . 37 (4): 277–322. DOI : 10.1007 / s10817-006-9062-х .
• Халмос, PR (1960). Наивная теория множеств . Ван Ностранд.
• Хенкин, Леон ; Тарский, Альфред ; Монах, JD (1971). Цилиндрические алгебры, часть 1 . Северная Голландия.
• Хенкин, Леон ; Тарский, Альфред ; Монк, JD (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.

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

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