Часто объектом изучения в математике служит множество вместе с определенной на нем структурой. Например, поля, формирующие основу обычной арифметики, линейные пространства, обеспечивающие связь геометрических объектов с операциями над числами, множества с выделенными на них бинарными отношениями. Все эти структуры образуют алгебраические системы, представляющие собой некоторые миры с определенными на них законами. Перейдем к точному определению алгебраической системы.
Напомним, что п-местным предикатом (отношением) на множестве А называется любое подмножество множества Аn; п-местной алгебраической операцией на множестве А называется функция F:An→A, где – n-я декартова степень множества А. Отметим, что поскольку операция F является функцией, для любого набора (x1,…,xn) An результат применения операции F(x1,…,xn) однозначно определен. Так как область значений операции F лежит в множестве А, то будем говорить, что операция F замкнута на множестве А.
Сигнатурой Σ называется совокупность предикатных и функциональных символов с указанием их местности. Константным символом или просто константой называется 0-местный функциональный символ. Если α ‑ функциональный или предикатный символ, то его местность обозначается через μ(α). Часто п-местные предикатные и функциональные символы будем обозначать соответственно через Р(n) и F(n), возможно с индексами. Если в рассматриваемой сигнатуре используются стандартные символы, такие, например, как + для операции сложения, ≤ для отношения порядка, | для отношения делимости, 0 для константного символа и другие, то мы просто пишем Σ={≤}, Σ={≤,+, ... , 0} и т.д.
Алгебраической системой сигнатуры Σ называется пара = где А – непустое множество и каждому n-местному предикатному (функциональному) символу из Σ поставлен в соответствие n-местный предикат (соответственно операция) на А. Множество А называется носителем, или универсумом алгебраической системы . Предикаты и функции, соответствующие символам из Σ, называются их интерпретациями. Обозначать интерпретации будем теми же буквами, что и соответствующие символы сигнатуры, возможно с индексом A. Заметим, что интерпретацией любого константного символа является некоторый элемент из А. Если Σ={α1,…, αn} – конечная сигнатура, то в записи фигурные скобки будем опускать.
Пример 1.1) Набор является алгебраической системой с двумя двухместными операциями.
2) Набор не является алгебраической системой, поскольку деление не является операцией на множестве , а элемент не принадлежит .
4) Набор является алгебраической системой, где т.е. множество всех подмножеств множества
Алгебраическая система = называется подсистемой системы = (обозначается ), если выполняются следующие условия:
а) А В;
б) для любого функционального символа F (n) Σ и любых элементов a1,a2,…,an A выполняется равенство FA(a1,a2,…,an)=FB(a1,a2,…,an), т.е. интерпретации символа F действуют одинаково на элементах из А;
в) для любого предикатного символа Р(n) Σ справедливо равенство P=∩An, т.е. предикат содержит в точности те кортежи предиката , которые состоят из элементов множества А.
Теорема 1.Если ‑ алгебраическая система, XВ, X≠Ø, то существует единственная подсистема (Х)= алгебраической системы такая, что X В(Х) и (Х) для любой подсистемы алгебраической системы , для которой XА.
Подсистема (Х) из теоремы 1 называется подсистемой алгебраической системы, порожденной множеством X.
Для описания элементов подсистемы (Х) определим индукцией по построению понятие терма сигнатуры Σ:
1) переменные и константные символы из Σ суть термы;
2) если F Σ ‑ n-местный функциональный символ, t1,t2,…,tn ‑ термы, то F(t1,t2,…,tn) ‑ терм;
3) никаких термов, кроме построенных по пп. 1,2, нет.
Множество всех термов сигнатуры Σ обозначается через Т(Σ).
Под сложностью терма будем понимать число символов, входящих в терм.