Дискретная математика. Множества. Отображения. Отношения

67 Упорядоченное множество ( , ) А p называется вполне упоря - доченным , если любое его непустое подмножество имеет наи - меньший элемент . Таковым является , например , множество нату - ральных чисел N с отношением неравенства чисел . Множество це - лых чисел с обычным неравенством чисел не является вполне упорядоченным , так как не имеет наименьшего элемента . Пусть , x y A ∈ – два элемента упорядоченного множества ( , ) A p . Тогда говорят , что элемент y доминирует над элементом x , если x y p и не существует другого элемента z A ∈ такого , что ( ) & ( ) x z z y p p , т . е . x z y p p . Отношение доминирования называют также отношением непосредственного предшествования ( x непосредственно предше - ствует y ) или отношением непосредственного следования ( y непо - средственно следует за элементом x ). Отношение доминирования обозначается символом . , ( x y A x ∀ ∈ ( ) & ( )) y x y z A x z y ↔ ¬∃ ∈ p p p . (5.27) Отношение доминирования антирефлексивно , антисим - метрично , но не транзитивно и , следовательно , не является отно - шением порядка . Рассмотрим множества действительных и рациональных чи - сел R и Q с обычными отношениями неравенства чисел ≤ . Извест - но , что эти множества всюду плотны , т . е . , ( ( ); x y x y z x z y ∀ ∈ ≠ → ∃ ∈ < < R R , ( ( ) x y x y z x z y ∀ ∈ ≠ → ∃ ∈ < < Q Q . Это значит , что отношение доминирования , ассоциирован - ное с неравенством чисел в этих множествах , пусто : = ∅ . На множестве натуральных чисел N {1, 2, ...} = с обычным неравенством чисел ≤ отношение доминирования непусто . В частности 1 2, 2 3 и т . д . Данное отношение доминирования изображено на рис . 5.3.