WikiDer > Остаточная решетка

Residuated lattice

В абстрактная алгебра, а остаточная решетка является алгебраическая структура это одновременно решетка Икс ≤ у и моноид Икс•у который допускает операции Икс\z и z/у, примерно аналогично делению или импликации, когда Икс•у рассматривается как умножение или соединение соответственно. Эти операции, называемые соответственно правой и левой невязками, совпадают, когда моноид коммутативен. Общая концепция была введена Морган Уорд и Роберт П. Дилворт в 1939 году. Примеры, некоторые из которых существовали до появления общей концепции, включают Булевы алгебры, Гейтинговые алгебры, остаточные булевы алгебры, алгебры отношений, и MV-алгебры. Остаточные полурешетки опустите операцию встречи ∧, например Клини алгебры и алгебры действий.

Определение

В математика, а остаточная решетка является алгебраическая структура L = (L, ≤, •, я) такие, что

(я) (L, ≤) является решетка.

(ii) (L, •, я) это моноид.

(iii) Для всех z существует для каждого Икс величайший у, и для каждого у величайший Икс, так что Икс•у ≤ z (остаточные свойства).

В (iii) "наибольшая у", будучи функцией z и Икс, обозначается Икс\z и назвал правый остаток из z к Икс. Думайте об этом как о том, что осталось от z справа после "деления" z слева от Икс. Вдвойне "величайший Икс"обозначается z/у и назвал левый остаток из z к у. Эквивалентное, более формальное утверждение пункта (iii), в котором эти операции используются для именования этих наибольших значений:

(iii) 'для всех Икс, у, z в L, у ≤ Икс\z ⇔ Икс•у ≤ z ⇔ Икс ≤ z/у.

Как следует из обозначений, остатки представляют собой форму частного. Точнее, для данного Икс в L, унарные операции Икс• и Икс - соответственно нижнее и верхнее сопряжение Связь Галуа на L, и дважды для двух функций •у и /у. По тем же соображениям, что и для любой связности Галуа, у нас есть еще одно определение невязок, а именно,

Икс•(Икс\у) ≤ у ≤ Икс\(Икс•у), и

(у/Икс)•Икс ≤ у ≤ (у•Икс)/Икс,

вместе с требованием, чтобы Икс•у быть монотонным в Икс и у. (При аксиоматизации с использованием (iii) или (iii) 'монотонность становится теоремой и, следовательно, не требуется при аксиоматизации.) Это дает смысл, в котором функции Икс• и Икс являются псевдообратными или сопряженными друг другу, а также для •Икс и /Икс.

Это последнее определение дано исключительно в терминах неравенств с учетом того, что монотонность может быть аксиоматизирована как Икс•у ≤ (Икс∨z)•у и аналогично для других операций и их аргументов. Более того, любое неравенство Икс ≤ у может быть выражено эквивалентно в виде уравнения, либо Икс∧у = Икс или Икс∨у = у. Это вместе с уравнениями, аксиоматизирующими решетки и моноиды, затем дает чисто эквациональное определение решеток с делениями при условии, что необходимые операции присоединены к сигнатуре (L, ≤, •, я), расширив его до (L, ∧, ∨, •, я, /, ). При такой организации решетки с делениями образуют эквациональный класс или разнообразие, чьи гомоморфизмы учитывают невязки, а также операции решетки и моноида. Обратите внимание, что распределительность Икс•(у ∨ z) = (Икс•у) ∨ (Икс•z) и Икс• 0 = 0 являются следствиями этих аксиом и поэтому не должны быть частью определения. Эта необходимая дистрибутивность • над, как правило, не влечет за собой дистрибутивности над ∨, то есть решетка с делениями не обязательно должна быть дистрибутивной решеткой. Однако дистрибутивность над влечет за собой, когда • и ∧ являются одной и той же операцией, частный случай решеток с делением, называемый Алгебра Гейтинга.

Альтернативные обозначения для Икс•у включают Икс◦у, Икс;у (алгебра отношений), и Икс⊗у (линейная логика). Альтернативы для я включают е и 1 '. Альтернативные обозначения остатков: Икс → у за Икс\у и у ← Икс за у/Икс, предполагаемое сходством между вычетом и импликацией в логике, при этом умножение моноида понимается как форма конъюнкции, которая не обязательно должна быть коммутативной. Когда моноид коммутативен, два остатка совпадают. Когда они не коммутативны, интуитивное значение моноида как конъюнкции и остатков как импликаций может быть понято как имеющее временное качество: Икс•у означает Икс а потом у, Икс → у означает имел Икс (в прошлом) тогда у (сейчас), и у ← Икс означает если даже Икс (в будущем) тогда у (в то время), как показано на примере естественного языка в конце примеров.

Примеры

Одной из первоначальных мотиваций для изучения решеток с делениями была решетка (двусторонних) идеалы из звенеть. Учитывая кольцо р, идеалы р, обозначается Id (р), образует полную решетку с пересечением множеств, действующим как операция пересечения, и «идеальным сложением», действующим как операция соединения. Операция моноида • задается «идеальным умножением», а элемент р Id (р) выступает в качестве идентификатора для этой операции. Учитывая два идеала А и B в Id (р), невязки даются

{ Displaystyle A / B: = {р in R mid rB substeq A }}

{ Displaystyle B setminus A: = {r in R mid Br substeq A }}

Стоит отметить, что {0} /B и B {0} - соответственно левый и правый аннигиляторы из B. Этот остаток связан с дирижер (или же транспортер) в коммутативная алгебра написано как (А:B)=А/B. Одно различие в использовании заключается в том, что B не обязательно быть идеалом р: это может быть просто подмножество.

Булевы алгебры и Гейтинговые алгебры коммутативные решетки с делениями, в которых Икс•у = Икс∧у (откуда единица я является верхним элементом 1 алгебры) и обе невязки Икс\у и у/Икс это та же операция, а именно импликация Икс → у. Второй пример является довольно общим, так как алгебры Гейтинга включают в себя все конечные распределительные решетки, а также все цепочки или общее количество заказов формирование полная решетка, например, единичный интервал [0,1] в вещественной строке или целые числа и ± ${ displaystyle infty}$ .

Структура (Z, мин, Максимум, +, 0, -, -) (целые числа с вычитанием для обоих остатков) представляет собой коммутативную решетку с остатками, такая что единица моноида не является наибольшим элементом (действительно, нет наименьшего или наибольшего целого числа), и умножение моноид не является встречной операцией решетки. В этом примере неравенства являются равенствами, потому что - (вычитание) - это не просто присоединенное или псевдообратное к +, но истинное обратное. Любая полностью упорядоченная группа при добавлении, такая как рациональные или действительные числа, может быть заменена целыми числами в этом примере. Неотрицательная часть любого из этих примеров - это предоставленный пример мин и Максимум меняются местами и - заменяется на монус, определенная (в данном случае) так, что Икс-у = 0, когда Икс ≤ у в противном случае - обычное вычитание.

Более общий класс примеров дается Булева алгебра из всех бинарные отношения на съемочной площадке Икс, а именно набор мощности Икс², сделал решетку с делениями, приняв умножение моноида • за композицию отношений, а единицу моноида за тождественное отношение я на Икс состоящий из всех пар (Икс,Икс) за Икс в Икс. Учитывая два отношения р и S на Икс, правая невязка р\S из S к р такое бинарное отношение, что Икс(р\S)у держится только тогда, когда для всех z в Икс, zRx подразумевает zSy (обратите внимание на связь с импликацией). Левый остаток является зеркальным отображением этого: у(S/р)Икс держится только тогда, когда для всех z в Икс, xRz подразумевает ySz.

Это можно проиллюстрировать с помощью бинарных отношений <и> на {0,1}, в которых 0 <1 и 1> 0 - единственные отношения, которые имеют место. потом Икс(>\<)у держится только когда Икс = 1, а Икс(</>)у держится только когда у = 0, показывая, что вычет <по> различается в зависимости от того, делаем ли мы вычет справа или слева. Это различие является следствием разницы между <•> и> • <, где единственные отношения, которые имеют место: 0 (<•>) 0 (поскольку 0 <1> 0) и 1 (> • <) 1 (поскольку 1 > 0 <1). Если бы мы выбрали ≤ и ≥ вместо <и>, ≥ ≤ и ≤ / ≥ были бы одинаковыми, потому что ≤ • ≥ = ≥ • ≤, оба из которых всегда выполняются между всеми Икс и у (поскольку Икс≤1≥у и Икс≥0≤у).

Булева алгебра 2^{Σ *} из всех формальные языки над алфавитом (множеством) Σ образует решетку с делениями, моноидное умножение которой является конкатенацией языков LM и чья моноидная единица я - это язык {ε}, состоящий только из пустой строки ε. Правильный остаток M\L состоит из всех слов ш над Σ такое, что Mw ⊆ L. Левый остаток L/M то же самое с wM на месте Mw.

Решетка с вычетом всех бинарных отношений на Икс конечно, когда Икс конечна и коммутативна только тогда, когда Икс имеет не более одного элемента. Когда Икс пусто, алгебра - это вырожденная булева алгебра, в которой 0 = 1 = я. Решетка всех языков на Σ коммутативна только тогда, когда Σ имеет не более одной буквы. Оно конечно только тогда, когда Σ пусто, состоящее из двух языков 0 (пустой язык {}) и моноидной единицы я = {ε} = 1.

Примеры, образующие булеву алгебру, обладают особыми свойствами, рассмотренными в статье о остаточные булевы алгебры.

В естественный язык решетки с остатками формализуют логику «и», когда используются вместе с некоммутативным значением «а затем». Настройка Икс = держать пари, у = победить, z = богатые, мы можем прочитать Икс•у ≤ z как «сделай ставку, а потом выиграй - богат» По аксиомам это эквивалентно у ≤ Икс→z что означает «выигрыш влечет за собой ставку, затем богатую», а также Икс ≤ z←у что означает «ставка влечет за собой выигрыш, если он когда-либо приносит прибыль». Люди легко обнаруживают такие несоответствия, как «ставка влечет за собой выигрыш, затем богатый» и «выигрыш влечет за собой ставку, если когда-либо, то богатый», поскольку оба они эквивалентны принятию желаемого за действительное: «выигрыш, а затем ставка влечет за собой богатство». Люди не так легко замечают, что Закон Пирса ((п→Q)→п)→п это классический тавтология, интересная ситуация, когда люди демонстрируют больше навыков неклассического мышления, чем классического (например, в логика релевантности, Закон Пирса не тавтология).

Остаточная полурешетка

А остаточная полурешетка для решеток с делением определяется почти тождественно, опуская только операцию пересечения ∧. Таким образом, это алгебраическая структура L = (L, ∨, •, 1, /, ), удовлетворяющее всем остаточным уравнениям решетки, как указано выше, за исключением тех, которые содержат вхождение символа. Вариант определения Икс ≤ у так как Икс∧у = Икс тогда недоступен, остается только другой вариант Икс∨у = у (или любой его эквивалент).

Любую решетку с делением можно превратить в полурешетку с делением, просто опуская ∧. Вырожденные полурешетки возникают в связи с алгебры действий, которые являются полурешетками с делением, которые также являются Клини алгебры, для которого ∧ обычно не требуется.

Navigation

Navigation

Themenportale

WikiDer > Остаточная решетка

Содержание

Определение

Примеры

Остаточная полурешетка

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

Рекомендации