Півкільця. Основні приклади

Визначення 3.1.Напівкільце — це алгебра з двома бінарними та двома нульарними операціями

така, що для довільних елементів а, b, з множини S виконуються такі рівності, звані аксіомами півкільця:

  1. a + (b + c) = (a + b) + c;
  2. a + b = b + a;
  3. a +0 = a;
  4. a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c;
  5. a ⋅1 =1 ⋅a = a
  6. a ⋅ (b + c) = a ⋅ b + a ⋅ c;
  7. (b + c) ⋅ b ⋅ a + c ⋅ a;
  8. a ⋅0 =0 ⋅ a =0.

Першу операцію називаютьскладанням півкільця, а другу операцію -множенням півкільцяS ; елементи 0 і 1 називають відповіднонулем і одиницею півкільця S.

Аксіоми півкільця називають також основними чеками півкільця.

Таким чином, з визначення випливає, що операція додавання півкільця асоціативна і комутативна, а нуль півкільця є нейтральним елементом щодо операції додавання; операція множення півкільця асоціативна та одиниця півкільця є нейтральним елементом щодо операції множення. Крім цього має місце властивість дистрибутивності (двосторонньої) операції множення щодо складання півкільця. Аксіому 8 півкільця називаютьанулюючою властивістю нуля у півкільці.

Використовуючи поняття моноїду, визначення 3.1 можна переформулювати так. Півкільце S = (S, +, ⋅, 0, 1) — це алгебра з двома бінарними та двома нульарними операціями, така, що:

  1. алгебра (S, +, 0) є комутативним моноїдом (його називають адитивним моноідом півкільця);
  2. алгебра (S, ⋅, 1) є моноідом (його називають мультиплікативним моноідом півкільця);
  3. мають місце властивості (двосторонньої) дистрибутивності операції складаннящодо операції множення;
  4. виконується анулююча властивість нуля.

Порівнюючи визначення півкільця з визначенням 2.5 кільця, бачимо, що кільце є окремий випадок півкільця: якщо кільце за додаванням є обелевою групою, то півкільце — лише комутативний моноід.

Виділимо два види напівкілець: комутативне півкільце з комутативною операцією множення і тне півкільце з ідемпотентною операцією додавання.

Приклад 3.1. Розглянемо алгебру

де ℝ + - безліч невід'ємних дійсних чисел, min - операція взяття найменшого з двох даних чисел, + - Операція додавання дійсних чисел, + ∞ - "плюс нескінченність" (у тому ж сенсі, що і в математичному аналізі), 0 - число " нуль".

Ця алгебра - півкільце, носієм якого є піввісь ℝ + = , поповнена елементом +∞ (множина всіх невід'ємних дійсних чисел разом з плюс нескінченністю ").

Незвичайність півкільця R + полягає в тому, що як його множення взято додавання дійсних чисел, тоді як додаванням обрана операція взяття найменшого з двох чисел. Відповідно до сигнатури, елемент +∞ розглядається як нуль півкільця. Справді, min(x, +∞) = x будь-якого x ∈ ℝ + U , тобто. елемент +∞ є нейтральним елементом щодо операції min (операції складання в півкільці). Елемент +∞ також має анулюючу властивість щодо операції складання чисел (операції множення в півкільці): х + (+∞) = +∞. Отже, виконуються аксіоми 3 та 8 півкільця.

Інші аксіоми півкільця також виконані. Легко переконатися, що алгебра (ℝ + U, min, +∞) - комутативний моноід і алгебра (ℝ + U, +, 0) - також комутативний моноід. Перевіримо властивості дистрибутивності, які в даному випадкузапишуться так:

a+min(b, c) = min(a+b, a+c).

a+min(b, c) = min(a+b, a+c).

Зауважимо, що у аналізованому півкільці множення + комутативно, а додавання min ідемпотентно. Отже, R + - ідемпотентне комутативне півкільце.

Приклад 3.2. Розглянемо алгебру B = (, +, ⋅, 0, 1), в якій операції + та ⋅ задані таблицями Келі (табл. 3.1 та 3.2).

Таблиця 3.1, Таблиця 3.2

+01
001
111
⋅01000101

Перевірка аксіом півкільця ґрунтується на цих таблицях і легко виконується. Звернемо увагу, що два елементи О і 1, з яких у даному випадку складається носій півкільця-півкільця, одночасно є відповідно нулем і одиницею даного півкільця. Легко бачити, що аналізоване напів-півкільце комутативне та ідемпотентне.

Цікаво те, що операції півкільця В можна трактувати як логічні зв'язки „або” та „і”, а елементи 0 та 1 – як „брехня” та „істина” відповідно.

Приклад 3.3. Розглянемо ще кілька різних алгебр, які є півкільцями. Виконання аксіом півкільця для всіх наведених алгебрів легко перевіряється.

а. АлгебраN = (ℕ0, +, ⋅, 0, 1) з носієм - безліччю невід'ємних цілих чисел і операціями складання та множення чисел є комутативне півкільце. Воно не є ідемпотентним.

б. АлгебраS A = (2 A , ∪, ∩, ∅, А) з носієм — безліччю всіх підмножин деякої множини А та операціями об'єднання та перетинує півкільце. Воно є ідемпотентним та комутативним.

в. АлгебраR A = (2 АхА , ∪, ॰, ∅, idA) з носієм - безліччю всіх бінарних відносин на множині А - і операціями об'єднання та композиції відносин є півкільцем. Воно йдемо потентне, але не комутативне.

м. АлгебраS [a,b] = ([а, b],max, min, а, b), носієм якої служить відрізок числової прямої, з операціями взяття максимуму та мінімуму з двох чисел є ідемпотентне та комутативне півкільце. #

Надалі нас цікавитимуть лише півкільця, оскільки саме на їх основі розробляються методи алгебри аналізу орієнтованих графів і кінцевих автоматів.

На носії ідемпотентного півкільцяS = (S, +, ⋅,0, 1 ) може бути введено відношення порядку, яке, природно, узгоджується з властивостями операцій півкільця: для довільних x, у ∈ S покладемо х ≤ у тоді і лише тоді, коли x + y = y, тобто. x ≤ y ↔ x + y = y. (3.1)

Перевіримо, що таким чином справді визначено ставлення до порядку. Для цього потрібно показати, що введене бінарне ставлення рефлексивне, антисиметричне та зитивне.

Оскільки для будь-якого х через ідемпотентність додавання має місце рівність х + х = x, то, згідно (3.1), маємо х ≤ x, тобто. введене ставлення рефлексивне.

Співвідношення х ≤ у та у ≤ х означають, що х + у = у і у + х = = х. Оскільки додавання комутативно, з цих рівностей слід, що x = у. Отже, розглянуте ставлення є антисиметричним.

Співвідношення х ≤ у та у ≤ z означають, що х + у = у та у + z = z.

Тоді x + z = x + (y + z) + z = y + z = z, звідки випливає, що х ≤ z. Таким чином, введене ставлення є транзитивним.

Отже, відношення на носії довільного ідемпотентногопівкільця є відношення порядку. Будемо називати його природним порядком ідемпотентного півкільця і ​​говоритимемо, що він заданий у цьому півкільці.

Ми встановили дуже важливий факт: будь-яке ідемпотентне півкільце можна розглядати як впорядковане безліч, причому відношення порядку визначається через додавання цього півкільця згідно з C.1). Введене відношення порядку можна інтерпретувати так: „більше при додаванні поглинає менше” (як, скажімо, при об'єднанні множини та деякої його підмножини).

Оскільки для будь-якого елемента довільного ідемпотентного півкільця S = S, +, ⋅, 0, 1) має місце 0 + х = x, то для будь-якого х ∈ S виконується нерівність 0 ≤ x, тобто. нуль ідемпотентного півкільця є найменший елемент щодо природного порядку ідемпотентного півкільця.

Пояснимо, як інтерпретується природний порядок ідемпотентних напівкілець, розглянутих у наведених вище прикладах.

Приклад 3.4. У півкільціВ (див. приклад 3.2) виконується рівність 0 + 1 = 1 і, отже, 0≤1.

У півкільціR + (див. приклад 3.1) х ≤ у, якщо і якщо min (x, y) = y.

Позначимо через ≤ℝ природний числовий порядок на множині дійсних чисел. Тоді для довільних елементів x у півкільцяR + співвідношення х ≤ у означає, що х ≥ℝу, тобто. число х не менше числа відносно природного числового порядку. Таким чином, порядок у півкільці R + – це двоякий порядок для відношення ≥ℝ. У півкільці є найменший елемент щодо введеного порядку елемент +∞, оскільки для будь-якого елемента х маємо min(x, +∞) = х. Існує і максимальний елемент — одиниця півкільця, тобто. число 0. Не слід плутати число 0 із нулем даного півкільця, саме з елементом +∞.

УпівкільцеS A (див. приклад З.З.б) отримуємо як відношення природного порядку півкільця відношення включення С . Справді, для будь-яких двох множин X, У ∈ 2 A із X U Y = Y витікає X ⊆ Y і навпаки. Найменшим елементом є нуль півкільця - 0 (порожня множина), а найбільшим - одиниця півкільця (множина А).

У півкільціR A (див. приклад З.З.в) відношення природного порядку півкільця також збігається із ставленням - включення для бінарних відносин. У цьому півкільці існують найменший елемент – порожнє відношення 0 та найбільший елемент – універсальне відношення. Проте на відміну півкільця SA найбільший елемент не збігається з одиницею півкільця.

У півкільціS [а,b] (див. приклад З.З.г) маємо природний числовий порядок, визначений на множині дійсних чисел відрізка [а, b]. Найменшим елементом є число а (нуль півкільця), а найбільшим - число b (одиниця півкільця).

Теорема 3.1. Якщо А - кінцеве підмножина (носія) ідемпотентного півкільця, то sup Л щодо природного порядку цього півкільця дорівнює сумі всіх елементів множини А.

◀Нехай А = та а = а1 +. + аn. Для довільного елемента ai, i = 1,n, в силу комутативності та ідемпотентності складання маємо

тобто. ai ≤ a, і тому а є верхня грань множини А. Покажемо, що це точна верхня грань множини. Візьмемо довільну верхню грань b множини А і розглянемо суму b + а. Оскільки кожного i = 1,n має місце ai ≤ b, тобто. ai + b = b, то b + а = b + (а1 + а2 +. + ааn) = (b + а1) + (а2 +. + аn) = b + а2 +. + аn = . = b

Отже, а ≤ b і тому а — тонна верхня грань множини А. ▶