Полукольцо

Эта статья об алгебраических структурах. Чтобы узнать о других значениях, см. Кольцо множеств § полукольцо .

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

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

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

Некоторые авторы называют полукольцом структуру без требования наличия $0$ или $1$. Это делает аналогию между кольцом и полукольцом , с одной стороны, и группой и полугруппой , с другой, более плавной. Эти авторы часто используют установку для определения концепции, определенной здесь. Это возникло как шутка, предполагающая, что оснастка — это кольца без отрицательных элементов . (И это похоже на использование rng для обозначения существа без мультипликативной идентичности .)

Термин диоид (от «двойного моноида») использовался для обозначения полуколец или других структур. Его использовал Кунцманн в 1972 году для обозначения полукольца. (В качестве альтернативы иногда используется для естественно упорядоченных полуколец. но этот термин также использовался для идемпотентных подгрупп Бачелли и др. в 1992 году. )

Определение

Полукольцо – это набор $R$ оснащен двумя бинарными операциями $+$ и $\cdot ,$ называется сложением и умножением, так что:

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

Прямо сказано, $(R,+)$ является коммутативным моноидом.Кроме того, следующие аксиомы связаны с обеими операциями:

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

Обозначения

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

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

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

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

Изготовление новых полуколец

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

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

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

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

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

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

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

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

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

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

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

Выводы

Выводы на полукольце $R$ это карты ${\mathrm {d} }\colon R\to R$ с ${\mathrm {d} }(x+y)={\mathrm {d} }(x)+{\mathrm {d} }(y)$ и ${\mathrm {d} }(x\cdot y)={\mathrm {d} }(x)\cdot y+x\cdot {\mathrm {d} }(y)$.

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

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

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

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

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

Полуполя

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

Кольца

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

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

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

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

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

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

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

Заказал полукольца

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

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

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

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

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

Полукольцо, в котором каждый элемент является аддитивным идемпотентом , т. е. $x+x=x$ для всех элементов $x$, называется (аддитивно) идемпотентным полукольцом . Создание $1+1=1$ достаточно. Имейте в виду, что иногда это называют просто идемпотентным полукольцом, независимо от правил умножения.

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

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

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

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

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

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

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

Числовые линии

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

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

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

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

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

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

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

• $0<1$

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

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

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

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

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

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

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

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

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

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

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

${\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.$

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

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

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

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

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

Звездчатое полукольцо (иногда пишется как staremiring ) — это полукольцо с дополнительным унарным оператором. ${}^{*}$, удовлетворяющий

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

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

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

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

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

где

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

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

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

Полукольцо Конвея — это звездное полукольцо, удовлетворяющее уравнениям суммы-звезды и произведения-звезды:

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

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

Примеры

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

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

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

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

• Множество всех идеалов данного полукольца образует полукольцо при сложении и умножении идеалов.
• Любая ограниченная дистрибутивная решетка представляет собой коммутативное полукольцо при соединении и пересечении. Булева алгебра является их частным случаем. также Булево кольцо является полукольцом (фактически кольцом), но оно не идемпотентно относительно сложения . Булево полукольцо — это полукольцо, изоморфное подполукольцу булевой алгебры.
• Коммутативное полукольцо, образованное двухэлементной булевой алгеброй и определяемое формулой $1+1=1$. еще называют Его Булево полукольцо . Теперь дано два набора $X$ и $Y,$ бинарные отношения между $X$ и $Y$ соответствуют матрицам, индексированным $X$ и $Y$ с элементами булевого полукольца сложение матриц соответствует объединению отношений, а умножение матриц соответствует композиции отношений .
• Любой единичный квантал представляет собой полукольцо при соединении и умножении.
• Нормальная косая решетка в кольце $R$ является полукольцом для операций умножения и наблы, причем последняя операция определяется формулой $a\nabla b=a+b+ba-aba-bab$

Больше используя моноиды,

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

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

• Учитывая набор $U,$ множество бинарных отношений над $U$ есть полукольцо со сложением объединением (отношений как множеств) и умножением составом отношений . Ноль полукольца — пустое отношение , а его единица — тождественное отношение . Эти отношения соответствуют матричному полукольцу (фактически матричной полуалгебре) квадратных матриц с индексом $U$ с записями в булевом полукольце, а затем сложение и умножение — обычные матричные операции, а ноль и единица — обычная нулевая матрица и единичная матрица .
• Набор кардинальных чисел , меньших любого заданного бесконечного кардинала, образует полукольцо при кардинальном сложении и умножении. Класс всех кардиналов внутренней модели образует (класс) полукольцо при кардинальном сложении и умножении (внутренней модели).
• Семейство (классов эквивалентности изоморфизма) комбинаторных классов (наборов счетного числа объектов с неотрицательными целочисленными размерами, таких, что существует конечное число объектов каждого размера) с пустым классом в качестве нулевого объекта, класс, состоящий только из пустых множество как единица, несвязное объединение классов как сложение и декартово произведение классов как умножение.
• Классы изоморфизма объектов в любой дистрибутивной категории при операциях совместного произведения и произведения образуют полукольцо, известное как бурсайдовская установка. Оснащение Бернсайда является кольцом тогда и только тогда, когда категория тривиальна .

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

Некоторые структуры, упомянутые выше, могут быть оснащены звездообразным режимом.

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

Приложения

The $(\max ,+)$ и $(\min ,+)$ тропические полукольца на действительных числах часто используются при оценке производительности систем дискретных событий. Тогда реальные цифры — это «затраты» или «время прибытия»; операция «макс» соответствует необходимости ожидания всех предварительных условий события (таким образом, занимая максимальное время), а операция «мин» соответствует возможности выбрать лучший и менее затратный выбор; и + соответствует накоплению по тому же пути.

Таким образом, алгоритм Флойда-Уоршалла для поиска кратчайших путей можно переформулировать как вычисление над $(\min ,+)$ алгебра. Аналогичным образом, алгоритм Витерби для поиска наиболее вероятной последовательности состояний, соответствующей последовательности наблюдений в скрытой модели Маркова, также может быть сформулирован как вычисление над $(\max ,\times )$ алгебра вероятностей. Эти алгоритмы динамического программирования полагаются на распределительное свойство связанных с ними полуколец для вычисления величин по большому (возможно, экспоненциальному) числу термов более эффективно, чем перечисление каждого из них.

Обобщения

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

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

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

См. также

• Кольцо множеств - Семья, замкнутая союзами и относительными дополнениями.
• Алгебра оценки — алгебра, описывающая обработку информации . Страницы с краткими описаниями целей перенаправления.

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

• Дерниам, Жан Клод; Пара, Клод (1971), Проблемы с путями в графах , Париж: Dunod
• Бачелли, Франсуа ; Коэн, Гай; Олсдер, Герт Ян; Квадрат, Жан-Пьер (1992), Синхронизация и линейность (онлайн-версия) , Wiley, ISBN  0-471-93609-Х
• Голан, Джонатан С. (1999) Полукольца и их приложения . Обновленная и расширенная версия «Теории полуколец» с приложениями к математике и теоретической информатике (Longman Sci. Tech., Harlow, 1992, MR). 1163371 ). Kluwer Academic Publishers, Дордрехт. xii+381 стр. ISBN   0-7923-5786-8 МР 1746739
• Берстель, Жан; Перрен, Доминик (1985). Теория кодов . Чистая и прикладная математика. Том. 117. Академическая пресса. ISBN  978-0-12-093420-1 . Збл   0587.68066 .
• Берстель, Жан; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. Том. 137. Кембридж: Издательство Кембриджского университета . 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-е изд.). Кембридж, Нью-Йорк, Нью-Йорк: Издательство Кембриджского университета . 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). Путеводитель по литературе по полукольцам и их применению в математике и информатике. С полной библиографией . Дордрехт: Клювер Академик. ISBN  1-4020-0717-5 . Збл   1072.16040 .
• Гондран, Мишель; Мину, Мишель (2008). Графы, диоиды и полукольца: новые модели и алгоритмы . Серия интерфейсов исследования операций/информатики. Том. 41. Дордрехт: Springer Science & Business Media. ISBN  978-0-387-75450-5 . Збл   1201.16038 .
• Пэр, Клод (1967), «Об алгоритмах решения задач о путях в конечных графах», Розентиль (редактор), Теория графов (дни международных исследований) - Теория графов (международный симпозиум) , Рим (Италия), июль 1966: Дунод (Париж) и Гордон и Брич (Нью-Йорк) {{citation}}: CS1 maint: местоположение ( ссылка )
• Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-84425-3 . Збл   1188.68177 .

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

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