Упорядоченные множества и универсальная алгебра (вводный курс). Гуров С.И. - 69 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

тация ω есть пара функций h ω
1
, ω
2
i,
ω
1
: Op → Op A и ω
2
: Rel → Rel A ,
сопоставляющих каждому символу из Op и Rel соответственно конкретные операции
или отношения на A той же арности. Упомянутому выше неявному отношению эквива-
лентности сопоставляют предикат равенства (=).
Окончательно, алгебраическая система A задаётся пятёркой h A, Op, Rel, ω
1
, ω
2
i.
Образами интерпретации являются совокупности функций Op A ⊆ Op A и предика-
тов Rel A ⊆ Rel A на множестве A. Алгебраические системы с одинаковыми абстракт-
ными сигнатурами называют однотипными. Однотипные АС различаются носителями и
интерпретациями. Операции и отношения однотипных АС, являющиеся образами разных
интерпретаций соответствующих символов сигнатуры называют одноимёнными.
При работе с конкретными АС их записывают короче, либо в общем виде как
A = h A, Op A, Rel A i ,
либо перечислением конкретных операций и отношений
A = h A, f
n
1
1
, . . . , f
n
N
0
N
0
, r
m
1
1
, . . . , r
m
M
M
, 0, . . . , 0 i .
Элементы O p A ненулевой арности называют главными операциями, элементы Rel A —
главными отношениями, а элементы Op A нулевой арности — главными элементами
АС. Элемент носителя A, отмечаемый нульарной операцией f
0
i
будем обозначать f
0
i
(A
0
),
опуская, возможно верхний и нижний индексы у символа функции.
Приведём примеры
21
алгебраических систем.
Пример 43. Для сигнатуры σ = h f
1
, f
2
, f
3
, r
1
, c
1
, c
2
i типа h 2, 2, 1, 2, 0, 0 i построим
различные однотипные АС, выбирая различные носители и по-разному задавая интер-
претацию символов сигнатуры σ.
A
1
: supp A
1
= { 0, 1, . . . }, а элементы сигнатуры интерпретируются следующим обра-
зом:
f
1
7→ + , f
2
7→ ·
(с соответствующим переходом к инфексной записи),
f
3
(n) = n + 1 , r 7→ 6 , c
1
7→ 0 , c
2
7→ 1 .
Ясно, что такая АС описывает арифметику неотрицательных целых чисел.
A
2
: supp A
2
= supp A
1
, но сигнатурные символы интерпретируются по-другому:
f
1
7→ 0 , f
2
(m, n) = m
n
, f
3
(n) = 2n ,
r(m, n) 7→ m ∧ n = 1 , c
1
7→ 1 , c
2
7→ 1 .
Эта экзотичная АС не имеет специального названия.
A
3
: supp A
3
= P(A). Сигнатурные символы будем трактовать следующим образом:
f
1
7→ ∪ , f
2
7→ ∩ , f
3
7→
−
, r 7→ ⊆ , c
1
7→ ∅ , c
2
7→ A .
Ясно, что мы получили тотальную булеву структуру множеств.
21
См. Пинус А.Г. Основы универсальной алгебры: Учебное пособие. — Новосибирск: Изд-во НГТУ,
1998.
69
тация ω есть пара функций h ω1 , ω2 i,

                         ω1 : Op → Op A              и           ω2 : Rel → Rel A ,

сопоставляющих каждому символу из Op и Rel соответственно конкретные операции
или отношения на A той же арности. Упомянутому выше неявному отношению эквива-
лентности сопоставляют предикат равенства (=).
   Окончательно, алгебраическая система A задаётся пятёркой h A, Op, Rel, ω1 , ω2 i.
   Образами интерпретации являются совокупности функций Op A ⊆ Op A и предика-
тов Rel A ⊆ Rel A на множестве A. Алгебраические системы с одинаковыми абстракт-
ными сигнатурами называют однотипными. Однотипные АС различаются носителями и
интерпретациями. Операции и отношения однотипных АС, являющиеся образами разных
интерпретаций соответствующих символов сигнатуры называют одноимёнными.
   При работе с конкретными АС их записывают короче, либо в общем виде как

                                      A = h A, Op A, Rel A i ,

либо перечислением конкретных операций и отношений
                                                 n                    mM
                     A = h A, f1n1 , . . . , fNN0 0 , r1m1 , . . . , rM  , 0, . . . , 0 i .

Элементы Op A ненулевой арности называют главными операциями, элементы Rel A —
главными отношениями, а элементы Op A нулевой арности — главными элементами
АС. Элемент носителя A, отмечаемый нульарной операцией fi0 будем обозначать fi0 (A0 ),
опуская, возможно верхний и нижний индексы у символа функции.
   Приведём примеры21 алгебраических систем.
Пример 43. Для сигнатуры σ = h f1 , f2 , f3 , r1 , c1 , c2 i типа h 2, 2, 1, 2, 0, 0 i построим
различные однотипные АС, выбирая различные носители и по-разному задавая интер-
претацию символов сигнатуры σ.
A1 : supp A1 = { 0, 1, . . . }, а элементы сигнатуры интерпретируются следующим обра-
     зом:

                                       f1 7→ + , f2 7→ ·
                     (с соответствующим переходом к инфексной записи),
                          f3 (n) = n + 1 , r 7→ 6 , c1 7→ 0 , c2 7→ 1 .

      Ясно, что такая АС описывает арифметику неотрицательных целых чисел.

A2 : supp A2 = supp A1 , но сигнатурные символы интерпретируются по-другому:

                            f1 7→ 0 , f2 (m, n) = mn , f3 (n) = 2n ,
                            r(m, n) 7→ m ∧ n = 1 , c1 7→ 1 , c2 →
                                                                7 1.

      Эта экзотичная АС не имеет специального названия.

A3 : supp A3 = P(A). Сигнатурные символы будем трактовать следующим образом:
                                                         −
               f1 7→ ∪ ,     f2 7→ ∩ ,        f3 7→          ,    r 7→ ⊆ ,   c1 7→ ∅ ,        c2 7→ A .

      Ясно, что мы получили тотальную булеву структуру множеств.
 21
    См. Пинус А.Г. Основы универсальной алгебры: Учебное пособие. — Новосибирск: Изд-во НГТУ,
1998.

                                                      69

Страницы