(45:1) Соотношение
(45:12). \W = \[jD*(e0)
устанавливает взаимно однозначное соответствие между всеми решениями V для Е (е0) и всеми решениями W для F(eQ).
Это утверждение будет доказано в следующем пункте.
45.5. Доказательство теоремы
45.5.1. Мы начнем с доказательства некоторых вспомогательных лемм.
Первая лемма состоит в совершенно очевидном утверждении, имеющем, однако, широкие приложения:
-У ~>
(45: J) Пусть два обобщенных дележа у = {у4, ..., уп} и б = {б1? ..., дп}
связаны соотношением
(45:13) yt}>di для всех £ = 1, ...,тг;
тогда для каждого а из а в-у следует as-б. Смысл этого результата состоит, очевидно, в том, что соотношение
-У ->
(45:13) выражает в некотором смысле подчиненность дележа б дележу уу несмотря на нетранзитивность отношения доминирования. Однако эта подчиненность не столь полна, как этого можно было бы ожидать. Так,
из соотношения 6 £- (3 нельзя сделать представляющийся правдоподобным
вывод о том, что у £- р, потому что из эффективности множества S для б
->
может и не следовать его эффективность для 7. (Читатель должен вспомнить основные определения п. 30.1.1.)
Нужно также заметить, что утверждение (45:J) является содержательным только потому, что мы обобщили понятие дележа. Для наших
старых определений (см. п. 42.4.1) мы должны были бы иметь =
i=l i=l
следовательно, из угЬг для всех i = 1, . . ., п должно было быть
-у ->
уг = 8j при всех i = 1, . . ., п, т. е. 7 = б.
45.5.2. Приведем теперь леммы, непосредственно осуществляющие требуемое доказательство теоремы (45:1).
->->-> ->
(45:К) Если а е- р, где a - исключенный дележ, a £ F (е0),
->->-> а р £ Е (е0), то существует дележ а, для которого а £- р, причем
а - исключенный дележ и а 6 Е (е0).
Доказательство. Пусть S - множество, участвующее в условиях (30:4:а) - (30:4:с) из п. 30.1.1 применительно к отношению
-У -У
доминирования a е- р. Из равенства S = I следовало бы, что для всех i = 1, . . ., п аг > рь так что
Sa,-v(/)>S pi-v(I).
Но так как а £ F (е0), a р f£ (е0), должно быть 2а* - v (-0 = ео =
- 2Рг ~ v 00» что противоречит предыдущему неравенству.
Следовательно, S Ф I. Выберем поэтому некоторое i0 = 1, . . ., п, не принадлежащее S. Положим ее = {av . . ., ап}, где
а\ = аг- для г =5= t0»
a 80 выбрано так, что ]а[ - v (/) = е0- Тогда для всех г будет
а\ аг-; следовательно, дележ а является исключенным и, очевидно, принадлежит Е (е0). Кроме того, так как ai = at для i Ф i0, а значит,
и для всех i £ S, то а е- Р влечет а е- р.
(45:L) Каждое решение W для F (е0) имеет вид (45:12) из теоремы
(45:1) для единственного множества V Е (е0) *).
Доказательство. Очевидно, рассматриваемое множество V, если оно вообще существует, есть пересечение MV [] Е (е0), так что оно единственно. Для того чтобы соотношение (45:12) выполнялось для
Y = Wr)E(e0)4
нам необходимо только, чтобы остаток W был равен D*(e0), т. е. чтобы (45:14) W-E(e0) = D*(e0).
Докажем поэтому равенство (45:14).
Каждый элемент множества D* (е0) является исключенным и принадлежит F (е0), так что ввиду (45: G) он принадлежит W. Кроме того, он не принадлежит Е (е0), так что он принадлежит W - Е (е0). Таким образом,
(45:15) W-£WI)*W.
Если, кроме того, (45:16) W-E(e0)<=D*(e0),
то (45:15) и (45:16) вместе дадут нам (45:14), что и требуется. Предположим поэтому, что включение (45:16) неверно. В соответствии с этим предположением мы рассмотрим дележ
а = {(*!, . . ., ап}, принадлежащий W - Е (е0) и не принадлежащий
D* (е0). Тогда а принадлежит F (е0), но не принадлежит Е (е0), так что
- v (/) < е0. Так как дележ а не принадлежит D* (е0), он не может
быть исключенным. Поэтому существует такое непустое множество S, что 2<*г < v (S).
i£S
*) Мы еще не утверждаем, что это множество V есть решение для Е (е0),- это будет установлено в (45:М).
Положим теперь а = {а, . . ., ап}, где
а1 = аг-{-г для i, принадлежащих S, al = аг для г, не принадлежащих S, а 8>0 выбрано так, что все еще
2сц-у(/)е0 и Saiv(5).
г=1 i£S
Такой дележ а принадлежит F (е0). Если он не принадлежит W,
то (так как W есть решение для F (е0)) существует такой дележ Р £ W,
-> ->
что Р е- а. Так как для всех i оца*, отсюда следует ввиду (45:J), что
р е- а. Но это невозможно, так как и р, и а принадлежат решению W.
Следовательно, дележ а должен принадлежать W. Но для всех i £ S а[ >
>06jH 2aiv()- Поэтому а е- а. Но это отношение противоречит тому,
что оба дележа, а и а, принадлежат решению W.
(45:М) Множество V из леммы (45:L) есть решение для Е (е0).
Доказательство. Очевидно, что V Е (е0) и V удовлетворяет условию (44:Е:а) из п. 44.7.3 вместе с W (которое является решением для F (е0)), так как V W. Таким образом, нам необходимо только проверить свойство (44:Е:Ь) из п. 44.7.3.
Рассмотрим дележ р £ Е (е0), не принадлежащий V. Тогда Р принадлежит и F (е0), но не принадлежит W; следовательно, существует такой ->->-> ->
дележ а £ W, что а е- р (W есть решение для F (е0)). Если этот дележ а
->
принадлежит Е (е0), то он принадлежит W [}Е (е0) = V, т. е. а должно
принадлежать Е (е0), причем а е- р.
Если же дележ а не принадлежит Е (е0), то он принадлежит W - Е (е0) = Z)* (е0) и, следовательно, является исключенным. Таким
образом, ос е- р, дележ а - исключенный и принадлежащий F (е0). Сле-довательно, ввиду (45:К) существует такой исключенный дележ а, принадлежащий Е (во), что а е- р. Ввиду (45:G) этот дележ а принадлежит W (так как Е (е0) <=- F (е0), a W есть решение для Е (е0)\); следовательно,
он принадлежит Wfl (о) = V. Таким образом, мы получаем, что -> -> ->
а £ Е (е0), причем а е- р.
Итак, условие (44:Е:Ь) из п. 44.7.3 выполнено в любом случае.
(45:N) Если V есть решение для Е (е0), то W, определенное соот-
ношением (45:12) теоремы (45:1), есть решение для F (е0).
Доказательство. Очевидночто W F (е0), так что мы должны доказать свойства (44:Е:а) и (44:Е:Ь) из п. 44.7.3.
Свойство (44:Е:а). Предположим, что для двух дележей а и р из W
имеет место а е- р. Ввиду отношения а е- р и свойства (45:D) невозможно,
чтобы дележ Р был исключенным. Поэтому р не содержится в D* (е0)