Алгебраические системы

Теория

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

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

  • Модели и алгебры

    Алгебраическая система — это упорядоченная тройка A= (А, Ω, П), где А — некоторое множество, называемое носителем алгебраической системы; Ω — некоторое множество операций на А, П — некоторое множество отношений на А. Упорядоченную пару (Ω, П) называют сигнатурой алгебраической системы.Подробнее

  • Подсистемы

    Пусть A = (A, Ω, П) — произвольная алгебраическая система и В ⊆ А — непустое множество. Множество В называют замкнутым относительно операций из Ω (Ω-замкнутым множеством), если результат применения любой n-арной операции из Ω к любым элементам из В принадлежит В, т.е. для любой n-арной операции ω и любых элементов а1, ..., аn ∈ В элемент ω(a1, ..., an) ∈ B. Подробнее

  • Конгруэнции и фактор-системы

    В этой главе нам будет удобно использовать "бесскобочную" запись для обозначения результата применения n-арной операции ω к элементам a1, ..., an и писать a1, ..., anω вместо ωa1, ..., an. Отношение эквивалентности р на носителе алгебраической системы A называют конгруэнцией на алгебраической системе ЛA, если выполняются условия:Подробнее

  • Гомоморфизмы

    Пусть A = (А, Ω, П) и В = (В, Ω, П) — две однотипные алгебраические системы. Отображение h: А → В называют гомоморфизмом алгебраической системы A в алгебраическую систему B, если выполняются следующие условия:Подробнее

  • Прямые произведения алгебраических систем

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

  • Конечные булевы алгебры

    Покажем применение понятия прямого произведения алгебраических систем к теории булевых алгебр. Мы докажем здесь интересный факт, состоящий в том, что мощность любой конечной булевой алгебры есть некоторая степень двойки. Отсюда будет следовать, например, что в конечной булевой алгебре может быть 1, 2, 8, 16, 32, 64 и т.д. элементов, но не может быть, скажем, 100 или 75 элементов. Чтобы доказать сформулированное утверждение о конечных булевых алгебрах, необходимо ввести некоторые вспомогательные определения и доказать некоторые утверждения. Напомним, что мы определили булеву алгебру Вn булевых векторов размерности n (см. пример 3.11). Эта алгебра есть не что иное, как n-я декартова степень двухэлементной булевой алгебры В =({0,1}, ∨, ∧, 0, 1).Подробнее

  • Многосортные алгебры

    Многосортная алгебра — это упорядоченная пара ((A)i)i∈I, Ω), где элементы семейства множеств(A)i)i∈I называют сортами, а множество Ω, называемое многосортной сигнатурой, состоит из многосортных операций — отображений вида ω: Ai1×...× Ain → Ai0 Операцию ω называют при этом n-арной операцией типа (i0, i1, ..., in).Подробнее

  • Вопросы и задачи

    4.1. Показать, что отношение ≤ на носителе поля F является отношением линейного порядка, т.е. для любых двух элементов a, b ∈ F имеет место а ≤ b или b ≤ a.Подробнее