Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Необходимость соотношений (1) уже была доказана. Остается убедиться лишь в их достаточности. Из истинности отношения а\Аа и первого из равенств (1) следует, что отношение ааа~1а истинно, а это означает, что в В существует элемент Ъ, для которого истинны aab, Ьа~га. Таким образом, для каждого а ? А в В существует элемент Ъ, для которого aab истинно. Пусть существует еще какой-нибудь элемент &J ? В, для которого Cuabl истинно. Из истинности Ъ ^ar1 a, aab вытекает истинность отношения /^a-1Gcfe. Согласно (1), а~1а — и потому
Ьіа_1аЬ <j=> Ъ^цЪ b{ = Ъ.
Итак, для каждого а ? А в В существует один и только один элемент Ь, для которого aab истинно. Это означает, что а есть отображение А па. В. Аналогичным образом убеждаемся, что а-1 есть отображение 5 на 4, что и требовалось.
Теорема 2. Объединение (пересечение) двух отображений множества А в множество В тогда и только тогда является отображением, когда оба заданных отображения совпадают друг с другом.
Действительно, если а, ? — отображения А в В, то для каждого а ? А а и ? содержат лишь по одной паре вида (а, х), (а, у), где х, у Є В. Из х Ф у следовало бы, что a U ? содержит две пары (а, х), (а, у), a а П ? не содержит ни одной пары с первым элементом, равным а.
Пусть M — множество, над элементами которого можно производить какую-то операцию / (точное определение понятия операции см. в п. 2.1). Подмножество P этого множества называется замкнутым относительно операции /, если, производя операцию / над элементами подмножества Р, мы получим снова элемент этого же подмножества. Теорема 2 показывает, что все множества отображений А в A1 замкнутые относительно операции объединения, состоят лишь из одного элементами потому мало интересно, ОТНОШЕНИЯ И ОТОБРАЖЕНИЯ-
23
То же самое верно и для множеств отображений, замкнутых относительно операции пересечения. Напротив, непустые совокупности отображений А в А, замкнутые относительно операции умножения, отличаются большим разнообразием. Они называются полугруппами отображений А в А.
Непустые совокупности отображений А в А, замкнутые не только относительно операции умножения, но и относительно операции обращения, называются группами отображения А в А. Так как обращение отображения А в А тогда и только тогда является отображением, когда оно взаимно однозначно, то группы отображений состоят лишь из взаимно однозначных отображений.
1.4. Эквивалентности. Бинарное отношение а на множестве А называется отношением эквивалентности или просто эквивалентностью на А, если для любых х, у, z из А:
а) хах (рефлексивность),
б) хау у ах (симметричность),
в) хау & yaz =Ф xaz (транзитивность), где знак заменяет слово «влечет».
Пользуясь введенными выше операциями над отношениями, свойства а), б), в) можно, очевидно, представить в следующем виде:
Рефлексивность: і cz а,
Симметричность: а-1 ^ а,
Транзитивность: a2 ^ а, где і — отношение равенства. Легко заметить, что эти три условия равносильны следующим:
і а, or1 = а, а2 = а.
Систему S непустых подмножеств заданного множества А условимся называть разбиением или расслоением множества А, если каждый элемент А принадлежит одному и только одному подмножеству из системы S. Подмножества из S называются смежными классами или слоями разбиения S.
С каждым разбиением S мы свяжем бинарное отношение о на А, полагая, по определению, хау истинным тогда и только тогда, когда х ж у принадлежат одному 24
ОБЩИЕ ПОНЯТИЯ
[Гл. I
и тому же слою множества А. На рис. 1 множество А изображено в виде квадрата, а слои — в виде прямоугольников, на которые разбивается квадрат. Отношение хау истинно тогда и только тогда, когда точки х, у принадлежат одному и тому же прямоугольнику. Ясно, что отношение р есть эквивалентность. Она называется эквивалентностью, отвечающей разбиению S.
Покажем, что каждая эквивалентность о на А отвечает некоторому разбиению S. Для каждого а ? А совокупность тех х, для которых хаа, обозначим через [я]. Подмножества [а] называем смежными классами А по а. Из рефлексивности отношения о следует, что а ? [а]. Далее, если Ъ ? [а], то [Ь] = [а]. В самом деле, если X ? [а], то хоа. Соотношение Ъ ? [а] влечет boa и потому aab (симметричность а). Из хаа, aab следует xab (транзитивность о). Таким образом, [о] ^ ГЫ. Обратно, если X ? [&], то из xab, baa получаем хаа или (?] ^ \а]. Включения [а] д= [6], [Ь] ^ [а] показывают, что [а] = [?>]. Итак, различные смежные классы не имеют общих элементов и каждый элемент а 6 А содержится в своем смежном классе [а]. Поэтому система всех смежных классов А по а есть разбиение множества А. Так как элементы из А тогда и только тогда эквивалентны, когда они входят в один и тот же смежный класс, то разбиение А на смежные классы А по а и заданная эквивалентность а отвечают друг другу.
Совокупность всех смежных классов множества А по эквивалентности er обозначается через Ala и называется фактор-множеством от А по ст.
Однозначное отображение А -*-А!а, при котором каждый элемент а Є А переходит в содержащий его смежный класс [а], называется каноническим отображением А на А /ст.
