Главная Промышленная автоматика.

cRc„, т. е. aRb. Поскольку (а,-произвольный элемент из R + , мы показали, что каждый элемент из R принадлежит R. Таким образом, R+R\ что и требовалось доказать. □

0.1.5. Отношения порядка

Важный класс отношений образуют отношения порядка. Вообще говоря, порядок на множестве Л-это любое транзитивное отношение на Л. При изучении алгоритмов важную роль играет специальный тип порядка, называемый частичным. Множество, на котором задан какой-нибудь порядок, называется упорядоченным.

Определение. Частичным порядком на множестве Л называется отношение R, определенное на Л и такое, что

(1) R транзнтивгго,

(2) для всех а Л утверждение aRa ложно i), т. е. отношение R up рефлексивно.

Из свойств (1) и (2) следует, что если aRb истинно, то bRa ложно. Это свойство называется асимметричностью.

Пример 0.8. Примером частичного порядка служит собственное включение множеств. Например, пусть 5 {i, ..., е„}- множество, состоящее из п элементов, и пусть A - S{S). Положим aRb для любых а, 6 из Л тогда и только тогда, когда аЬ. Отношение R является частичным порядком.

{5 О


Рис. 0.4. Частичный порядок.

На рис. 0.4 графически изображен этот частичный порядок для случая S = \0, 1, 2}. Множество 5 собственно включает тогда и только тогда, когда существует направленный вниз путь, ведущий из Sj в Sg. □

) Под „aRb ложно" понимается, что (а, Ь) R.

В литературе частичным порядком иногда называют то, что мы называем рефлексивным частичным порядком.

Определение. Рефлексивным частичным порядком на Л называется отношение R, обладающее следующими свойствами:

(1) R транзитивно,

(2) R рефлексивно,

(3) если aRb и bRa, то а = Ь.

Последнее свойство называют антисимметричностью.

Примером рефлексивного частичного порядка служит (не обязательно собственное) включение множеств.

В разд. 0.5 мы покажем, что каждый частичный порядок можно представить графически в виде структуры, называемой ориентированным ациклическим графом.

Важный частный случай частичного порядка-Линейный порядок.

Определение. Линейный порядок R на множестве Л - это такой частичный порядок, что если а w b принадлежат Л, то либо aRb, либо bRa, либо а--Ь. Если Л - конечное множество, то линейный порядок R удобно представлять себе, считая все элементы множества Л расположенными в виде последовательности а, а, ...,а„, для которой aRaj тогда и только тогда, когда i < j.

Аналогично можно определить рефлексивный линейный порядок, а именно R - рефлексивный линейный порядок на Л, если R-такой рефлексивный частичный порядок, что aRb или bRa для всех а и & из Л.

Например, отношение < (меньше), определенное на множестве неотрицательных целых чисел, является линейным порядком. Примером рефлексивного линейного порядка может служить отношение

0.1.6. Отображения

Важный класс отношений, которым мы будем пользоваться, образуют отображения.

Определение. Отображением (а также функцией или преобразованием) М множества Л в множество В называется такое отношение из Л в В, что если {а, Ь) и (а, с) принадлежат М, то Ь=с.

Если (а,Ь)М, то обычно пишут М(а)Ь. Говорят, что М{а) определено, если существует такое ЬВ, что (а, Ь)М. Если М (а) определено для всех аА, то говорят, что Л1 всюду определено. Если хотят подчеркнуть, что М может быть опреде-



) Ранее мы употребляли эти термины, предполагая, разумеется, что их интуитивный смысл ясен. Однако целесообразно дать формальные определения.

(2) Множество четных чисел.

(3) {{а, Ь)\а и b целые}.

Примеры несчетных множеств:

(1) Множество вещественных чисел.

(2) Множество всех отображений целых чисел в целые.

(3) Множество всех подмножеств множества положительных целых чисел.

УПРАЖНЕНИЯ

0.1.1. Пусть Л-{О, 1, 2, 3, 4, 5, 6}. Запишите множества, определяемые следующими предикатами:

(а) \Х\Х принадлежит А и X четно},

(б) {Х\Х принадлежит Л и является квадратом},

(в) {1 принадлежит Л и Х>Х+1}.

0.1.2. Пусть Л = {О, 1,2} и В-{О, 3, 4}. Запишите множества

(а) A(jB,

(б) Af]B,

(в) Л-Л,

(г) .9 (Л), (Д) Ах В.

0.1.3. Покажите, что если Л -множество, состоящее из п элементов, то (А) состоит из 2 элементов.

0.1.4. Пусть Л и Б--множества, а t/ -некоторое универсальное множество, по отгюшению к которому берутся дополнения. Покажите, что

(а) АиВ = А0В,

(б) АпВ = А[]В.

Эти тождества называются законами де Моргана.

0.1.5. Покажите, что не существует такого множества t/, что АИ для всех множеств Л. Указание: Рассмотрите парадокс Рассела.

0.1.6. Дайте пример отношения, которое

(а) рефлексивно, но не симметрично и не транзитивно;

(б) симметрично, но не рефлексивно и не транзитивно; (з) транзитивно, но не рефлексивно и не симметрично.

В каждом случае укажите множество, на котором определено отношение.

0.1.7. Приведите пример отношения на множестве, которое

(а) рефлексивно и симметрично, но не транзитивно;

(б) рефлексивно и транзитивно, по не симметрично;

(в) симметрично и транзитивно, но не рефлексивно.

лено не для всех аА, то говорят, что М - частичное отображение (функция) множества А в множество В. В любом случае пишут Л1: А-Множества А и В называются соответственно областью определения и множеством значений М.

Если отображение М: АВ таково, что для каждого ЬВ существует не более одного такого аА, что Л1(а) -Ь, то М называется инъективным (взаимно однозначным). Если отображение М всюду определено на Л и для каждого ЬВ существует точно одно такое аА, что М(а) = Ь, то М называется биективным.

Если отображение М: А-В инъективное, то можно найти обратное отображение М~: В-А, для которого M~(b) = a тогда и только тогда, когда М{а) = Ь. Если существует ЬВ, для которого в Л не найдется такого а, что М(а) = Ь, то будет частичной функцией.

Понятие биективного отображения используется для определения моищости множества, которая, говоря неформально, означает число элементов этого множества.

Определение. Два множества А w В называются равномощ-ными, если существует биективное отображение т А в В.

Пример 0.9. Множества {О, 1, 2} и {а, Ь, с\ равномощны. Для доказательства этого утверждения можно взять, например, биективное отображение М ~ {(О, а), (1, Ь), (2, с)}. Множество целых чисел имеет ту же мощность, что и множество четных чисел, хотя последнее является собственным подмножеством первого. Это легко доказать с помощью биективного отображения {{i, 201 - целое число}. □

Теперь можно точно определить, что мы понимаем под конечным множеством и бесконечным множеством).

Определение. Множество S конечно, если оно равномощно множеству {I, 2, ...,п} для некоторого целого числа п. Множество бесконечно, если оно равномощно некоторому своему собственному подмножеству. Множество счетно, если оно равно-мощно множеству положительных целых чисел. (Из примера 0.9 следует, что каждое счетное множество бесконечно.) Бесконечное множество, которое не является счетным, называется несчетньш.

Примеры счетных множеств:

(1) Множество всех положительных и отрицательных целых чисел.



Предостережение: Вы заблуждаетесь, если считаете, что симметричное и транзитивное отношение обязано быть рефлексивным (так как aRb и bRa влечет aRa).

0.1.8. Покажите, что следуюш,ие отношения являются отношениями эквивалентности;

(а) {(G, с)абЛ},

(б) отношение конгруэнтности, заданное на множестве треугольников.

0.1.9. Пусть / - отношение эквивалентности на множестве Л. Пусть а и -элементы из А. Покажите, что

(а) [й:]=[Ь] тогда и только тогда, когда aRb,

(б) [с]Л[Ь] = 0 тогда и только тогда, когда aRb ложно.

0.1.10. Пусть Л -конечное множество. Какие отношения эквивалентности порождают наибольшее н наименьшее число классов эквивалентности?

O.i.U. Пусть Л-jO, 1, 2} и R = {(0, 1). (1, 2)}. Найдите R и R.

0.1.12. Докажите теорему 0.2(6).

0.1.13. Пусть /? -отношение на Л. Покажите, что существует такое единственное отношение R, что

(2) отношение эквивалентности на Л,

(3) если / - какое-то отношение эквивалентности на Л и RR\ то R,R.

R Назызается наижньшим отношением эквивалентности, содержащим R.

Определение. Полным порядком на Л называется аакой рефлексивный частичный порядок на А, что для каждого непустого подмножества А существует такое ЬВ, Что bRa для всех аВ (т. е. каждое непустое подмножество содержит наименьший элемент). Множество Л называется тогда вполне упорядоченным.

0.1.14. Покажите, что отношение < (меньше или равно) является - полным порядком на множестве положительных целых чисел.

Определение. Пусть Л-множество. Обозначим

(1) АА,

(2) Л-:Л-1Х Л для i > 1.

Пусть Л* обозначает множество U Л.

0.1.15. Пусть / - полный порядок на Л. Определим отношение R на Л + , положив (а„ ...,a,„)R (b, . .., тогда и только тогда, когда выполняется одно из двух условий i):

1) Строго говоря, (ai, . . ., а) означает ((.. .((Oi, а), ад), .. .), а) в соответствии с определением Л".

(1) aRbi для некоторого i-m и aj=bj для всех l/<t,

(2) тп и abi для всех lim.

Покажите, что R - полный порядок на Л"*". Он называется лексикографическим порядком на Л + . (Примером лексикографического порядка может служить упорядочение слов в словаре.)

0.1.16. Для каждого из следующих отношений установить, является ли оно частичным порядком, рефлексивным частичным порядком, линейным порядком или рефлексивным линейным порядком;

(а) на (А),

(б) на 5 (Л),

(в) отношение R на множестве людей Я, определенное так: aRb тогда и только тогда, когда д- -отец Ь,

(г) отношение R на Я, определенное так; aR тогда и только тогда, когда а-предок Ь,

(д) отношение R па Н, определенное так: aR.b тогда и только тогда, когда а старше Ь.

0.1.17. Пусть и R - отношения. К,омпозицией отношений /?1 и R, обозначаемой RoR,, называется отношение {{а, Ь)\ существует такое с, что aRc и cRb}. Покажите,; что если и /2 -отображения, то /j о/д-отображение. При каких уело-ВИЯХ R о R будет всюду определенным отображением? Инъек-тивным отображением? Биективным отображением?

0.1.18. Пусть Л -конечное множество и ВЛ. Покажите, что если М: ЛS -биективное отображение, то А = В.

0.1 J9. Пусть Л и состоят соответственно из m и /г элементов. Покажите, что существует п" всюду определенных из Л функций, отображающих А ъ В. Сколько существует всех не обязательно всюду определенных отображений из Л в 5?

*0.1.20. Пусть Л - произвольное не обязательно конечное множество. Покажите, что множества (Л) и \М\М~всюду определенная функция, отображающая Л в {О, 1}} равномощны.

0.1.21. Покажите, что множество всех целых чисел равно-мощно

(а) множеству простых чисел,

(б) множеству пар целых чисел.

Указание: Определите линейный порядок R на множестве пар целых чисел, положив (ч, /J(Ia, /J тогда и только тогда, когда < ( + / или + + b и ii<4.

0.1.22. Множество Л „больше" множества В, если А я В имеют разную мощность и В равномощно подмножеству множества Л. Покажите, что множество вещественных чисел, лежащих строго между





0 1 [2] 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.002