Книги и конспекты / Шпоры / 6
.pdfЧастичное упорядочение. Принцип двойственности. Лемма о наибольших и наименьших элементах. Доминирование. Теорема о доминировании.
Рассмотри бинарное отношение на S. - частичный порядок на S, если обладает тремя свойствами:
1)Рефлексивность (x≤x)
2)Антисимметричность (х≤у, у≤х => х=у)
3)Транзитивность (х≤у, y≤z => x≤z)
S с заданной ≤ ([S,≤]) называется частично упорядоченным множеством.
Принцип двойственности (≤ ≥): все теоремы верные для ≤ верны
и для ≥.
Лемма. В любом частично упорядоченном множестве [S,≤] может существовать не более одного наименьшего элемента и не более одного наимбольшего.
О (I) – наибольший (наименьший) элемент множества S, если x≤O и x≤I , для любого x S.
Доказательство: пусть О1 и О2 – два наименьших элемента, тогда О1≤О2 и О2≤О1 (солгасно антисимметричности) О1 = О2. Аналогично для I.
Если а и b – элементы частично упорядоченного множества, а<b и x : a<x<b, то говорят что b доминирует над а
Теорема. Пусть а<b на конечном множестве, тогда у этого множества можно найти хотя бы одну цепь:
x0 = a<x1<x2<…<xn=b, где xi-1 <xi
Доказательство. Т.к. а<b, то существует такой с1, что a<c1 и с1<b. Т.к. а<c1 то существует такой с2 что а<c2 и с2<c1 и т.д.