Дискретная математика

25 очевидно, имеем: 11 ^3(mod8) и 10 ^2(mod8), тогда 21 =S(mod%) и ПО = 6(mod 8). Только сокращать, вообще говоря, нельзя: имеем, что 10 =2(mod 8), но сравнение 5 = l(mod 8^, неверно, хотя 2 5^0. § 8. Отношения порядка Бинарное отношение R на множестве А называется отношением частичного порядка, если R рефлексивно, антисимметрично и транзитивно. Отношение частичного порядка обозначается через < , т.е. вместо JcRy пишется у и читается, что х предшествует7. Бинарное отношение Я на множестве Л называется отношением строгого порядка, если R антирефяексивно, антисимметрично и транзитивно. Отношение строгого порядка обозначается через < , т.е. вместо xRy пишется х ^ у к читается, чтох строго предшествует;'. Рассмотрим примеры. Отношение х<у на множестве действительных чисел есть отношение частичного порядка, но не является отношением строгого порядка. Отношение х<у на (-оо, со) является отношением строгого порядка, но не является отношением частичного порядка, так как это отношение не рефлексивно. На множестве подмножеств данного множества М отношение с: является отношением частичного порядка. Если для х,уеА имеем х=^ у или у^ х, то считаем элементы х и у сравпимьши, в противном случае несравнтьши. Множество А с заданным на нем отношением частичного порядка называется частично упорядоченным множеством. Частично упорядоченное множество, в котором любые два элемента сравнимы, называется линейно упорядоченным множеством. Элемент а частично упорядоченного множества А называется лшнымальным (наименьшим) элементом, если не существует элементов х, х а, предшествующих ему, т.е. не существуете, х-р^а, такого, чтох<а. Линейное упорядоченное множество А называется вполне упорядоченным, если всякое непустое подмножество В множества А имеет наименьший элемент. Множество М= {0,1, 2, ...} является вполне упорядоченным. Множество (-со,ой) не является вполне упорядоченным, ибо, например, каждое из подмножеств ('-со,07 и ('0,17 не имеют наименьшего элемента.