Мы уже отмечали, что ацикличность следует из частичной упорядоченности (это, очевидно, и является содержанием (65:D:b), а значит, тем более и из линейной упорядоченности. Остается показать, что фактически ацикличность является более широким понятием, чем частичное упорядочение, т. е. что отношение может быть ациклическим, не будучи упорядочивающим (частично или линейно).

Вот примеры указанного явления. Пусть D есть множество всех целых положительных чисел, a xtfy - отношение непосредственного следования, т. е. х = у + 1. Или же пусть D - множество всех вещественных чисел, a xtfy есть отношение быть больше, но не намного, скажем не более чем на 1, т. е. отношение у + 1 х > у.

Мы закончим этот пункт замечанием, что примеры линейных или частичных упорядочений и ацикличных отношений могут быть легко умножены. Недостаток места не позволяет нам сделать это, но мы бы могли предложить это читателю в качестве полезного упражнения. Полезно также обратиться к ссылкам на литературу, указанным в сноске 1 на стр. 88 и в сноске 4 на стр. 589.

65.4. Решения для симметричного отношения и для линейного упорядочения

65.4.1. Изучим теперь схемы, о которых говорилось в конце п. 65.2,

Первая схема. Пусть отношение tf симметрично в смысле п. 30.3.2. В этом случае целесообразно вернуться назад к связи с насыщением, о котором говорилось в начале п. 65.2. Симметричность tf дает нам всю нужную информацию о решении.

Вторая схема. Пусть отношение tf линейно упорядочивающее. В этом случае мы введем обычное определение: х есть максимум в Z), если не существует такого г/, что ytfx. Иногда бывает удобно подчеркнуть связь с линейным упорядочением, называя этот х абсолютным максимумом в D. (Сравните это с соответствующим местом в описании следующей схемы.) Ясно, что D либо не имеет максимума, либо он единственный1).

Теперь мы имеем следующее утверждение:

(65:Е) Множество V является решением тогда и только тогда, когда

оно является одноэлементным множеством, состоящим из максимума в D.

Доказательство. Необходимость. Пусть V - решение. Так как D непусто, V также непусто.

Рассмотрим у 6 V. Если xtf г/, то х не может принадлежать V, а значит, существует такое и £ V, что и utfх. По транзитивности должно быть utfy, что невозможно, так как ж и, в. у принадлежат V. Следовательно, не существует таких ж(вВ1), что xtfy2), и у должен быть максимумом в D.

Таким образом, в D имеется максимум, который должен быть единственным (см. выше). Следовательно, V есть одноэлементное множество, из него состоящее.

Достаточность. Пусть х0 есть максимум в D и V = (х0). Возьмем произвольное у (из D\); то, что xtfy не верно ни для какого х £ V, означает отрицание x0tfy. А так как не может быть и ytfx0, мы получаем у = х0.

1) Доказательство. Если хну оба являются максимумами в Z>, то ytfx и xtfy исключаются и, по (65:А:а), должно быть х = у.

2) Подобная ситуация уже обсуждалась в п. 4.6.2.

Значит, такие у образуют множество V. Следовательно, V является решением.

65.4.2. Таким образом, в D нет решения V, если в нем нет максимума, в то время как решение существует и единственно, если в D максимум имеется.

Если D конечно, то, очевидно, имеет место последнее. Это интуитивно вполне правдоподобно и может быть также легко доказано. В целях завершенности, а также для того, чтобы сделать еще более очевидной параллель с соответствующими частями следующего замечания, мы тем не менее дадим его полное доказательство.

(65:F) Если множество D конечно, то в нем есть максимум.

Доказательство. Предположим противное, т. е. что в D максимума нет. Выберем произвольно xt 6 D, затем х2, для которого x2qFxu далее х3, для которого а;3Л2, и т. д. По (65:A:b) xmofxn для т > п; следовательно, по (65:А:а) хт Ф хп. Это значит, что все xi9 x2l x3l ... различны и D бесконечно.

Эти результаты показывают, что существование и единственность V равносильны существованию и единственности максимума в D.

65.5. Решения для частичного упорядочения

65.5.1. Третья схема. Отношение of является частичным упорядочением. Мы перенесем буквально на этот случай определение максимума в D из предыдущей схемы. Иногда бывает удобно указать на связь с частичным упорядочением, называя его относительным максимумом в D. (Сравните с соответствующим местом в предыдущем пункте. Это сравнение очень полезно, несмотря на следующую сноску 1.) В D может не существовать максимума, а может быть один или несколько максимумов1). Итак, относительный максимум в отличие от абсолютного не обязательно единственный 2).

Вопрос о существовании играет различную роль для относительного и абсолютного максимумов. Окажется, что важнейшим свойством теперь является следующее:

(65:G) Если у £ D не является максимумом, то существует такой максимум х, что х<$Ру.

Для абсолютного максимума, т. е. когда @ является линейным упорядочением, утверждение (65:G) выражает существование максимума 3). Для относительного максимума это не так, т. е. для частичного упорядочения из одного лишь существования (относительного) максимума не обяза-

г) Аргументы сноски 1 на стр. 591 здесь неверны, так как они зависят от (65:А:а), которое теперь ослаблено до (65:В:а).

Например, рассмотрим в качестве D единичный квадрат на плоскости и определим на нем частичное упорядочение одним из двух способов, данных в двух первых примерах в конце п. 65.3.2. Тогда максимумы в D образуют соответственно либо его верхнюю сторону, либо верхнюю и правую вместе.

2) Мы предостерегаем читателя от смешения нашего понятия относительного максимума с одноименным понятием, встречающимся в математическом анализе. Там относительным максимумом часто называется локальный максимум. Так как встречающиеся там величины численные и, следовательно, линейно упорядоченные, это не имеет ничего общего с нашей теорией.

3) Доказательство. Так как D непусто, из (65: G) следует существование максимума. Предположим противное: пусть х0 есть максимум/). Тогда для любого у, не являющегося максимумом, т. е. для у Ф х0, исключено y<fjpx0 и справедливость (65:А:а) (линейное упорядочение!) дает х0(у.

тельно вытекает (65:G). Легко привести соответствующие примеры, но это не входит в наши планы. Достаточно сказать, что (65:G) окажется подлинным обобщением условия существования абсолютного максимума (см. предыдущую схему) на случай относительного максимума (см. ниже). Теперь мы имеем следующее;

(65:Н) V есть решение тогда и только тогда, когда (65:G) выполнено (для D и оР!), а V - множество всех (относительных) максимумов.

Доказательство. Необходимость. Пусть V - решение.

Если у $ V, то существует такое х £ V, что xtfу; следовательно, у не есть максимум. Поэтому все максимумы принадлежат V.

Если у £ V, то аргументы, приведенные в ходе доказательства (65:Е) из п. 65.4.1, могут быть повторены буквально, и они доказывают, что у есть максимум.

Таким образом, V есть в точности множество всех максимумов.

Если у не есть максимум, т. е. не принадлежит V, то существует некоторое х £ V, т. е. максимум, для которого xofy; поэтому (65:G) выполняется (для D и оР).

Достаточность. Предположим, что (65:G) выполняется, и пусть V - множество всех максимумов.

Для х, у £ V невозможно хоРу, так как у - максимум. Если у (J V, т. е. не максимум, то по (65:G) существует такой х, являющийся максимумом, т. е. принадлежащий V, что xtfy. Значит, V есть решение по (65:1).

Читатель может проверить, что этот результат (65:Н) превращается в (65:Е) из п. 65.4.1, если упорядочение полное.

Утверждение (65:Н) показывает, что не существует решения V, если D и оР не удовлетворяют условиям (65:G); решение существует и единственно, если это условие выполнено.

65.5.2. Если D конечно, то, очевидно, имеет место последнее. Приведем полное доказательство.

(65:1) Если D конечно, то условие (65:G) выполняется.

Доказательство. Предположим противное, т. е. что D не удовлетворяет (65:G). Назовем элемент у исключительным, если он не максимум и ХоРу не имеет места ни для какого максимума х. Невыполнение (65:G) означает, что исключительные у существуют.

Рассмотрим некоторый исключительный у. Так как он не максимум, существует такой х, что ХоРу. Так как у исключительный, х не максимум. Если существует такой максимум и, что иоРх, то по (65:В:Ь) мы получаем шТу, что противоречит исключительности у} Следовательно, такого и не существует, т. е. элемент х тоже исключительный. Таким образом, мы получаем:

(65:J) Если элемент у исключительный, то существует такой исклю-

чительный X, ЧТО ХоРу.

Выберем теперь исключительные х и х2 так, чтобы было х2оРх, затем исключительный х3 так, чтобы было х3оРх2, и т. д. По (65:В:Ь) для m> п будет хтоРхп\ следовательно, по (65:В:а) хт Ф хп, т. е. все Xi, х2, х3, ... различны, а значит, множество D бесконечно.

(Сравним последнюю часть этого вывода с доказательством (65:F) из предыдущего пункта. Заметим, что можно заменить там (65:А:а) на более слабое (65:В:а).)