соотношений (65:В:а) не выполняется (так как упорядочение частичное, это возможно), называются несравнимыми (в смысле отношения cf).

Легко привести примеры частичного упорядочения: точки на плоскости, если xofy означает, что ордината х больше, чем у (см. сноску 3 на стр. 589). Мы можем определить хоРу как отношение, состоящее в том, что обе координаты х больше соответствующих координат у г). Другой хороший пример получается в области положительных целых чисел, если в качестве хоРу рассматривать отношение делимости х на у, исключая равенство.

65.3.3. Для обоих введенных понятий упорядочения сохраняется (65:А:Ь), в то время как (65:А:а) превращается (ослабляясь) в (65:В:а). Это подчеркивает важность (65:А:Ь), называемого свойством транзитивности 2). Предпримем теперь дальнейшее ослабление комбинации (65:В:а) и (65:А:Ь) так, чтобы (65:А:Ь) было тоже существенно изменено.

Заметим сначала, что (65:В:а) эквивалентно следующим двум условиям:

(65:С:а) Никогда хоРх.

(65:С:Ь) Никогда одновременно хоРу и уоРх.

В самом деле, (65:В:а) исключает три комбинации х = у, хоРу\ х = уг у£Рх\ хоРу, уоРх. Первая и вторая из них - это всего лишь два способа написания (65:С:а), а третья - это в точности (65:С:Ь).

Докажем теперь следующее.

(65:D) Рассмотрим утверждение:

(Ат) Неверно хх0, х2хи . . ., xm<SPxm-u где х0 = хт и х0г хх, . . ., m ! принадлежат D. Тогда мы имеем:

(65:D:a) (65:В:а) эквивалентно (At) и (А2).

(65:D:b) Из (65:В:а) и (65:А:Ь) следуют все (Ах), (А2), (А3), . . .

Доказательство. (65:D:a). Ясно, что (At) есть (65:С:а) а А2 есть (65:С:Ь).

Запись отношения (Ат) в обратном порядке и применение (65:А:Ь) т - 1 раз дает хтоРх0. Так как хт = х0, это означает х0х0, что противоречит (65:В:а).

Эти результаты наводят на мысль рассматривать совокупность всех условий (At), (А2), (Аз), . . . Они следуют из (65:В:а) и (65:А:Ь), т. е. из» частичного упорядочения, и представляют, как окажется, дальнейшее ослабление этого свойства.

Введем в соответствии с этим следующее определение:

(65:D:c) Отношение оР ациклично, если оно удовлетворяет всем условиям (А±), (А2), (А3), . . .

Читатель поймет, почему мы называем это свойство отношения ацикличностью: если какое-либо (Ат) неверно, то имеется цепочка отношений хХоРхо, x2oPxt, ..., хтъРхтЛ, которая является циклом, так как ее последний элемент хт совпадает с первым д;0.

г) Заметим, что это близко к правдоподобному типу частичной упорядоченности* полезностей в смысле последнего замечания из п. 3.7.2. Каждое мыслимое событие-может зависеть от двух числовых характеристик, которые обе надо увеличить для того, чтобы породить ясное и воспроизводимое предпочтение.

2) Некоторые другие важные отношения, совсем иной природы, чем упорядочение, также обладают этим свойством: например, равенство х = у.

Мы уже отмечали, что ацикличность следует из частичной упорядоченности (это, очевидно, и является содержанием (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(у.