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

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

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

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

Алгебраической системой сигнатуры Σ называется пара = где А – непустое множество и каждому n -местному предикатному (функциональному) символу из Σ поставлен в соответствие n -местный предикат (соответственно операция) на А. Множество А называется носителем, или универсумом алгебраической системы t wx: val=" Cambria Math" /> < w: i/> < /w: rPr> < m: t> A< /m: t> < /m: r> < /m: oMath> < /m: oMathPara> < /w: p> < w: sectPr wsp: rsidR=" 00000000" > < w: pgSz w: w=" 12240" w: h=" 15840" /> < w: pgMar w: top=" 1134" w: right=" 850" w: bottom=" 1134" w: left=" 1701" w: header=" 720" w: footer=" 720" w: gutter=" 0" /> < w: cols w: space=" 720" /> < /w: sectPr> < /w: body> < /w: wordDocument> "> . Предикаты и функции, соответствующие символам из Σ, называются их интерпретациями. Обозначать интерпретации будем теми же буквами, что и соответствующие символы сигнатуры, возможно с индексом A. Заметим, что интерпретацией любого константного символа является некоторый элемент из А. Если Σ ={ α ₁, …, α _n } – конечная сигнатура, то в записи фигурные скобки будем опускать.

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

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

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

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

Алгебраическая система t wx: val=" Cambria Math" /> < w: i/> < /w: rPr> < m: t> A< /m: t> < /m: r> < /m: oMath> < /m: oMathPara> < /w: p> < w: sectPr wsp: rsidR=" 00000000" > < w: pgSz w: w=" 12240" w: h=" 15840" /> < w: pgMar w: top=" 1134" w: right=" 850" w: bottom=" 1134" w: left=" 1701" w: header=" 720" w: footer=" 720" w: gutter=" 0" /> < w: cols w: space=" 720" /> < /w: sectPr> < /w: body> < /w: wordDocument> "> = называется подсистемой системы = (обозначаетсяt wx: val=" Cambria Math" /> < w: i/> < /w: rPr> < m: t> A< /m: t> < /m: r> < /m: oMath> < /m: oMathPara> < /w: p> < w: sectPr wsp: rsidR=" 00000000" > < w: pgSz w: w=" 12240" w: h=" 15840" /> < w: pgMar w: top=" 1134" w: right=" 850" w: bottom=" 1134" w: left=" 1701" w: header=" 720" w: footer=" 720" w: gutter=" 0" /> < w: cols w: space=" 720" /> < /w: sectPr> < /w: body> < /w: wordDocument> "> t wx: val=" Cambria Math" /> < w: i/> < /w: rPr> < m: t> B< /m: t> < /m: r> < /m: oMath> < /m: oMathPara> < /w: p> < w: sectPr wsp: rsidR=" 00000000" > < w: pgSz w: w=" 12240" w: h=" 15840" /> < w: pgMar w: top=" 1134" w: right=" 850" w: bottom=" 1134" w: left=" 1701" w: header=" 720" w: footer=" 720" w: gutter=" 0" /> < w: cols w: space=" 720" /> < /w: sectPr> < /w: body> < /w: wordDocument> "> ), если выполняются следующие условия:

а) А В;

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

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

Теорема 1. Если ‑ алгебраическая система, X В, X≠ Ø, то существует единственная подсистема (Х)= алгебраической системы такая, что X В(Х) и (Х) t wx: val=" Cambria Math" /> < w: i/> < /w: rPr> < m: t> A< /m: t> < /m: r> < /m: oMath> < /m: oMathPara> < /w: p> < w: sectPr wsp: rsidR=" 00000000" > < w: pgSz w: w=" 12240" w: h=" 15840" /> < w: pgMar w: top=" 1134" w: right=" 850" w: bottom=" 1134" w: left=" 1701" w: header=" 720" w: footer=" 720" w: gutter=" 0" /> < w: cols w: space=" 720" /> < /w: sectPr> < /w: body> < /w: wordDocument> "> для любой подсистемы алгебраической системы t wx: val=" Cambria Math" /> < w: i/> < /w: rPr> < m: t> B< /m: t> < /m: r> < /m: oMath> < /m: oMathPara> < /w: p> < w: sectPr wsp: rsidR=" 00000000" > < w: pgSz w: w=" 12240" w: h=" 15840" /> < w: pgMar w: top=" 1134" w: right=" 850" w: bottom=" 1134" w: left=" 1701" w: header=" 720" w: footer=" 720" w: gutter=" 0" /> < w: cols w: space=" 720" /> < /w: sectPr> < /w: body> < /w: wordDocument> "> , для которой X А.

Подсистема (Х) из теоремы 1 называется подсистемой алгебраической системы t wx: val=" Cambria Math" /> < w: i/> < /w: rPr> < m: t> B< /m: t> < /m: r> < /m: oMath> < /m: oMathPara> < /w: p> < w: sectPr wsp: rsidR=" 00000000" > < w: pgSz w: w=" 12240" w: h=" 15840" /> < w: pgMar w: top=" 1134" w: right=" 850" w: bottom=" 1134" w: left=" 1701" w: header=" 720" w: footer=" 720" w: gutter=" 0" /> < w: cols w: space=" 720" /> < /w: sectPr> < /w: body> < /w: wordDocument> "> , порожденной множеством X.

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

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

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

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

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