Книги и конспекты / Шпоры / 7
.pdf7.Доминирование. Теорема о доминировании (формулировка).
Минимальный и максимальный элемент. Теорема о нумерации элементов конечного частично упорядоченного множества. Верхняя и нижняя границы.
Лемма о границах.
Определение доминирования. Пусть P = [S, ≤]- частично упорядоченное множество, а a и b - его элементы. Будем говорить, что a
доминирует над b, если a > b, но ни для какого x S не верно, что a > x > b.
Теорема о доминировании (формулировка). Пусть a < b в конечном частично упорядоченном множестве P. Тогда P содержит, по крайней мере,
одну цепь x0 a x1 ... xl b , в которой каждый из элементов xi (i =1, . . . , l) доминирует над xi 1 .
Определение (минимальный и максимальный элемент).
Элемент m частично упорядоченного множества [S, ≤] называется минимальным, если не существует такого элемента x S, что x<m.
Элемент m называется максимальным, если не существует такого элемента x S, что x > m.
Теорема о нумерации.
Пусть [S, ≤], S {s1 ,..., sn } - конечное частично упорядоченное множество. Тогда элементы S можно пронумеровать таким образом:
S {x1 ,..., xn } , что из xi x j будет следовать i<j.
Доказательство.
Т.е. нужно расставить S1 ,...Sn так, чтобы они шли по возрастанию.
► Введѐм множество X m* {X1* ,..., X m* }
1)m=S x1 (S1 ) x1* (x1* )S1
2)m=r, берѐм S2 , сравниваем с X 1* если S2 X1* - ставим слева, если S2 X1* -
справа.
Пусть S |
2 |
S |
1 |
X * X |
2 |
(S |
, X * ), X * (X * , X * ) . Строим биекцию: |
|||||||
|
|
1 |
|
2 |
1 |
2 |
1 |
2 |
|
|
||||
2={1,2} X |
m |
{X * ,..., X * |
}. Берѐм S |
m 1 |
, рассмотрим S |
m 1 |
X * и снова |
|||||||
|
|
|
1 |
|
m |
|
|
|
|
|
k |
перенумеровываем.◄
Следствие. В любом конечном частично упорядоченном множестве P
есть минимальный элемент m: не существует x P, такого, что x < m.
Верхняя и нижняя грани. Пусть S некоторое подмножество частично упорядоченного множества P. Элемент a (a P) называется нижней границей, или минорантой, множества S, если a ≤ x для всех x S.
Назовем a верхней границей, или мажорантой, множества S, если a ≥ x для всех x S. Определим элемент b P нижней гранью S, если: он является
нижней границей для S; b b для любой другой нижней границы b
множества S. В этом случае пишут b = inf S.
Аналогично c P - верхняя грань множества S, если: c - верхняя граница для
S; c c . В этом случае вводят обозначение c = sup S.
Лемма о границах. Любое подмножество частично упорядоченного множества имеет не более одной верхней и не более одной нижней грани.
Доказательство. Пусть b1 ,b2 - нижние грани множества S. Тогда
, потому что b1 - нижняя граница, а b2 - наибольшая нижняя граница.
Аналогично, b2 b1 . Из свойства (если x y, y x, то x=y) следует, что b1 b2 . Двойственное рассуждение доказывает единственность верхней грани.