Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Например, пусть U есть совокупность всех подмножеств какого-либо фиксированного множества U. Отношение включения х^у для элементов X, у из VL (см. п. 1.1) является, очевидно, частичным порядком на множестве U.
Элементы a, b множества А называются сравнимыми относительно частичного порядка на этом множестве, если a Ъ или Ъ а. Частичный порядок ^ на мно- ОТНОШЕНИЯ И ОТОБРАЖЕНИЯ-
31
жестве А называется линейным порядком, если любые два элемента a, b из А сравнимы относительно
Пусть на множестве А задан частичный порядок и В = А. Элемент а Q А называется верхней границей для В в А, если b а для всех b QB. Элемент a Q А называется наибольшим в А, если а служит верхней границей для самого множества А. Элемент т Q А называется максимальным в А, если каждый элемент х из А либо не сравним с т, либо х т.
Ясно, что если множество А обладает наибольшим элементом а, то а будет единственным максимальным элементом в А. Аналогично определяются понятия нижней границы подмножества В в А, наименьшего и минимального элементов в А.
Например, если А = {1, 2, 3, 4, 5} и х ^ у означает, что у делится на х без остатка, то 1 есть наименьший элемент в Л, а 3, 4, 5 — максимальные элементы в А. Наибольшего элемента в А в данном примере нет.
Множество А, на котором задан какой-нибудь частичный (линейный) порядок, называется частично (соответственно линейно) упорядоченным. Линейно упорядоченное множество называется также цепью.
Если {А, > — частично упорядоченное множество и В — подмножество множества А, то отношение
хру <=> ж<г/ (ж, у QB)
будет, очевидно, частичным порядком на В. Обычно его обозначают тем же символом, что и заданный частичный порядок на А. Таким образом, всякое подмножество В частично упорядоченного множества {A, ) относительно отношения является частично упорядоченным.
Лемма Цорна. Каждый элемент непустого частично упорядоченного множества (А, <с^>, в котором каждая цепь (В, ) (B^A) имеет верхнюю границу, содержится в некотором максимальном элементе.
Это утверждение логически равносильно так называемой аксиоме выбора (см. п. 2.5), и поэтому будет принято нами в качестве аксиомы.
Линейно упорядоченное множество А называется вполне упорядоченным, если всякое непустое подмножество В множества А имеет наименьший элемент. 32
ОБЩИЕ ПОНЯТИЯ
[Гл. I
Во вполне упорядоченном множестве А для всякого элемента а, который не является наибольшим в А, имеется единственный элемент а' такой, что а <С а' и a' ^ х для всякого элемента х ? А, большего а. Элемент а' называется непосредственно следующим за а. В свою очередь элемент а называется непосредственно предшествующим для элемента а'. Элемент из А, не имеющий непосредственно предшествующего в А, называется предельным.
Лемма Цорна логически равносильна также следующей аксиоме.
Аксиома полной упорядочиваемо-с т и. Всякое непустое множество может быть вполне упорядочено.
Высказывания, касающиеся элементов вполне упорядоченного множества А, можно доказывать методом трансфинитной индукции, который заключается в следующем. Пусть 1 — наименьший элемент множества А и P (х) — некоторое высказывание об элементе X 6 А. Если P(I) .истинно и из истинности P (х) для всех элементов X ? А, строго меньших а, следует истинность высказывания P (а), то можно утверждать, что P (х) истинно для всех X ? А. Действительно, пусть В есть совокупность тех элементов у из А, для которых высказывание P (у) ложно. Если Вф 0, то В имеет наименьший элемент, который мы обозначим а. Так как P (1) истинно, то а Ф 1, и поэтому а >¦ 1. Для всех элементов X, строго меньших а, высказывание P (х) истинно. По условию P (а) тоже должно быть истинным, и мы получили противоречие.
1.6. Многозначные и частичные отображения. Понятия отображения и эквивалентности, рассмотренные в предыдущих пунктах, допускают полезные обобщения, которые теперь й будут изложены.
Пусть а — произвольное отношение, определенное на паре множеств А, В. Как и в случае отображений, элемент b ? В будем называть образом элемента а Є А, если aab истинно. В отличие от «настоящих» отображений, теперь, вообще говоря, могут существовать такие элементы в А, у которых или совсем нет образа в В, или есть несколько образов в В. По этой причине отображения, отвечающие произвольному отношению а, называются частичными ОТНОШЕНИЯ И ОТОБРАЖЕНИЯ- 34
мулътиотображениями из множества А в множество В.
Если а — частичное мультиотображение из множества А в множестве В, то, как и в случае обычных отображений, полагают
аа — {х I аах} (а ? А),
Aia = {х I аах, а 6 A1) (.A1 S А).
Таким образом, .A1OC — это совокупность всех образов всех элементов подмножества A1. Множество 5а-1 называется областью определенности, a Aa — совокупностью значений частичного мультиотображения а.
Если частичное мультиотображение а из множества А в множество В таково, что для каждого элемента а ? А множество аа либо состоит лишь из одного элемента, либо является пустым, то а называется частичным отображением из А в В.
Для каждых отношений а, ?, определенных соответственно на множествах А, В я В, С, очевидно, справедливо равенство
