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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

Сюръективный гомоморфизм АС называют эпиморфизмом (или наложением), а инъ-
ективный гомоморфизм — мономорфизмом (или вложением), т.е. также, как и соответ-
ствующе отображения. Гомоморфизм АС в себя называется эндоморфизмом. Изомор-
физм АС на себя называют автоморфизмом. С каждой АС A связаны моноид эндомор-
физмов End (A) и группа автоморфизмов Aut (A) (группа обратимых элементов моно-
ида End (A)).
Класс алгебраических систем называется абстрактным, если если с каждой АС в нём
лежат все системы, ей изоморфные.
Теорема 3.2. Всякий сюръективный эндоморфизм конечной системы есть изоморфизм.
Доказательство. Рассмотрим АС A = h A, Op A, Rel A i с конечным носителем A и на-
ложение ϕ : A → A. Нам надо показать, что ϕ тождественно согласовано с отношениями
A и ϕ(A).
Пусть r — произвольное отношение арности m из Rel A. Поскольку ϕ — гомо-
морфизм, то для любого набора a
1
, . . . , a
m
из m элементов носителя A истина им-
пликация r(a
1
, . . . , a
m
)
¡
¢
r(ϕ(a
1
), . . . , ϕ(a
m
)), т.е. для её посылки и заключения могут
иметь место только следующие пары истинностных значений посылки и заключения:
(0, 0), (0, 1), (1, 1). Теорема будет доказана, если выяснится, что второй случай в наших
условиях не реализуется.
Наложение множества на себя является биекцией и, в силу конечности A, переста-
новкой его элементов конечной степени. Тогда существует натуральное d такое, что ϕ
d
есть тождественная перестановка. Пусть отношение r(ϕ(a
1
), . . . , ϕ(a
m
)) выполнено. От-
сюда следует, что, поскольку ϕ — гомоморфизм, для любого натурального t выполне-
но r(ϕ
t
(a
1
), . . . , ϕ
t
(a
m
)). При t = d получаем, что выполнено и r(a
1
, . . . , a
m
). Таким
образом, r(ϕ(a
1
), . . . , ϕ(a
m
))
¡
¢
r(a
1
, . . . , a
m
), и случай (0, 1) невозможен.
3.3 Конгруэнции и гомоморфные системы
3.3.1 Конгруэнции и фактор-системы
Определение 3.6. Однородное отношение ρ на множестве A называется стабильным
относительно операции f местности n на A, если при n > 0 для любых элементов
a
1
, a
1
0
, . . . , a
n
, a
n
0
∈ A справедливо
n
^
i=1
a
i
ρa
i
0
⇒ f (a
1
, . . . , a
n
)ρf(a
1
0
, . . . , a
n
0
) ,
а при n = 0 — ρ рефлексивно.
Аналогично может быть определено стабильное отношение произвольной арности.
Стабильность отношения означает, что если наборы аргументов функции находятся в
данном отношении, то и результаты операции также находятся в этом отношении.
Однородное отношение ρ на АС h A, Op A, Rel A i называется стабильным на этой
АС, если оно стабильно относительно любой операции из Op A. Например, полное O и
диагональное M отношения стабильны на любой АС.
Определение 3.7. Стабильная на АС эквивалентность называется конгруэнцией на ней.
Ясно, что полное и диагональное отношения являются конгруэнциями на любой АС.
С каждой АС A связана решётка конгруэнций Con(A), которая оказывается полной
подрешёткой в решётке её подсистем Sub (A). Решётка Con(A) имеет универсальные
75
   Сюръективный гомоморфизм АС называют эпиморфизмом (или наложением), а инъ-
ективный гомоморфизм — мономорфизмом (или вложением), т.е. также, как и соответ-
ствующе отображения. Гомоморфизм АС в себя называется эндоморфизмом. Изомор-
физм АС на себя называют автоморфизмом. С каждой АС A связаны моноид эндомор-
физмов End (A) и группа автоморфизмов Aut (A) (группа обратимых элементов моно-
ида End (A)).
   Класс алгебраических систем называется абстрактным, если если с каждой АС в нём
лежат все системы, ей изоморфные.

Теорема 3.2. Всякий сюръективный эндоморфизм конечной системы есть изоморфизм.

Доказательство. Рассмотрим АС A = h A, Op A, Rel A i с конечным носителем A и на-
ложение ϕ : A → A. Нам надо показать, что ϕ тождественно согласовано с отношениями
A и ϕ(A).
    Пусть r — произвольное отношение арности m из Rel A. Поскольку ϕ — гомо-
морфизм, то для любого набора a1 , . . . , am из m элементов носителя A истина им-
пликация r(a1 , . . . , am ) ¡¢ r(ϕ(a1 ), . . . , ϕ(am )), т.е. для её посылки и заключения могут
иметь место только следующие пары истинностных значений посылки и заключения:
(0, 0), (0, 1), (1, 1). Теорема будет доказана, если выяснится, что второй случай в наших
условиях не реализуется.
    Наложение множества на себя является биекцией и, в силу конечности A, переста-
новкой его элементов конечной степени. Тогда существует натуральное d такое, что ϕd
есть тождественная перестановка. Пусть отношение r(ϕ(a1 ), . . . , ϕ(am )) выполнено. От-
сюда следует, что, поскольку ϕ — гомоморфизм, для любого натурального t выполне-
но r(ϕt (a1 ), . . . , ϕt (am )). При t = d получаем, что выполнено и r(a1 , . . . , am ). Таким
образом, r(ϕ(a1 ), . . . , ϕ(am )) ¡¢ r(a1 , . . . , am ), и случай (0, 1) невозможен.

3.3     Конгруэнции и гомоморфные системы
3.3.1   Конгруэнции и фактор-системы
Определение 3.6. Однородное отношение ρ на множестве A называется стабильным
относительно операции f местности n на A, если при n > 0 для любых элементов
a1 , a1 0 , . . . , an , an 0 ∈ A справедливо
                         n
                         ^
                               ai ρai 0 ⇒ f (a1 , . . . , an )ρf (a1 0 , . . . , an 0 ) ,
                         i=1

а при n = 0 — ρ рефлексивно.

   Аналогично может быть определено стабильное отношение произвольной арности.
Стабильность отношения означает, что если наборы аргументов функции находятся в
данном отношении, то и результаты операции также находятся в этом отношении.
   Однородное отношение ρ на АС h A, Op A, Rel A i называется стабильным на этой
АС, если оно стабильно относительно любой операции из Op A. Например, полное O и
диагональное M отношения стабильны на любой АС.

Определение 3.7. Стабильная на АС эквивалентность называется конгруэнцией на ней.

   Ясно, что полное и диагональное отношения являются конгруэнциями на любой АС.
   С каждой АС A связана решётка конгруэнций Con(A), которая оказывается полной
подрешёткой в решётке её подсистем Sub (A). Решётка Con(A) имеет универсальные

                                                        75

Страницы