Полукольцо

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

Наименьшее полукольцо, не являющееся кольцом, — это двухэлементная булева алгебра , например, с логической дизъюнкцией в качестве сложения. Мотивирующим примером, который не является ни кольцом, ни решеткой, является множество натуральных чисел (включая ноль) при обычном сложении и умножении. Полукольца широко распространены, поскольку подходящая операция умножения возникает как функциональная композиция эндоморфизмов над любым коммутативным моноидом .${\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]}$

• Совокупность всех идеалов данного полукольца образует полукольцо относительно сложения и умножения идеалов.
• Любая ограниченная дистрибутивная решетка является коммутативным полукольцом относительно 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