Оставшаяся решетка

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

Определение

В математике — результирующая решетка это алгебраическая структура $L = (L, \leq, •, I)$ такая, что

(i) ( L , ≤) является решеткой .

(ii)

(L, •, I)

— моноид .

(iii) Для всех z существует для каждого x наибольший y и для каждого y наибольший x такой, что x • y ⩽ z (свойства остатка).

В (iii) «наибольшее значение y функцией от z и x , обозначается x \ z и называется правой остаткой z », являющееся через x . Думайте об этом как о том, что остается от z справа после «разделения» z слева на x . образом «наибольший x » обозначается z / y и называется левым остатком z Двойственным через y . Эквивалентное, более формальное утверждение (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 \leq (x \lor z) • y$ и аналогично для других операций и их аргументов. Более того, любое неравенство x ≤ y можно эквивалентно выразить в виде уравнения: либо $x \land y = x,$ либо $x \lor y = y$ . Это вместе с уравнениями, аксиоматизирующими решетки и моноиды, затем дает чисто эквациональное определение оставшихся решеток при условии, что необходимые операции присоединены к сигнатуре $(L, \leq, •, I),$ тем самым расширяя ее до $( L , ∧, ∨, •, Я , /, \)$ . При такой организации оставшиеся решетки образуют эквациональный класс или многообразие , гомоморфизмы которого учитывают остатки, а также операции решетки и моноида. Обратите внимание, что дистрибутивность $x • (y \lor z) = (x • y) \lor (x • z)$ и x • 0 = 0 являются следствиями этих аксиом, и поэтому их не нужно делать частью определения. Эта необходимая дистрибутивность • над $\lor,$ вообще говоря, не влечет за собой дистрибутивность $\land$ над $\lor$ , то есть полученная решетка не обязательно должна быть дистрибутивной решеткой. Однако дистрибутивность $\land$ над $\lor$ влечет за собой, когда • и $\land$ — одна и та же операция, частный случай результирующих решеток, называемый алгеброй Гейтинга .

Альтернативные обозначения для 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 (в тот момент), как показано в примере на естественном языке в конце примеров.

Примеры

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

A/B:=\{r\in R\mid rB\subseteq A\}

B\setminus A:=\{r\in R\mid Br\subseteq A\}

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

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

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

Более общий класс примеров дает булева алгебра всех бинарных отношений на множестве X , а именно степенное множество X ², создал результирующую решетку, взяв умножение моноида • в качестве композиции отношений, а единицу моноида в качестве тождественного отношения I на X, состоящего из всех пар ( x , x ) для 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 состоит из всех слов w над Σ таких, что Mw ⊆ L . Левый остаток L / M такой же, как и wM вместо Mw .

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

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

В естественном языке оставшиеся решетки формализуют логику «и», когда она используется с ее некоммутативным значением «и тогда». Установив x = bet , y = win , z = rich , мы можем прочитать x • y ≤ z как «ставка, а затем выигрыш влечет за собой богатство». Согласно аксиомам, это эквивалентно $y \leq x \to z,$ что означает «выигрыш влечет за собой ставку, тогда богатый», а также $x \leq z \leftarrow y,$ что означает «ставка влечет за собой, если когда-либо выиграет, то богатый». Люди легко обнаруживают такие нелогичные высказывания, как «ставка влечет за собой победу, а затем богатство» и «выигрыш влечет за собой, если когда-либо ставка, то богатство», поскольку оба они эквивалентны выдаче желаемого за действительное «выиграй, а затем ставка влечет за собой богатство». ^{[ нужна ссылка ]} Люди не так легко обнаруживают, что закон Пирса (( P → Q ) → P ) → P представляет собой классическую тавтологию , интересную ситуацию, когда люди демонстрируют большее мастерство в неклассических рассуждениях, чем в классических (например, в логике релевантности , закон Пирса это не тавтология). ^{[ соответствующий? ]}

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

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

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

См. также

Ссылки

Уорд, Морган и Роберт П. Дилворт (1939) «Остаточные решетки», Trans. амер. Математика. Соц. 45 : 335–54. Перепечатано в книгах Богарт К., Фриз Р. и Кунг Дж., ред. (1990) Теоремы Дилворта: Избранные статьи Р. П. Дилворта Базель: Birkhäuser.
Николаос Галатос, Питер Джипсен, Томаш Ковальски и Хироакира Оно (2007), Остаточные решетки. Алгебраический взгляд на субструктурную логику , Elsevier, ISBN 978-0-444-52141-5 .