Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
/ (аи . . ., ап) = И,
называется (га-арным) отношением на А, отвечающим предикату /. Обратно, пусть задано какое-нибудь га-арное отношение а gl" на А. Полагая
мы получим га-арный предикат, отвечающий отношению ct. Таким образом, re-арные предикаты и га-арные отношения на произвольном множестве находятся во взаимно однозначном соответствии.
Характеристической функцией re-арного отношения а, определенного на множестве А, называется га-арная функция X из А" в JV, определенная таблицей
/(*) = 0.(х-1), g(x)= 0-(х-2)
И, если (а1( ..ап)?а, Л, если (A1, . .., ап)$а,
1, если (O1, ..., ап) ? а, 0, если (O1, ..., ап)$ а. MO ДЁ JlIl Й АЛГЕБРЫ
45
Частичной ¦ характеристической функцией «.-арного отношения a gi" называется частичная /г-арная функция, определенная таблицей
{1, если (of, ..., ап) Qa,
/ \ > неопределенность, если (oj, ..., ап) $ а.
Например, если ф, -ф — характеристическая и соответственно частичная характеристическая функции для отношения < на N, то
Ф(1, 3) = г|з (1, 3) = 1, ф(1, 1) = О, (1, 1) — неопределенность.
Подмножества множества А — это унарные отношения на А. Поэтому характеристическая функция подмножества — это функция одного переменного, равная 1 в точках подмножества и равная 0 в точках, не принадлежащих подмножеству. Частичная характеристическая функция подмножества равна 1 в точках подмножества и неопределенная вне подмножества.
В дальнейшем мы часто не будем различать отношение и отвечающий ему предикат и будем для предиката P вместо P (X1, . . ., хт) =И писать просто P (X1, . . ., хт). В частности, равенство
P (х, у) = Q (х, у)
для предикатов Р, Q мы иногда будем писать в виде соотношения
P (х, у) <?> Q (х, у).
Согласно определению каждой частичной /г-арной операции F на множестве А отвечает подмножество декартовой степени An*1, состоящее из тех последовательностей (аь . . ., ап, ап+1) из Лп+1, для которых значение F (al7 . . ., ап) частичной операции F определено и равно ап+1. Иногда это подмножество называют графиком частичной операции F и говорят, например, о характеристической функции графика частичной операции вместо того, чтобы говорить о характеристической функции самой частичной операции. С принятой нами точки зрения оба выражения означают одно и то же. 46
ОБЩИЕ ПОНЯТИЯ
[Гл. I
Иногда приходится рассматривать нульарные операции и нульарные предикаты. Нульарной операцией на множестве А называется фиксированный элемент из этого множества, а нульарным предикатом — истина или ложь.
Если на множестве А заданы операция F и предикат Р, то их арности условимся обозначать в дальнейшем соответственно п (F), п (P).
2.2. Алгебраические системы. Пусть а, ? — некоторые порядковые числа. Типом т порядка (а, ?) условимся называть пару отображений W (а) N, W(?)—>N множеств W (a), W (?) в множество N = {0, 1, 2, . . .}. Тип т будем записывать в виде
т = (т0, . . ., ть . . .; п0, . . пп, . . .)
(I < а, -л < ?).
Два типа т, т' будут считаться равными тогда и только тогда, когда они имеют один и тот же порядок (а, ?) и гп\ = mi, пц = Uvl для всех | <С а и для всех т] < ?. Тип т называется конечным, если числа а, ?, составляющие его порядок (а, ?), конечны.
Алгебраической системой (или просто системой) типа т называется объект ЭД — (A, Qf, Qp), состоящий из трех множеств: непустого множества А, множества операций ?2^. — {F0, . . ., . . .}, определенных на множестве А для каждого ? << а, и множества предикатов = = (P0) • • -і Рт]7 • • ¦}» заданных на множестве А для каждого т] <С ?, причем арности рассматриваемых операций и предикатов должны удовлетворять условиям:
п (Fi) = m| для всех | < а и п (Pti) = п^ для всех T]<?.
Множество А называется носителем или основным множеством системы И, а его элементы—элементами системы SI. Мощность IА I множества А называется мощностью или порядком системы St и обозначается также | St |.
В отличие от других операций и предикатов, которые могут быть определены на множестве А, операции F^ (I < а) и предикаты Ptl (т] < ?) называются основными или главными. Значения главных нульарных операций системы называются главными или выделенными элементами этой системы. модели и алгебрьі
47
Объединяя множества Qjj- и Qp системы И и полагая Q = Qjf U ЙР, мы сможем записать систему SI более кратко: 91 - {A, Й>.
Если даны две системы Ш = (А, Й), = (В, Q') одного и того же типа т, имеющего порядок (а, ?), то главные операции F^ ? й, G^ Q й' для каждого ? <С a, a также главные предикаты Pv Q й, <?n 6 Для каждого т] <С ? называются одноименными. Часто одноименные главные операции и одноименные главные предикаты однотипных алгебраических систем 93, ... обозначают в каждой из рассматриваемых систем одинаково, скажем F0, ... . . ., Fb . . ., P0, . . ., Pti, . . . (I < а, г] < ?).
Сиртема 21 = (А, й) называется конечной, если множество А конечно.
Система 31 конечного типа записывается в виде = = (A-r F0, . . ., Fs-i; P0, - • ., Pui) или в виде 91 = = {А-, F1, . . ., Fs; P1.....Pt).
Алгебраическая система Ш = {А, й} называется алгеброй, если ЙР =0, и моделью (или реляционной системой), если Qir = 0.
