Полукольцо

Алгебраическое кольцо, которое не обязательно должно иметь аддитивные отрицательные элементы

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

Наименьшее полукольцо, не являющееся кольцом, — это двухэлементная булева алгебра , например, с логической дизъюнкцией в качестве сложения. Мотивирующим примером, который не является ни кольцом, ни решеткой, является множество натуральных чисел (включая ноль) при обычном сложении и умножении. Полукольца широко распространены, поскольку подходящая операция умножения возникает как функциональная композиция эндоморфизмов над любым коммутативным моноидом . ${\displaystyle \lor }$ ${\displaystyle \mathbb {N} }$

Терминология

Некоторые авторы определяют полукольца без требования наличия или . Это делает аналогию между кольцом и полукольцом , с одной стороны, и группой и полугруппой , с другой стороны, более гладкой. Эти авторы часто используют rig для концепции, определенной здесь. ^{[1] [a]} Это возникло как шутка, предполагающая, что rig — это кольца без отрицательных элементов . (Сродни использованию rng для обозначения ar i ng без мультипликативного тождества .) ${\displaystyle 0}$ ${\displaystyle 1}$

Термин диоид (для «двойного моноида») использовался для обозначения полуколец или других структур. Он был использован Кунцманном в 1972 году для обозначения полукольца. ^[2] (Иногда его также используют для естественно упорядоченных полуколец ^[3], но этот термин также использовался для идемпотентных подгрупп Бачелли и др. в 1992 году. ^[4] )

Определение

Полукольцо — это множество , снабженное двумя бинарными операциями , называемыми сложением и умножением, такое, что: ^{[5] [6] [7]} ${\displaystyle R}$ ${\displaystyle +}$ ${\displaystyle \cdot ,}$

• ${\displaystyle (R,+)}$— это коммутативный моноид с единичным элементом, называемым : ${\displaystyle 0}$
  • ${\displaystyle (a+b)+c=a+(b+c)}$
  • ${\displaystyle 0+a=a}$
  • ${\displaystyle a+0=a}$
  • ${\displaystyle a+b=b+a}$
• ${\displaystyle (R,\,\cdot \,)}$представляет собой моноид с единичным элементом, называемым : ${\displaystyle 1}$
  • ${\displaystyle (a\cdot b)\cdot c=a\cdot (b\cdot c)}$
  • ${\displaystyle 1\cdot a=a}$
  • ${\displaystyle a\cdot 1=a}$

Далее, с обеими операциями связаны следующие аксиомы:

• При умножении любой элемент слева и справа уничтожается аддитивным тождеством:
  • ${\displaystyle 0\cdot a=0}$
  • ${\displaystyle a\cdot 0=0}$
• Умножение слева и справа распределяется относительно сложения:
  • ${\displaystyle a\cdot (b+c)=(a\cdot b)+(a\cdot c)}$
  • ${\displaystyle (b+c)\cdot a=(b\cdot a)+(c\cdot a)}$

Обозначение

Символ обычно опускается из записи, то есть просто пишется ${\displaystyle \cdot }$ ${\displaystyle a\cdot b}$ ${\displaystyle ab.}$

Аналогично, порядок операций является обычным, в котором применяется до . То есть обозначает . ${\displaystyle \cdot }$ ${\displaystyle +}$ ${\displaystyle a+b\cdot c}$ ${\displaystyle a+(b\cdot c)}$

Для устранения неоднозначности можно написать или , чтобы подчеркнуть, к какой структуре относятся рассматриваемые единицы. ${\displaystyle 0_{R}}$ ${\displaystyle 1_{R}}$

Если — элемент полукольца и , то -кратное умножение самого себя обозначается , и аналогично записывается -кратное сложение. ${\displaystyle x\in R}$ ${\displaystyle n\in {\mathbb {N} }}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle x^{n}}$ ${\displaystyle x\,n:=x+x+\cdots +x}$ ${\displaystyle n}$

Строительство новых полуколец

Нулевое кольцо с базовым множеством — это полукольцо, называемое тривиальным полукольцом. Эту тривиальность можно охарактеризовать с помощью и поэтому, когда говорят о нетривиальных полукольцах, часто молчаливо предполагается, как если бы это была дополнительная аксиома. Теперь, если полукольцо любое, есть несколько способов определить новые. ${\displaystyle \{0\}}$ ${\displaystyle 0=1}$ ${\displaystyle 0\neq 1}$

Как уже отмечалось, натуральные числа с их арифметической структурой образуют полукольцо. Взятие нуля и образа операции-последователя в полукольце , т.е. множества вместе с унаследованными операциями, всегда является подполукольцом . ${\displaystyle {\mathbb {N} }}$ ${\displaystyle R}$ ${\displaystyle \{x\in R\mid x=0_{R}\lor \exists p.x=p+1_{R}\}}$ ${\displaystyle R}$

Если — коммутативный моноид, композиция функций обеспечивает умножение для формирования полукольца: Множество эндоморфизмов образует полукольцо, где сложение определяется из поточечного сложения в . Нулевой морфизм и тождество являются соответствующими нейтральными элементами. Если с полукольцом, мы получаем полукольцо, которое можно связать с квадратными матрицами с коэффициентами в , полукольцо матриц с использованием обычных правил сложения и умножения матриц. Если задано и полукольцо, всегда является полукольцом. Оно, как правило, некоммутативно, даже если было коммутативным. ${\displaystyle (M,+)}$ ${\displaystyle \operatorname {End} (M)}$ ${\displaystyle M\to M}$ ${\displaystyle M}$ ${\displaystyle M=R^{n}}$ ${\displaystyle R}$ ${\displaystyle n\times n}$ ${\displaystyle {\mathcal {M}}_{n}(R)}$ ${\displaystyle R}$ ${\displaystyle n\in {\mathbb {N} }}$ ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}_{n}(R)}$ ${\displaystyle R}$

Расширения Дорро : Если — полукольцо, то с поточечным сложением и умножением, заданным определяет другое полукольцо с мультипликативной единицей . Очень похоже, если — любое подполукольцо из , можно также определить полукольцо на , просто заменив повторяющееся сложение в формуле на умножение. Действительно, эти конструкции работают даже при более свободных условиях, поскольку структура на самом деле не обязана иметь мультипликативную единицу. ${\displaystyle R}$ ${\displaystyle R\times {\mathbb {N} }}$ ${\displaystyle \langle x,n\rangle \bullet \langle y,m\rangle :=\langle x\cdot y+(x\,m+y\,n),n\cdot m\rangle }$ ${\displaystyle 1_{R\times {\mathbb {N} }}:=\langle 0_{R},1_{\mathbb {N} }\rangle }$ ${\displaystyle N}$ ${\displaystyle R}$ ${\displaystyle R\times N}$ ${\displaystyle R}$

Полукольца без нулевой суммы в некотором смысле дальше всего от того, чтобы быть кольцами. Если полукольцо, можно присоединить новый ноль к базовому множеству и таким образом получить такое полукольцо без нулевой суммы, которое также не имеет делителей нуля . В частности, теперь и старое полукольцо на самом деле не является подполукольцом. Затем можно продолжать и присоединять новые элементы «сверху» по одному за раз, всегда соблюдая при этом ноль. Эти две стратегии также работают при более свободных условиях. Иногда при выполнении этих построений используются обозначения соответственно . ${\displaystyle 0'}$ ${\displaystyle 0\cdot 0'=0'}$ ${\displaystyle -\infty }$ ${\displaystyle +\infty }$

Присоединение нового нуля к тривиальному полукольцу, таким образом, приводит к другому полукольцу, которое может быть выражено в терминах логических связок дизъюнкции и конъюнкции: . Следовательно, это наименьшее полукольцо, которое не является кольцом. Явно, оно нарушает аксиомы кольца как для всех , т.е. не имеет аддитивного обратного. В самодвойственном определении ошибка связана с . (Это не следует путать с кольцом , сложение которого функционирует как xor .) В модели фон Неймана натуральных чисел , , и . Двухэлементное полукольцо может быть представлено в терминах теоретико-множественного объединения и пересечения как . Теперь эта структура фактически все еще образует полукольцо, когда заменяется любым обитаемым множеством вообще. ${\displaystyle \langle \{0,1\},+,\cdot ,\langle 0,1\rangle \rangle =\langle \{\bot ,\top \},\lor ,\land ,\langle \bot ,\top \rangle \rangle }$ ${\displaystyle \top \lor P=\top }$ ${\displaystyle P}$ ${\displaystyle 1}$ ${\displaystyle \bot \land P=\bot }$ ${\displaystyle \mathbb {Z} _{2}}$ ${\displaystyle \veebar }$ ${\displaystyle 0_{\omega }:=\{\}}$ ${\displaystyle 1_{\omega }:=\{0_{\omega }\}}$ ${\displaystyle 2_{\omega }:=\{0_{\omega },1_{\omega }\}={\mathcal {P}}1_{\omega }}$ ${\displaystyle \langle {\mathcal {P}}1_{\omega },\cup ,\cap ,\langle \{\},1_{\omega }\rangle \rangle }$ ${\displaystyle 1_{\omega }}$

Идеалы полукольца , с их стандартными операциями на подмножестве, образуют решеточно-упорядоченное, простое и безсуммовое полукольцо. Идеалы находятся в биекции с идеалами . Набор левых идеалов (и также правых идеалов) также имеет большую часть этой алгебраической структуры, за исключением того, что тогда не функционирует как двустороннее мультипликативное тождество. ${\displaystyle R}$ ${\displaystyle {\mathcal {M}}_{n}(R)}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$

Если — полукольцо и — обитаемое множество , обозначает свободный моноид , а формальные многочлены над его словами образуют другое полукольцо. Для небольших множеств образующие элементы традиционно используются для обозначения полиномиального полукольца. Например, в случае синглтона, такого что , пишут . Свободные от нулевых сумм подполукольца из можно использовать для определения подполуколец из . ${\displaystyle R}$ ${\displaystyle A}$ ${\displaystyle A^{*}}$ ${\displaystyle R[A^{*}]}$ ${\displaystyle A=\{X\}}$ ${\displaystyle A^{*}=\{\varepsilon ,X,X^{2},X^{3},\dots \}}$ ${\displaystyle R[X]}$ ${\displaystyle R}$ ${\displaystyle R[A^{*}]}$

Если задано множество , не обязательно состоящее из одного элемента, то, присоединив элемент по умолчанию к множеству, лежащему в основе полукольца, можно определить полукольцо частичных функций от до . ${\displaystyle A}$ ${\displaystyle R}$ ${\displaystyle A}$ ${\displaystyle R}$

При наличии вывода на полукольце другая операция " ", выполняющая функцию , может быть определена как часть нового умножения на , в результате чего получается еще одно полукольцо. ${\displaystyle {\mathrm {d} }}$ ${\displaystyle R}$ ${\displaystyle \bullet }$ ${\displaystyle X\bullet y=y\bullet X+{\mathrm {d} }(y)}$ ${\displaystyle R[X]}$

Вышеизложенное ни в коем случае не является исчерпывающим перечнем систематических конструкций.

Производные

Дифференциациями на полукольце являются отображения с и . ${\displaystyle R}$ ${\displaystyle {\mathrm {d} }\colon R\to R}$ ${\displaystyle {\mathrm {d} }(x+y)={\mathrm {d} }(x)+{\mathrm {d} }(y)}$ ${\displaystyle {\mathrm {d} }(x\cdot y)={\mathrm {d} }(x)\cdot y+x\cdot {\mathrm {d} }(y)}$

Например, если — единичная матрица и , то подмножество , заданное матрицами с , является полукольцом с выводом . ${\displaystyle E}$ ${\displaystyle 2\times 2}$ ${\displaystyle U={\bigl (}{\begin{smallmatrix}0&1\\0&0\end{smallmatrix}}{\bigr )}}$ ${\displaystyle {\mathcal {M}}_{2}(R)}$ ${\displaystyle a\,E+b\,U}$ ${\displaystyle a,b\in R}$ ${\displaystyle a\,E+b\,U\mapsto b\,U}$

Характеристики

Основным свойством полуколец является то, что они не являются ни левым, ни правым делителем нуля , а также квадратами самих себя, т. е. имеют . ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle u^{2}=u}$

Некоторые примечательные свойства унаследованы от моноидных структур: Аксиомы моноида требуют существования единицы, и поэтому множество, лежащее в основе полукольца, не может быть пустым. Кроме того, 2-арный предикат , определенный как , здесь определенный для операции сложения, всегда составляет правое каноническое отношение предпорядка . Рефлексивность подтверждается тождеством. Кроме того, всегда допустимо, и поэтому ноль является наименьшим элементом относительно этого предпорядка. Рассматривая его для коммутативного сложения в частности, различие «право» можно проигнорировать. В неотрицательных целых числах , например, это отношение является антисимметричным и сильно связанным , и, таким образом, фактически (нестрогим) полным порядком . ${\displaystyle x\leq _{\text{pre}}y}$ ${\displaystyle \exists d.x+d=y}$ ${\displaystyle y\leq _{\text{pre}}y}$ ${\displaystyle 0\leq _{\text{pre}}y}$ ${\displaystyle \mathbb {N} }$

Ниже обсуждаются более условные свойства.

Полуполя

Любое поле также является полуполем , которое в свою очередь является полукольцом, в котором также существуют мультипликативные обратные элементы.

Кольца

Любое поле также является кольцом , которое в свою очередь является полукольцом, в котором также существуют аддитивные обратные. Обратите внимание, что полукольцо не имеет такого требования, т. е. оно требует только коммутативный моноид , а не коммутативную группу . Дополнительное требование для самого кольца уже подразумевает существование мультипликативного нуля. Этот контраст также является причиной того, что для теории полуколец мультипликативный нуль должен быть указан явно.

Здесь , аддитивное обратное к , квадраты к . Поскольку аддитивные разности всегда существуют в кольце, является тривиальным бинарным отношением в кольце. ${\displaystyle -1}$ ${\displaystyle 1}$ ${\displaystyle 1}$ ${\displaystyle d=y-x}$ ${\displaystyle x\leq _{\text{pre}}y}$

Коммутативные полукольца

Полукольцо называется коммутативным полукольцом, если также коммутативно и умножение. ^[8] Его аксиомы можно сформулировать кратко: оно состоит из двух коммутативных моноидов и на одном множестве таких, что и . ${\displaystyle \langle +,0\rangle }$ ${\displaystyle \langle \cdot ,1\rangle }$ ${\displaystyle a\cdot 0=0}$ ${\displaystyle a\cdot (b+c)=a\cdot b+a\cdot c}$

Центр полукольца является подполукольцом, а его коммутативность эквивалентна принадлежности к собственному центру .

Коммутативное полукольцо натуральных чисел является исходным объектом среди себе подобных, то есть существует единственное сохраняющее структуру отображение в любое коммутативное полукольцо. ${\displaystyle {\mathbb {N} }}$

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

Упорядоченные полукольца

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

Если задан строгий полный порядок (иногда его также называют линейным порядком или псевдопорядком в конструктивной формулировке), то по определению положительные и отрицательные элементы удовлетворяют соответственно . По иррефлексивности строгого порядка, если — левый делитель нуля, то — ложь. Неотрицательные элементы характеризуются как , что затем записывается как . ${\displaystyle 0<x}$ ${\displaystyle x<0}$ ${\displaystyle s}$ ${\displaystyle s\cdot x<s\cdot y}$ ${\displaystyle \neg (x<0)}$ ${\displaystyle 0\leq x}$

В общем случае строгий полный порядок может быть отрицаемым для определения связанного частичного порядка. Асимметрия первого проявляется как . Фактически в классической математике последний является (нестрогим) полным порядком и таким, что подразумевает . Аналогично, если задан любой (нестрогий) полный порядок, его отрицание является иррефлексивным и транзитивным , и эти два свойства, найденные вместе, иногда называются строгим квазипорядком. Классически это определяет строгий полный порядок – действительно, строгий полный порядок и полный порядок могут быть определены в терминах друг друга. ${\displaystyle x<y\to x\leq y}$ ${\displaystyle 0\leq x}$ ${\displaystyle x=0\lor 0<x}$

Напомним, что " ", определенное выше, является тривиальным в любом кольце. Существование колец, допускающих нетривиальный нестрогий порядок, показывает, что они не обязательно должны совпадать с " ". ${\displaystyle \leq _{\text{pre}}}$ ${\displaystyle \leq _{\text{pre}}}$

Аддитивно идемпотентные полукольца

Полукольцо, в котором каждый элемент является аддитивным идемпотентом , то есть для всех элементов , называется (аддитивно) идемпотентным полукольцом . ^[9] Достаточно установить . Имейте в виду, что иногда это просто называют идемпотентным полукольцом, независимо от правил умножения. ${\displaystyle x+x=x}$ ${\displaystyle x}$ ${\displaystyle 1+1=1}$

В таком полукольце эквивалентно и всегда образует частичный порядок, здесь теперь обозначаемый . В частности, здесь . Таким образом, аддитивно идемпотентные полукольца не имеют нулевой суммы и, действительно, единственное аддитивно идемпотентное полукольцо, которое имеет все аддитивные обратные, — это тривиальное кольцо, и поэтому это свойство специфично для теории полуколец. Сложение и умножение уважают порядок в том смысле, что подразумевает , и, кроме того, подразумевает также как , для всех и . ${\displaystyle x\leq _{\text{pre}}y}$ ${\displaystyle x+y=y}$ ${\displaystyle x\leq y}$ ${\displaystyle x\leq 0\leftrightarrow x=0}$ ${\displaystyle x\leq y}$ ${\displaystyle x+t\leq y+t}$ ${\displaystyle s\cdot x\leq s\cdot y}$ ${\displaystyle x\cdot s\leq y\cdot s}$ ${\displaystyle x,y,t}$ ${\displaystyle s}$

Если аддитивно идемпотентно, то и многочлены от . ${\displaystyle R}$ ${\displaystyle R[X^{*}]}$

Полукольцо, на базовом множестве которого имеется решетчатая структура, является решеточно-упорядоченным, если сумма совпадает с пересечением, , а произведение лежит под соединением . Решеточно-упорядоченное полукольцо идеалов на полукольце не обязательно является дистрибутивным относительно решетчатой ​​структуры. ${\displaystyle x+y=x\lor y}$ ${\displaystyle x\cdot y\leq x\land y}$

Более строго, чем просто аддитивная идемпотентность, полукольцо называется простым тогда и только тогда, когда для всех . Тогда также и для всех . Здесь тогда функции, родственные аддитивно бесконечному элементу. Если — аддитивно идемпотентное полукольцо, то с унаследованными операциями — его простое подполукольцо. Примером аддитивно идемпотентного полукольца, которое не является простым, является тропическое полукольцо на с 2-арной максимальной функцией относительно стандартного порядка в качестве сложения. Его простое подполукольцо тривиально. ${\displaystyle x+1=1}$ ${\displaystyle x}$ ${\displaystyle 1+1=1}$ ${\displaystyle x\leq 1}$ ${\displaystyle x}$ ${\displaystyle 1}$ ${\displaystyle R}$ ${\displaystyle \{x\in R\mid x+1=1\}}$ ${\displaystyle {\mathbb {R} }\cup \{-\infty \}}$

C -полукольцо — это идемпотентное полукольцо со сложением, определенным над произвольными множествами.

Аддитивно идемпотентное полукольцо с идемпотентным умножением, , называется аддитивно и мультипликативно идемпотентным полукольцом , но иногда также просто идемпотентным полукольцом. Коммутативные простые полукольца с этим свойством — это в точности ограниченные дистрибутивные решетки с единственным минимальным и максимальным элементом (которые затем являются единицами). Алгебры Гейтинга являются такими полукольцами, а булевы алгебры — частным случаем. ${\displaystyle x^{2}=x}$

Далее, если заданы две ограниченные дистрибутивные решетки, то существуют конструкции, приводящие к коммутативным аддитивно-идемпотентным полукольцам, которые сложнее, чем просто прямая сумма структур.

Числовые ряды

В модели кольца можно определить нетривиальный предикат положительности и предикат как , который составляет строгий полный порядок, который удовлетворяет таким свойствам, как , или классически закону трихотомии . С его стандартным сложением и умножением эта структура образует строго упорядоченное поле , которое является Дедекиндово-полным . По определению , все свойства первого порядка, доказанные в теории действительных чисел, также доказуемы в разрешимой теории действительного замкнутого поля . Например, здесь является взаимоисключающим с . ${\displaystyle {\mathbb {R} }}$ ${\displaystyle 0<x}$ ${\displaystyle x<y}$ ${\displaystyle 0<(y-x)}$ ${\displaystyle \neg (x<0\lor 0<x)\to x=0}$ ${\displaystyle x<y}$ ${\displaystyle \exists d.y+d^{2}=x}$

Но помимо просто упорядоченных полей, четыре свойства, перечисленные ниже, также действительны во многих подполукольцах , включая рациональные числа, целые числа, а также неотрицательные части каждой из этих структур. В частности, неотрицательные действительные числа, неотрицательные рациональные числа и неотрицательные целые числа являются такими полукольцами. Первые два свойства аналогичны свойству, действительному в идемпотентных полукольцах: Трансляция и масштабирование уважают эти упорядоченные кольца в том смысле, что сложение и умножение в этом кольце подтверждают ${\displaystyle {\mathbb {R} }}$

• ${\displaystyle (x<y)\,\to \,x+t<y+t}$
• ${\displaystyle (x<y\land 0<s)\,\to \,s\cdot x<s\cdot y}$

В частности, и поэтому возведение элементов в квадрат сохраняет положительность. ${\displaystyle (0<y\land 0<s)\to 0<s\cdot y}$

Обратите внимание еще на два свойства, которые всегда действительны в кольце. Во-первых, тривиально для любого . В частности, существование положительной аддитивной разности можно выразить как ${\displaystyle P\,\to \,x\leq _{\text{pre}}y}$ ${\displaystyle P}$

• ${\displaystyle (x<y)\,\to \,x\leq _{\text{pre}}y}$

Во-вторых, при наличии трихотомического порядка ненулевые элементы аддитивной группы разбиваются на положительные и отрицательные элементы, причем операция инверсии перемещается между ними. При , все квадраты доказано неотрицательны. Следовательно, нетривиальные кольца имеют положительную мультипликативную единицу, ${\displaystyle (-1)^{2}=1}$

• ${\displaystyle 0<1}$

Обсудив строгий порядок, следует, что и и т.д. ${\displaystyle 0\neq 1}$ ${\displaystyle 1\neq 1+1}$

Дискретно упорядоченные полукольца

В теории порядка есть несколько противоречивых понятий дискретности. При наличии некоторого строгого порядка на полукольце одно из таких понятий задается как положительное и охватывающее , т. е. отсутствие элемента между единицами, . В настоящем контексте порядок будет называться дискретным , если это выполняется и, кроме того, все элементы полукольца неотрицательны, так что полукольцо начинается с единиц. ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle x}$ ${\displaystyle \neg (0<x\land x<1)}$

Обозначим через теорию коммутативного, дискретно упорядоченного полукольца, также подтверждающую четыре приведенных выше свойства, связывающие строгий порядок с алгебраической структурой. Все ее модели имеют модель в качестве своего начального сегмента, а неполнота Гёделя и неопределимость по Тарскому уже применимы к . Неотрицательные элементы коммутативного, дискретно упорядоченного кольца всегда подтверждают аксиомы . Таким образом, немного более экзотическая модель теории задается положительными элементами в кольце полиномов , с предикатом положительности для , определенным в терминах последнего ненулевого коэффициента, , и как указано выше. В то время как доказывает все -предложения , которые истинны относительно , ​​за пределами этой сложности можно найти простые такие утверждения, которые независимы от . Например, в то время как -предложения, истинные относительно , ​​по-прежнему истинны для другой только что определенной модели, проверка полинома демонстрирует -независимость -утверждения о том, что все числа имеют вид или (« нечетные или четные »). Демонстрация того, что также может быть дискретно упорядочено, демонстрирует, что -утверждение для ненулевого числа («никаких рациональных квадратов, равных ») является независимым. Аналогично, анализ для демонстрирует независимость некоторых утверждений о факторизации, верных в . Существуют характеристики простоты, которые не подходят для числа . ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle {\mathbb {Z} }[X]}$ ${\displaystyle p={\textstyle \sum }_{k=0}^{n}a_{k}X^{k}}$ ${\displaystyle 0<p:=(0<a_{n})}$ ${\displaystyle p<q:=(0<q-p)}$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle X}$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle \Pi _{2}}$ ${\displaystyle 2q}$ ${\displaystyle 2q+1}$ ${\displaystyle {\mathbb {Z} }[X,Y]/(X^{2}-2Y^{2})}$ ${\displaystyle \Pi _{1}}$ ${\displaystyle x^{2}\neq 2y^{2}}$ ${\displaystyle x}$ ${\displaystyle 2}$ ${\displaystyle {\mathbb {Z} }[X,Y,Z]/(XZ-Y^{2})}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle 2}$

В другом направлении из любой модели можно построить упорядоченное кольцо, которое затем имеет элементы, отрицательные относительно порядка, который все еще дискретен в том смысле, что охватывает . Для этого определяется класс эквивалентности пар из исходного полукольца. Грубо говоря, кольцо соответствует разностям элементов в старой структуре, обобщая способ, которым исходное кольцо может быть определено из . Это, по сути, добавляет все обратные элементы, и тогда предпорядок снова тривиален в том, что . ${\displaystyle {\mathsf {PA}}^{-}}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \forall x.x\leq _{\text{pre}}0}$

За пределами размера двухэлементной алгебры ни одно простое полукольцо не начинается с единиц. Дискретно упорядоченное также контрастирует, например, со стандартным порядком на полукольце неотрицательных рациональных чисел , которое плотно между единицами. Для другого примера, может быть упорядочено, но не дискретно. ${\displaystyle {\mathbb {Q} }_{\geq 0}}$ ${\displaystyle {\mathbb {Z} }[X]/(2X^{2}-1)}$

Натуральные числа

${\displaystyle {\mathsf {PA}}^{-}}$плюс математическая индукция дает теорию, эквивалентную арифметике Пеано первого порядка . Теория также, как известно, не категорична , но , конечно, является предполагаемой моделью. доказывает, что нет делителей нуля и что она свободна от нулевой суммы, и поэтому ни одна ее модель не является кольцом. ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle {\mathsf {PA}}}$

Стандартная аксиоматизация более лаконична, и теория ее порядка обычно рассматривается в терминах нестрогого " ". Однако простое удаление принципа мощной индукции из этой аксиоматизации не оставляет работоспособной алгебраической теории. Действительно, даже арифметика Робинсона , которая удаляет индукцию, но добавляет обратно предшествующий постулат существования, не доказывает аксиому моноида . ${\displaystyle {\mathsf {PA}}}$ ${\displaystyle \leq _{\text{pre}}}$ ${\displaystyle {\mathsf {Q}}}$ ${\displaystyle \forall y.(0+y=y)}$

Полные полукольца

Полное полукольцо — это полукольцо, для которого аддитивный моноид является полным моноидом , что означает, что оно имеет бесконечную операцию суммы для любого набора индексов и что должны выполняться следующие (бесконечные) законы дистрибутивности: ^{[10] [11] [12]} ${\displaystyle \Sigma _{I}}$ ${\displaystyle I}$

${\displaystyle {\textstyle \sum }_{i\in I}{\left(a\cdot a_{i}\right)}=a\cdot \left({\textstyle \sum }_{i\in I}{a_{i}}\right),\qquad {\textstyle \sum }_{i\in I}{\left(a_{i}\cdot a\right)}=\left({\textstyle \sum }_{i\in I}{a_{i}}\right)\cdot a.}$

Примерами полного полукольца являются множество степеней моноида относительно объединения и матричное полукольцо над полным полукольцом. ^[13] Для коммутативных, аддитивно идемпотентных и простых полуколец это свойство связано с вычетными решетками .

Непрерывные полукольца

Непрерывное полукольцо определяется аналогичным образом как такое, для которого моноид сложения является непрерывным моноидом . То есть, частично упорядоченным со свойством наименьшей верхней границы , и для которого сложение и умножение уважают порядок и супремумы. Полукольцо с обычным сложением, умножением и расширенным порядком является непрерывным полукольцом. ^[14] ${\displaystyle \mathbb {N} \cup \{\infty \}}$

Любое непрерывное полукольцо является полным: ^[10] это можно рассматривать как часть определения. ^[13]

Звездчатые полукольца

Звездное полукольцо (иногда пишется как звездное полукольцо ) — это полукольцо с дополнительным унарным оператором , ^{[9] [11] [15] [16]} удовлетворяющим ${\displaystyle {}^{*}}$

${\displaystyle a^{*}=1+aa^{*}=1+a^{*}a.}$

Алгебра Клини — это звездное полукольцо с идемпотентным сложением и некоторыми дополнительными аксиомами. Они важны в теории формальных языков и регулярных выражений . ^[11]

Полные звездчатые полукольца

В полном звездном полукольце оператор звезды ведет себя скорее как обычная звезда Клини : для полного полукольца мы используем оператор бесконечной суммы, чтобы дать обычное определение звезды Клини: ^[11]

${\displaystyle a^{*}={\textstyle \sum }_{j\geq 0}{a^{j}},}$

где

${\displaystyle a^{j}={\begin{cases}1,&j=0,\\a\cdot a^{j-1}=a^{j-1}\cdot a,&j>0.\end{cases}}}$

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

полукольцо Конвея

Полукольцо Конвея — это звездное полукольцо, удовлетворяющее уравнениям «сумма-звезда» и «произведение-звезда»: ^{[9] [17]}

${\displaystyle {\begin{aligned}(a+b)^{*}&=\left(a^{*}b\right)^{*}a^{*},\\(ab)^{*}&=1+a(ba)^{*}b.\end{aligned}}}$

Каждое полное звездное полукольцо также является полукольцом Конвея, ^[18] но обратное утверждение неверно. Примером полукольца Конвея, которое не является полным, является множество расширенных неотрицательных рациональных чисел с обычным сложением и умножением (это модификация примера с расширенными неотрицательными вещественными числами, приведенного в этом разделе, путем исключения иррациональных чисел). ^[11] Итеративное полукольцо — это полукольцо Конвея, удовлетворяющее аксиомам группы Конвея, ^[9] ассоциированное Джоном Конвеем с группами в звездных полукольцах. ^[19] ${\displaystyle \mathbb {Q} _{\geq 0}\cup \{\infty \}}$

Примеры

• По определению любое кольцо и любое полуполе также являются полукольцом.
• Неотрицательные элементы коммутативного дискретно упорядоченного кольца образуют коммутативное дискретно (в определенном выше смысле) упорядоченное полукольцо. Оно включает в себя неотрицательные целые числа . ${\displaystyle \mathbb {N} }$
• Также неотрицательные рациональные числа , а также неотрицательные действительные числа образуют коммутативные, упорядоченные полукольца. ^{[20] [21] [22]} Последнее называетсяВероятностное полукольцо .^[6]Ни кольца, ни дистрибутивные решетки не являются таковыми. Эти примеры также имеют мультипликативные обратные.
• Новые полукольца могут быть условно построены из существующих, как описано. Расширенные натуральные числа с добавлением и умножением расширены так, что . ^[21] ${\displaystyle \mathbb {N} \cup \{\infty \}}$ ${\displaystyle 0\cdot \infty =0}$
• Множество многочленов с натуральными коэффициентами, обозначенное образует коммутативное полукольцо. Фактически, это свободное коммутативное полукольцо с одним генератором. Также могут быть определены многочлены с коэффициентами в других полукольцах, как обсуждалось. ${\displaystyle \mathbb {N} [x],}$ ${\displaystyle \{x\}.}$
• Неотрицательные конечные дроби , в позиционной системе счисления по данному основанию , образуют подполукольцо рациональных чисел. Имеем ‍ , если делит . Для множество является кольцом всех конечных дробей по основанию и плотно в . ${\displaystyle {\tfrac {\mathbb {N} }{b^{\mathbb {N} }}}:=\left\{mb^{-n}\mid m,n\in \mathbb {N} \right\}}$ ${\displaystyle b\in \mathbb {N} }$ ${\displaystyle {\tfrac {\mathbb {N} }{b^{\mathbb {N} }}}\subseteq {\tfrac {\mathbb {N} }{c^{\mathbb {N} }}}}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle |b|>1}$ ${\displaystyle {\tfrac {\mathbb {Z} _{0}}{b^{\mathbb {Z} _{0}}}}:={\tfrac {\mathbb {N} }{b^{\mathbb {N} }}}\cup \left(-{\tfrac {\mathbb {N} _{0}}{b^{\mathbb {N} }}}\right)}$ ${\displaystyle b,}$ ${\displaystyle \mathbb {Q} }$
• Логарифмическое полукольцо на сложении, заданное с нулевым элементом умножения и единичным элементом ^[6] ${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$ ${\displaystyle x\oplus y=-\log \left(e^{-x}+e^{-y}\right)}$ ${\displaystyle +,}$ ${\displaystyle +\infty ,}$ ${\displaystyle 0.}$

Аналогично, при наличии соответствующего порядка с нижним элементом,

• Тропические полукольца определяются по-разному. Полукольцо max-plus — это коммутативное полукольцо, выступающее в качестве полукольцевого сложения (тождество ) и обычного сложения (тождество 0), выступающего в качестве полукольцевого умножения. В альтернативной формулировке тропическое полукольцо есть и min заменяет max в качестве операции сложения. ^[23] Связанная версия имеет в качестве базового множества. ^{[6] [10]} Они являются активной областью исследований, связывающих алгебраические многообразия с кусочно-линейными структурами. ^[24] ${\displaystyle \mathbb {R} \cup \{-\infty \}}$ ${\displaystyle \max(a,b)}$ ${\displaystyle -\infty }$ ${\displaystyle \mathbb {R} \cup \{\infty \},}$ ${\displaystyle \mathbb {R} \cup \{\pm \infty \}}$
• Полукольцо Лукасевича : замкнутый интервал со сложением и , заданный взятием максимального из аргументов ( ), и умножением и , заданным , появляется в многозначной логике . ^[11] ${\displaystyle [0,1]}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \max(a,b)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \max(0,a+b-1)}$
• Полукольцо Витерби также определено над базовым множеством и имеет максимум в качестве своего сложения, но его умножение является обычным умножением действительных чисел. Оно появляется в вероятностном анализе . ^[11] ${\displaystyle [0,1]}$

Обратите внимание, что . Подробнее об аддитивно идемпотентных полукольцах, ${\displaystyle \max(x,x)=x}$

• Совокупность всех идеалов данного полукольца образует полукольцо относительно сложения и умножения идеалов.
• Любая ограниченная дистрибутивная решетка является коммутативным полукольцом относительно join и meet. Булева алгебра является частным случаем этих алгебр. Булево кольцо также является полукольцом (на самом деле, кольцом), но оно не идемпотентно относительно сложения . Булево полукольцо является полукольцом, изоморфным подполукольцу булевой алгебры. ^[20]
• Коммутативное полукольцо, образованное двухэлементной булевой алгеброй и определяемое . Его также называют ${\displaystyle 1+1=1}$Булево полукольцо .^{[6][21][22][9]}Теперь даны два множестваибинарные отношениямеждуисоответствуют матрицам, индексированнымис записями в булевом полукольце,сложение матрицсоответствует объединению отношений, аумножение матрицсоответствуеткомпозиции отношений.^[25] ${\displaystyle X}$ ${\displaystyle Y,}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle X}$ ${\displaystyle Y}$
• Любой единичный квантал является полукольцом относительно соединения и умножения.
• Нормальная косая решетка в кольце — это полукольцо для операций умножения и набла, где последняя операция определяется как ${\displaystyle R}$ ${\displaystyle a\nabla b=a+b+ba-aba-bab}$

Больше с использованием моноидов,

• Описано построение полуколец из коммутативного моноида . Как отмечено, дайте полукольцо , матрицы образуют другое полукольцо. Например, матрицы с неотрицательными элементами образуют матричное полукольцо. ^[20] ${\displaystyle \operatorname {End} (M)}$ ${\displaystyle M}$ ${\displaystyle R}$ ${\displaystyle n\times n}$ ${\displaystyle {\mathcal {M}}_{n}(\mathbb {N} ),}$
• При заданном алфавите (конечном множестве) Σ множество формальных языков над (подмножествами ) является полукольцом с произведением, индуцированным конкатенацией строк и сложением как объединением языков (то есть обычным объединением как множеств). Нуль этого полукольца является пустым множеством (пустым языком), а единицей полукольца является язык, содержащий только пустую строку . ^[11] ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{*}}$ ${\displaystyle L_{1}\cdot L_{2}=\left\{w_{1}w_{2}\mid w_{1}\in L_{1},w_{2}\in L_{2}\right\}}$
• Обобщая предыдущий пример (рассматривая его как свободный моноид над ), возьмем любой моноид; множество степеней всех подмножеств образует полукольцо относительно теоретико-множественного объединения как сложения и умножения по множествам: ^[22] ${\displaystyle \Sigma ^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle M}$ ${\displaystyle \wp (M)}$ ${\displaystyle M}$ ${\displaystyle U\cdot V=\{u\cdot v\mid u\in U,\ v\in V\}.}$
• Аналогично, если — моноид, то множество конечных мультимножеств в образует полукольцо. То есть, элемент — это функция ; заданный элемент функции сообщает вам, сколько раз этот элемент встречается в мультимножестве, которое он представляет. Аддитивная единица — это постоянная нулевая функция. Мультипликативная единица — это функция, отображающая в , а все остальные элементы в Сумма задается как , а произведение — как ${\displaystyle (M,e,\cdot )}$ ${\displaystyle M}$ ${\displaystyle f\mid M\to \mathbb {N} }$ ${\displaystyle M,}$ ${\displaystyle e}$ ${\displaystyle 1,}$ ${\displaystyle M}$ ${\displaystyle 0.}$ ${\displaystyle (f+g)(x)=f(x)+g(x)}$ ${\displaystyle (fg)(x)=\sum \{f(y)g(z)\mid y\cdot z=x\}.}$

Что касается множеств и подобных абстракций,

• Если задано множество бинарных отношений над , то это полукольцо со сложением — объединением (отношений как множеств) и умножением — композицией отношений . Нуль полукольца — пустое отношение , а его единица — тождественное отношение . ^[11] Эти отношения соответствуют матричному полукольцу (на самом деле, матричной полуалгебре) квадратных матриц, индексированных с элементами в булевом полукольце, а затем сложение и умножение — это обычные матричные операции, в то время как ноль и единица — это обычные нулевая матрица и тождественная матрица . ${\displaystyle U,}$ ${\displaystyle U}$ ${\displaystyle U}$
• Множество кардинальных чисел , меньших любого заданного бесконечного кардинала, образует полукольцо относительно кардинального сложения и умножения. Класс всех кардиналов внутренней модели образует (класс) полукольцо относительно кардинального сложения и умножения (внутренней модели).
• Семейство (классов эквивалентности изоморфизма) комбинаторных классов (множеств счетного числа объектов с неотрицательными целыми размерами, таких, что существует конечное число объектов каждого размера) с пустым классом в качестве нулевого объекта, классом, состоящим только из пустого множества в качестве единицы, несвязным объединением классов в качестве сложения и декартовым произведением классов в качестве умножения. ^[26]
• Классы изоморфизма объектов в любой дистрибутивной категории , при операциях копроизведения и произведения , образуют полукольцо, известное как оснастка Бернсайда. ^[27] Оснастка Бернсайда является кольцом тогда и только тогда, когда категория тривиальна .

Звездчатые полукольца

Некоторые из вышеперечисленных конструкций могут быть оснащены функцией «звезда».

• Вышеупомянутое полукольцо бинарных отношений над некоторым базовым множеством , в котором для всех Эта операция звезды на самом деле является рефлексивным и транзитивным замыканием ( то есть наименьшим рефлексивным и транзитивным бинарным отношением над , содержащим ). ^[11] ${\displaystyle U}$ ${\displaystyle R^{*}=\bigcup _{n\geq 0}R^{n}}$ ${\displaystyle R\subseteq U\times U.}$ ${\displaystyle R}$ ${\displaystyle U}$ ${\displaystyle R.}$
• Полукольцо формальных языков также является полным звездным полукольцом, причем звездная операция совпадает со звездой Клини (для множеств/языков). ^[11]
• Множество неотрицательных расширенных действительных чисел вместе с обычным сложением и умножением действительных чисел представляет собой полное звездное полукольцо с операцией звездочки, заданной для (то есть геометрической прогрессией ) и для ^[11] ${\displaystyle [0,\infty ]}$ ${\displaystyle a^{*}={\tfrac {1}{1-a}}}$ ${\displaystyle 0\leq a<1}$ ${\displaystyle a^{*}=\infty }$ ${\displaystyle a\geq 1.}$
• Булево полукольцо с ^{[b] [11]} ${\displaystyle 0^{*}=1^{*}=1.}$
• Полукольцо с расширенным сложением и умножением, и для ^{[b] [11]} ${\displaystyle \mathbb {N} \cup \{\infty \},}$ ${\displaystyle 0^{*}=1,a^{*}=\infty }$ ${\displaystyle a\geq 1.}$

Приложения

И тропические полукольца на вещественных числах часто используются при оценке производительности в дискретно-событийных системах. Вещественные числа тогда являются «стоимостью» или «временем прибытия»; операция «max» соответствует необходимости ждать все предварительные условия события (таким образом, занимая максимальное время), тогда как операция «min» соответствует возможности выбрать лучший, менее затратный выбор; и + соответствует накоплению по тому же пути. ${\displaystyle (\max ,+)}$ ${\displaystyle (\min ,+)}$

Алгоритм Флойда–Уоршелла для кратчайших путей может быть, таким образом, переформулирован как вычисление над алгеброй. Аналогично, алгоритм Витерби для нахождения наиболее вероятной последовательности состояний, соответствующей последовательности наблюдений в скрытой марковской модели, также может быть сформулирован как вычисление над алгеброй вероятностей. Эти алгоритмы динамического программирования полагаются на дистрибутивное свойство связанных с ними полуколец для вычисления величин над большим (возможно, экспоненциальным) числом членов более эффективно, чем перечисление каждого из них. ^{[28] [29]} ${\displaystyle (\min ,+)}$ ${\displaystyle (\max ,\times )}$

Обобщения

Обобщение полуколец не требует существования мультипликативного тождества, так что умножение является полугруппой, а не моноидом. Такие структуры называются полукольцами ^[30] или предполукольцами . ^[31] Дальнейшее обобщение — это левые предполукольца [ ^32], которые дополнительно не требуют правой дистрибутивности (или правые предполукольца , которые не требуют левой дистрибутивности).

Еще одним обобщением являются почти-полукольца : в дополнение к тому, что им не требуется нейтральный элемент для произведения или право-дистрибутивности (или лево-дистрибутивности), им не требуется сложение, чтобы быть коммутативными. Так же, как кардинальные числа образуют (класс) полукольцо, так и порядковые числа образуют почти-полукольцо , когда принимаются во внимание стандартные порядковые сложение и умножение . Однако класс порядковых чисел можно превратить в полукольцо, рассмотрев вместо этого так называемые естественные (или Хессенберговы) операции .

В теории категорий 2 -rig — это категория с функториальными операциями, аналогичными операциям rig. То, что кардинальные числа образуют rig, можно категоризировать, сказав, что категория множеств (или, в более общем смысле, любой топос ) является 2-rig.

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

• Кольцо множеств  – Семья, замкнутая относительно союзов и относительных дополнений
• Оценочная алгебра  – алгебра, описывающая обработку информации.Pages displaying short descriptions of redirect targets

Примечания

1. Для примера см. определение rig ​​на Proofwiki.org
2. Это полное звездное полукольцо и, следовательно, также полукольцо Конвея. ^[11]

Цитаты

1. Глазек (2002), стр. 7
2. Кунцманн, Дж. (1972). Теория де резо (графики) (на французском языке). Париж: Дюнод. Збл  0239.05101.
3. Полукольца на завтрак, слайд 17
4. Baccelli, François Louis; Olsder, Geert Jan; Quadrat, Jean-Pierre; Cohen, Guy (1992). Синхронизация и линейность. Алгебра для дискретных событийных систем . Wiley Series on Probability and Mathematical Statistics. Chichester: Wiley. Zbl  0824.93003.
5. Берстель и Перрин (1985), с. 26
6. Lothaire (2005), с. 211
7. Сакарович (2009), стр. 27–28.
8. Лотер (2005), стр. 212
9. Ésik, Zoltán (2008). "Итерационные полукольца". В Ito, Masami (ред.). Developments in language theory. 12-я международная конференция, DLT 2008, Киото, Япония, 16–19 сентября 2008 г. Труды . Lecture Notes in Computer Science. Vol. 5257. Berlin: Springer-Verlag . pp. 1–20. doi :10.1007/978-3-540-85780-8_1. ISBN 978-3-540-85779-2. Збл  1161.68598.
10. Kuich, Werner (2011). "Алгебраические системы и автоматы с магазинной памятью". В Kuich, Werner (ред.). Алгебраические основы в информатике. Эссе, посвященные Симеону Бозапалидису по случаю его выхода на пенсию . Lecture Notes in Computer Science. Vol. 7020. Berlin: Springer-Verlag . pp. 228–256. ISBN 978-3-642-24896-2. Збл  1251.68135.
11. Droste & Kuich (2009), стр. 7–10.
12. Kuich, Werner (1990). "ω-непрерывные полукольца, алгебраические системы и автоматы с магазинной памятью". В Paterson, Michael S. (ред.). Автоматы, языки и программирование: 17-й международный коллоквиум, Уорикский университет, Англия, 16–20 июля 1990 г., Труды . Конспект лекций по информатике. Том 443. Springer-Verlag . С. 103–110. ISBN 3-540-52826-1.
13. Sakarovitch (2009), стр. 471
14. Ésik, Zoltán; Leiß, Hans (2002). «Нормальная форма Грейбаха в алгебраически полных полукольцах». В Bradfield, Julian (ред.). Computer science logic. 16-й международный семинар, CSL 2002, 11-я ежегодная конференция EACSL, Эдинбург, Шотландия, 22–25 сентября 2002 г. Труды . Lecture Notes in Computer Science. Том 2471. Берлин: Springer-Verlag . С. 135–150. Zbl  1020.68056.
15. Леманн, Дэниел Дж. (1977), «Алгебраические структуры для транзитивного замыкания» (PDF) , Теоретическая информатика , 4 (1): 59–76, doi :10.1016/0304-3975(77)90056-1
16. Берстель и Ройтенауэр (2011), с. 27
17. Эсик, Золтан; Куич, Вернер (2004). «Эквациональные аксиомы для теории автоматов». В Мартин-Виде, Карлос (ред.). Формальные языки и приложения . Исследования по нечеткости и мягким вычислениям. Т. 148. Берлин: Springer-Verlag . С. 183–196. ISBN 3-540-20907-7. Збл  1088.68117.
18. Дросте и Куич (2009), с. 15, теорема 3.4.
19. Conway, JH (1971). Регулярная алгебра и конечные машины . Лондон: Chapman and Hall. ISBN 0-412-10620-5. Збл  0231.94041.
20. Guterman, Alexander E. (2008). "Ранг и детерминантные функции для матриц над полукольцами". В Young, Nicholas; Choi, Yemon (ред.). Surveys in Contemporary Mathematics . London Mathematical Society Lecture Note Series. Том 347. Cambridge University Press . С. 1–33. ISBN 978-0-521-70564-6. ISSN  0076-0552. Збл  1181.16042.
21. Сакарович (2009), стр. 28.
22. Berstel & Reutenauer (2011), стр. 4
23. Шпейер, Дэвид; Штурмфельс, Бернд (2009) [2004]. «Тропическая математика». Математика. Маг . 82 (3): 163–173. arXiv : math/0408099 . дои : 10.4169/193009809x468760. S2CID  119142649. Збл  1227.14051.
24. Шпейер, Дэвид; Штурмфельс, Бернд (2009). «Тропическая математика». Mathematics Magazine . 82 (3): 163–173. doi :10.1080/0025570X.2009.11953615. ISSN  0025-570X. S2CID  15278805.
25. Джон К. Баез (6 ноября 2001 г.). "квантовая механика над коммутативной установкой". Группа новостей : sci.physics.research. Usenet:  [email protected] . Получено 25 ноября 2018 г.
26. Бард, Грегори В. (2009), Алгебраический криптоанализ, Springer, Раздел 4.2.1, «Комбинаторные классы», и далее, стр. 30–34, ISBN 9780387887579
27. Schanuel SH (1991) Отрицательные множества имеют эйлерову характеристику и размерность. В: Carboni A., Pedicchio MC, Rosolini G. (ред.) Теория категорий. Lecture Notes in Mathematics, т. 1488. Springer, Berlin, Heidelberg
28. Пара (1967), стр. 271.
29. Дерниам и Пара (1971)
30. Голан (1999), стр. 1, гл. 1
31. Гондран и Мину (2008), с. 22, гл. 1, §4.2.
32. Гондран и Мину (2008), с. 20, гл. 1, §4.1.

Библиография

• Дерниам, Жан Клод; Пара, Клод (1971), Problèmes de cheminement dans lesgraphes (Проблемы с путями в графах) , Париж: Dunod
• Бачелли, Франсуа ; Коэн, Гай; Олсдер, Герт Ян; Квадрат, Жан-Пьер (1992), Синхронизация и линейность (электронная версия), Wiley, ISBN 0-471-93609-X
• Golan, Jonathan S. (1999) Semirings and their applications . Обновленная и расширенная версия The theory of semirings, with applications to mathematics and theoretical computer science (Longman Sci. Tech., Harlow, 1992, MR 1163371). Kluwer Academic Publishers, Dordrecht. xii+381 pp. ISBN 0-7923-5786-8 MR 1746739 
• Берстель, Жан; Перрен, Доминик (1985). Теория кодов . Чистая и прикладная математика. Т. 117. Academic Press. ISBN 978-0-12-093420-1. Збл  0587.68066.
• Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. Том 137. Кембридж: Cambridge University Press . ISBN 978-0-521-19022-0. Збл  1250.68007.
• Дросте, Манфред; Куич, Вернер (2009), «Глава 1: Полукольца и формальные степенные ряды», Справочник по взвешенным автоматам , стр. 3–28, doi :10.1007/978-3-642-01492-5_1
• Дарретт, Ричард (2019). Вероятность: теория и примеры (PDF) . Серия Кембридж по статистической и вероятностной математике. Том 49 (5-е изд.). Кембридж, Нью-Йорк, Нью-Йорк: Cambridge University Press . ISBN 978-1-108-47368-2. OCLC  1100115281 . Получено 5 ноября 2020 г. .
• Фолланд, Джеральд Б. (1999), Реальный анализ: современные методы и их применение (2-е изд.), John Wiley & Sons, ISBN 9780471317166
• Голан, Джонатан С. (1999), Полукольца и их приложения , Дордрехт: Kluwer Academic Publishers, doi :10.1007/978-94-015-9333-5, ISBN 0-7923-5786-8, г-н  1746739
• Лотер, М. (2005). Прикладная комбинаторика к словам . Энциклопедия математики и ее приложений. Том. 105. Коллективная работа Жана Берстеля, Доминика Перрена, Максима Крошмора, Эрика Лапорта, Мехрияра Мори, Нади Пизанти, Мари-Франс Саго, Жезины Рейнерт , Софи Шбат , Михаэля Уотермана, Филиппа Жаке, Войцеха Шпанковского , Доминика Пулалона, Жиля Шеффера, Роман Колпаков, Григорий Кучеров, Жан-Поль Аллуш и Валери Берте . Кембридж: Издательство Кембриджского университета . ISBN 0-521-84802-4. Збл  1133.68067.
• Глазек, Казимеж (2002). Справочник по литературе по полукольцам и их приложениям в математике и информационных науках. С полной библиографией . Дордрехт: Kluwer Academic. ISBN 1-4020-0717-5. Збл  1072.16040.
• Gondran, Michel; Minoux, Michel (2008). Графы, диоиды и полукольца: новые модели и алгоритмы . Серия Operations Research/Computer Science Interfaces. Том 41. Дордрехт: Springer Science & Business Media. ISBN 978-0-387-75450-5. Збл  1201.16038.
• Пэр, Клод (1967), «Sur des алгоритмы pour des problèmes de cheminement dans les Graphes Finis (Об алгоритмах решения задач о путях в конечных графах)», в Rosentiehl (редактор), Théorie desgraphes (journées Internationales d'études) - Теория графов (международный симпозиум) , Рим (Италия), июль 1966 г.: Дюно (Париж) и Гордон и Брич (Нью-Йорк){{citation}}: CS1 maint: location (link)
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Кембридж: Cambridge University Press . ISBN 978-0-521-84425-3. Збл  1188.68177.

Дальнейшее чтение

• Голан, Джонатан С. (2003). Полукольца и аффинные уравнения над ними . Springer Science & Business Media. ISBN 978-1-4020-1358-4. Збл  1042.16038.
• Grillet, Mireille P. (1970). «Соотношения Грина в полукольце». Port. Math . 29 : 181–195. Zbl  0227.16029.
• Гунавардена, Джереми (1998). «Введение в идемпотентность». В Гунавардена, Джереми (ред.). Идемпотентность. На основе семинара, Бристоль, Великобритания, 3–7 октября 1994 г. (PDF) . Кембридж: Cambridge University Press . стр. 1–49. Zbl  0898.16032.
• Jipsen, P. (2004). «От полуколец к вычетным решеткам Клини». Studia Logica . 76 (2): 291–303. doi :10.1023/B:STUD.0000032089.54776.63. S2CID  9946523. Zbl  1045.03049.
• Долан, Стивен (2013), «Развлечения с полукольцами» (PDF) , Труды 18-й международной конференции ACM SIGPLAN по функциональному программированию , стр. 101–110, doi :10.1145/2500365.2500613, ISBN 9781450323260, S2CID  2436826