В абстрактной алгебре решетка с делениями - это алгебраическая структура, которая одновременно является решеткой x ≤ y и моноидом x • y, допускающим операции x \ z и z / y , примерно аналогичные делению или импликации, когда x • y рассматривается как умножение или соединение соответственно. Эти операции, называемые соответственно правой и левой невязками, совпадают, когда моноид коммутативен. Общая концепция была представлена Морганом Уордом иРоберт П. Дилворт в 1939 году. Примеры, некоторые из которых существовали до появления общей концепции, включают булевы алгебры , алгебры Гейтинга , булевы алгебры с делением , алгебры отношений и MV-алгебры . Residuated полурешетки опускают операцию встретиться ∧, например Клини алгебры и алгебра действий .
Определение [ править ]
В математике решетка с делениями - это алгебраическая структура L = ( L , ≤, •, I ) такая, что
- (i) ( L , ≤) - решетка .
- (ii) ( L , •, I ) - моноид .
- (iii) Для любого z существует наибольшее значение y для каждого x , а для каждого y наибольшее значение x такое, что x • y ≤ z (свойства остатка).
В формуле (III), «величайшие у », является функцией г и х , обозначается й \ г и называется правая Остаточными из г по х . Думайте об этом как о том, что осталось от z справа после «деления» z слева на x . Двойственно, то «наибольшая х » обозначаются г / у и называются левым остаточным из г на у . Эквивалентное, более формальное утверждение пункта (iii), в котором эти операции используются для обозначения этих наибольших значений:
(iii) 'для всех x , y , z в L , y ≤ x \ z ⇔ x • y ≤ z ⇔ x ≤ z / y .
Как следует из обозначений, остатки представляют собой форму частного. Точнее, для данного x в L унарные операции x • и x \ являются соответственно нижним и верхним сопряженными связями Галуа на L и двойственно для двух функций • y и / y . По тем же рассуждениям, которые применимы к любой связности Галуа, у нас есть еще одно определение невязок, а именно,
- x • ( x \ y ) ≤ y ≤ x \ ( x • y ) и
- ( y / x ) • x ≤ y ≤ ( y • x ) / x ,
вместе с требованием монотонности x • y по x и y . (При аксиоматизации с использованием (iii) или (iii) монотонность становится теоремой и, следовательно, не требуется в аксиоматизации.) Это дает смысл, в котором функции x • и x \ являются псевдообратными или сопряженными друг другу, а также для • х и / х .
Это последнее определение чисто в терминах неравенств, где отмечается, что монотонность может быть аксиоматизирована как x • y ≤ ( x ∨ z ) • y и аналогично для других операций и их аргументов. Более того, любое неравенство x ≤ y может быть эквивалентно выражено в виде уравнения: либо x ∧ y = x, либо x ∨ y = y . Это вместе с уравнениями, аксиоматизирующими решетки и моноиды, затем дает чисто эквациональное определение решеток с делениями при условии, что необходимые операции присоединены к сигнатуре ( L, ≤, •, I ), расширяя его до ( L , ∧, ∨, •, I , /, \). Организованные таким образом решетки с аппроксимацией образуют эквациональный класс или многообразие , гомоморфизмы которого учитывают остатки, а также операции решетки и моноида. Обратите внимание, что дистрибутивность x • ( y ∨ z ) = ( x • y ) ∨ ( x • z ) и x• 0 = 0 являются следствием этих аксиом и поэтому не должны быть частью определения. Эта необходимая дистрибутивность • над, как правило, не влечет за собой дистрибутивности над, то есть решетка с делением не обязательно должна быть дистрибутивной решеткой. Однако дистрибутивность над влечет за собой, когда • и ∧ - одна и та же операция, частный случай решеток с аппроксимацией, называемый алгеброй Гейтинга .
Альтернативные обозначения для x • y включают x ◦ y , x ; y ( алгебра отношений ) и x ⊗ y ( линейная логика ). Альтернативы для I включают e и 1 '. Альтернативные обозначения для остатков: x → y для x \ y и y ← x для y / x, предполагаемое сходством между вычетом и импликацией в логике, при этом умножение моноида понимается как форма конъюнкции, которая не обязательно должна быть коммутативной. Когда моноид коммутативен, два остатка совпадают. Когда он не коммутативен, интуитивное значение моноида как конъюнкции и остатков как импликаций может быть понято как имеющее временное качество: x • y означает x, а затем y , x → y означает, что x (в прошлом), затем y (теперь ), а y ← x означает когда-либо x (в будущем)затем y (в то время), как показано на примере естественного языка в конце примеров.
Примеры [ править ]
Одним из первоначальных мотивов для изучения residuated решеток была решетка (двусторонних) идеалы одного кольца . Принимая во внимание кольца R , идеалы R , обозначат Id ( R ), образует полную решетку с множеством пересечений , действующими в качестве операции встречается и «идеальными» Кроме того , действующими в качестве операции соединения. Операция моноида • задается «идеальным умножением», и элемент R из Id ( R ) действует как единичный элемент для этой операции. Для двух идеалов A и B в Id ( R ) невязки имеют вид
Стоит отметить , что {0} / B и B \ {0} являются соответственно левый и правый уничтожители из B . Это residuation связано с проводником (или переносчика ) в коммутативной алгебре записывается как ( A : B ) = A / B . Одно из различий в использовании состоит в том, что B не обязательно должен быть идеалом R : это может быть просто подмножество.
Булевы алгебры и алгебры Гейтинга представляют собой коммутативные решетки с аппроксимацией, в которых x • y = x ∧ y ( поэтому единица I является верхним элементом 1 алгебры), и обе невязки x \ y и y / x являются одной и той же операцией, а именно импликацией x → у . Второй пример является довольно общим, поскольку алгебры Гейтинга включают в себя все конечные дистрибутивные решетки , а также все цепочки или полные порядки, образующие полную решетку., например, единичный интервал [0,1] в вещественной строке или целые числа и ± .
Структура ( Z , min , max , +, 0, -, -) (целые числа с вычитанием для обоих остатков) представляет собой коммутативную решетку с остатками, такая что единица моноида не является наибольшим элементом (действительно, нет наименьшего или наибольшее целое число), и умножение моноида не является операцией пересечения решетки. В этом примере неравенства являются равенствами, потому что - (вычитание) не просто присоединенное или псевдообратное к +, но истинное обратное. Любая полностью упорядоченная группа при добавлении, такая как рациональные или действительные числа, может быть заменена целыми числами в этом примере. Неотрицательная часть любого из этих примеров является примером при условии, что min и max поменяны местами, а - заменяется наmonus , определяемый (в данном случае) так, что x - y = 0, когда x ≤ y, а в противном случае - обычное вычитание.
Более общий класс примеров дается булевой алгеброй всех бинарных отношений на множестве X , а именно множеством степеней X 2 , сделанным решеткой с делениями, приняв умножение моноида как композицию отношений, а единицу моноида как тождество отношение Я на X , состоящее из всех пар ( х , х ) для й в X . Учитывая два отношения R и S на X , правая аппроксимируемость R \ S группы S по R- это бинарное отношение, такое что x ( R \ S ) y выполняется только тогда, когда для всех z в X , zRx влечет zSy (обратите внимание на связь с импликацией). Левая невязка является зеркальным отображением этого: y ( S / R ) x выполняется тогда, когда для всех z в X , xRz влечет ySz .
Это можно проиллюстрировать с помощью бинарных отношений <и> на {0,1}, в которых 0 <1 и 1> 0 являются единственными отношениями, которые имеют место. Тогда x (> \ <) y выполняется только тогда, когда x = 1, в то время как x (</>) y выполняется только тогда, когда y = 0, показывая, что вычет <by> различается в зависимости от того, остаемся ли мы справа или слева. . Это различие является следствием разницы между <•> и> • <, где единственные отношения, которые имеют место: 0 (<•>) 0 (поскольку 0 <1> 0) и 1 (> • <) 1 (поскольку 1 > 0 <1). Если бы мы выбрали ≤ и ≥ вместо <и>, ≥ \ ≤ и ≤ / ≥ были бы одинаковыми, потому что ≤ • ≥ = ≥ • ≤,оба из которых всегда выполняются между всеми x и y (посколькуx ≤1≥ y и x ≥0≤ y ).
Булева алгебра 2 Σ * всех формальных языков над алфавитом (множеством) Σ образует решетку с делениями, моноидное умножение которой является конкатенацией языков LM, а моноидной единицей I является язык {ε}, состоящий только из пустой строки ε. Правый остаточный M \ L состоит из всех слов ш над а, что Mw ⊆ L . Левая невязка L / M совпадает с wM вместо Mw .
Решетка с аппроксимацией всех бинарных отношений на X конечна только тогда, когда X конечно, и коммутативна только тогда, когда X имеет не более одного элемента. Когда X пусто алгебра является вырожденным Булева алгебра , в которой 0 = 1 = I . Решетка с аппроксимацией всех языков на Σ коммутативна только тогда, когда Σ имеет не более одной буквы. Оно конечно только тогда, когда Σ пусто, состоящее из двух языков 0 (пустой язык {}) и моноидной единицы I = {ε} = 1.
Примеры, образующие булеву алгебру, обладают особыми свойствами, рассматриваемыми в статье о булевых алгебрах с аппроксимацией .
В естественном языке решетки с делениями формализуют логику «и», когда они используются в некоммутативном значении «а затем». Устанавливая x = ставка , y = выигрыш , z = богатство , мы можем читать x • y ≤ z как «ставка, а затем выигрыш влечет за собой богатство». По аксиомам это эквивалентно y ≤ x → z, что означает «выигрыш влечет за собой ставку, затем богатую», а также x ≤ z ← yчто означает "ставка влечет за собой выигрыш, если он когда-либо приносит прибыль". Люди легко обнаруживают такие несоответствия, как «ставка влечет за собой выигрыш, затем богатый» и «выигрыш влечет за собой ставку, если когда-либо делает ставку, то богатую», поскольку оба они эквивалентны принятию желаемого за действительное: «выигрыш и затем ставка влечет за собой богатство». Люди не так легко обнаруживают, что закон Пирса (( P → Q ) → P ) → P является классической тавтологией , интересной ситуацией, когда люди демонстрируют больший опыт в неклассических рассуждениях, чем в классических (например, в логике релевантности , закон Пирса это не тавтология).
Вырожденная полурешетка [ править ]
Residuated полурешетка определяется почти одинаково для residuated решеток, опуская только операцию встретиться ∧. Таким образом, это алгебраическая структура L = (L,, •, 1, /, \), удовлетворяющая всем уравнениям решетки с делениями, как указано выше, за исключением тех, которые содержат вхождение символа. Вариант определения x ≤ y как x ∧ y = x тогда недоступен, остается только другой вариант x ∨ y = y (или любой его эквивалент).
Любую решетку с делением можно превратить в полурешетку с делением, просто опуская ∧. Вычисленные полурешетки возникают в связи с алгебрами действия , которые являются аппроксимируемыми полурешетками, которые также являются алгебрами Клини , для которых обычно не требуется.
См. Также [ править ]
- Quantale
- Остаточное отображение
- Субструктурная логика
- Выведенная булева алгебра
Ссылки [ править ]
- Уорд, Морган и Роберт П. Дилворт (1939) "Остаточные решетки", Trans. Амер. Математика. Soc. 45 : 335–54. Перепечатано в Bogart, K, Freese, R., and Kung, J., eds. (1990) Теоремы Дилворта: Избранные статьи Р. П. Дилворта Базель: Биркхойзер.
- Николаос Галатос, Питер Джипсен, Томаш Ковальски и Хироакира Оно (2007), Остаточные решетки. Алгебраический взгляд на субструктурную логику , Elsevier, ISBN 978-0-444-52141-5 .
