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

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

Напомним, что п-местным предикатом (отношением) на множестве А называется любое подмножество множества Аⁿ; п-местной алгебраической операцией на множестве А называется функция F:Aⁿ→A, где – n-я декартова степень множества А. Отметим, что поскольку операция F является функцией, для любого набора (x₁,…,x_n)Aⁿ результат применения операции F(x₁,…,x_n) однозначно определен. Так как область значений операции F лежит в множестве А, то будем говорить, что операция F замкнута на множестве А.

Сигнатурой Σназывается совокупность предикатных и функциональных символов с указанием их местности. Константным символом или простоконстантойназывается 0-местный функциональный символ. Еслиα ‑ функциональный или предикатный символ, то его местность обозначается черезμ(α).Частоп-местные предикатные и функциональные символы будем обозначать соответственно черезР⁽ⁿ⁾иF⁽ⁿ⁾, возможно с индексами. Если в рассматриваемой сигнатуре используются стандартные символы, такие, например, как + для операции сложения, ≤ для отношения порядка, | для отношения делимости, 0 для константного символа и другие, то мы просто пишемΣ={≤}, Σ={≤,+, ... , 0} и т.д.

Алгебраической системой сигнатурыΣназывается пара =гдеА– непустое множество и каждомуn-местному предикатному (функциональному) символу изΣпоставлен в соответствиеn-местный предикат (соответственно операция) наА. МножествоА называетсяносителем, илиуниверсумом алгебраической системы. Предикаты и функции, соответствующие символам изΣ, называются ихинтерпретациями. Обозначать интерпретации будем теми же буквами, что и соответствующие символы сигнатуры, возможно с индексомA. Заметим, что интерпретацией любого константного символа является некоторый элемент изА. ЕслиΣ={α₁,…, α_n} – конечная сигнатура, то в записифигурные скобки будем опускать.

Пример 1. 1) Наборявляется алгебраической системой с двумя двухместными операциями.

2. Набор является алгебраической системой с бинарным отношением ≤, двухместными операциями +,, одноместной операцией':п→n+1 и нуль-местной операций 1.

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

4. Набор является алгебраической системой, гдет.е. множество всех подмножеств множества

Алгебраическая система =называетсяподсистемой системы=(обозначается), если выполняются следующие условия:

а) АВ;

б) для любого функционального символа F ⁽ⁿ⁾Σи любых элементовa₁,a₂,…,a_nA выполняется равенствоF_A(a₁,a₂,…,a_n)=F_B(a₁,a₂,…,a_n), т.е. интерпретации символаFдействуют одинаково на элементах изА;

в) для любого предикатного символа Р⁽ⁿ⁾Σ справедливо равенствоP=∩Aⁿ, т.е. предикатсодержит в точности те кортежи предиката, которые состоят из элементов множестваА.

Теорема 1. Если ‑ алгебраическая система,XВ, X≠Ø, то существует единственная подсистема(Х)=алгебраической системы такая, чтоXВ(Х) и (Х)для любой подсистемы алгебраической системы, для которойXА.

Подсистема (Х) из теоремы 1 называетсяподсистемой алгебраической системы, порожденной множеством X.

Для описания элементов подсистемы (Х) определим индукцией по построению понятиетерма сигнатурыΣ:

1. переменные и константные символы из Σсуть термы;

2. если FΣ‑ n-местный функциональный символ,t₁,t₂,…,t_n‑ термы, тоF(t₁,t₂,…,t_n)‑ терм;

3. никаких термов, кроме построенных по пп. 1,2, нет. Множество всех термов сигнатуры Σ обозначается черезТ(Σ).

Под сложностьютерма будем понимать число символов, входящих в терм.

Пример 2.

1) Термами сигнатуры Σ={+,∙,≤,0} будут, например,0, x, x+y, z∙(x+z)+0∙y, а x+y≤(0+х)x термом не является.

2) Если Σ={ƒ⁽³⁾, g⁽¹⁾, h⁽²⁾} ‑ функциональная сигнатура, то выраженияh(ƒ(x₁, x₂, x₃), g(x₂)), g(ƒ(h(x₁, x₂), x₁, g(x₂))– термы, аh(x₁, ƒ(x₁, x₃)) термом не является.

Пусть t(x₁,…,x_k) ‑ терм изT(Σ), все переменные которого содержатся в множестве {x₁,…,x_k},=‑ алгебраическая система.Значение терма t на элементахa₁,…,a_kA (t(a₁,…,a_k)) определяется по индукции:

1. если t есть переменнаяx_i (константный символс), то значениеt естьа_i (с);

2. если tF(t₁,…, t_n), гдеF ⁽ⁿ⁾Σ, t₁(x₁,…,x_k),…,t_n(x₁,…,x_k)Т(Σ) и значения термовt₁,…, t_nна элементахa₁,…,a_kравныb₁,…,b_n то значение термаtестьF(b₁,…,b_n).

Теорема 2. Если=‑ алгебраическая система,Ø≠XB, тоB(Х)={t(a₁,…,a_n) | tT(Σ), a₁,…,a_nX}.