Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.12.2023

Просмотров: 423

Скачиваний: 2

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

б) отношение перпендикулярности двух прямых?28. Доказать, что отношение {((x1, y1), (x2, y2)) | x2 1+ y2 1= x2 2+ y2 2} являет- ся отношением эквивалентности на множестве R2. Определить классы этой эквивалентности.29. Доказать, что отношение {(a, b) | (a − b) — рациональное число} явля- ется отношением эквивалентности на множестве вещественных чисел.30. Пусть на множестве ω определено отношение 6, задаваемое следую- щим правилом:m 6 n ⇔ m делит n.Считая, что 0 делит 0, показать, что 6 — частичный порядок. Для произвольных натуральных чисел m и n найти inf{m, n} и sup{m, n}относительно указанного порядка.31. Для обычных отношений 6 и < на множестве ω показать, что< ◦ < 6= <, 6 ◦ < = < и 6 ◦ > = ω2 32. Построить пример ч.у.м. с единственным минимальным элементом, но без наименьшего.33. Рассмотрим на множестве R2отношение Парето Π:(x1, y1) Π (x2, y2) ⇔ x1 6 x2и y1 6 y2.Для точек A(a1, a2) и B(b1, b2) найти множество нижних и верхних гра- ней множества {A, B}. Чему равен inf{A, B} и sup{A, B}?34. Построить линейный порядок на множестве комплексных чисел.35. Составить матрицу отношения полного порядка, при котором нумера- ция элементов ведется: а) по возрастанию; б) по убыванию. 50Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ36. Проверить, являются ли частичными порядками бинарные отношения со следующими матрицами:а)1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1; б)1 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1; в)1 0 0 0 1 1 1 1 1 1 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1;г)1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 1; д)1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1; е)1 0 1 1 1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1;ж)1 0 1 0 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1; з)1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1; и)1 1 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 0 1 1;к)1 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1; л)1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1; м)1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 1Построить диаграммы Хассе для заданных порядков. Есть ли в со- ответствующих частично упорядоченных множествах наименьшие или наибольшие элементы? Какие из этих частичных порядков линейные?37. Построить всевозможные попарно неизоморфные четырехэлементые ч.у.м. hA; 6i. Какие из этих ч.у.м. самодвойственны, т. е. изоморфныhA; >i? Глава 2АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ§ 2.1.Определения и примерыЧасто объектом изучения в математике и ее приложениях служит мно- жество вместе с определенной на нем структурой. Читателю уже известны поля, формирующие основу обычной арифметики, линейные пространства,обеспечивающие связь геометрических объектов с операциями над числами,множества с введенными на них бинарными отношениями. Все эти струк- туры образуют алгебраические системы, представляющие собой некоторые миры с определенными в них законами. Перейдем к точному определению алгебраической системы.Рассмотрим непустое множество A. В § 1.2 было введено понятиеn-местной операции на множестве A (f : An→ A). Отметим, что, поскольку операция f является функцией, для любого набора (x1, . . . , xn) ∈ Anре- зультат применения операции f (x1, . . . , xn) однозначно определен. Так как область значений операции f лежит в множестве A, то будем говорить, что операция f замкнута на множестве A.Сигнатурой или языком Σ называется совокупность предикатных и функциональных символов с указанием их местности. При этом множе- ства предикатных и функциональных символов не пересекаются. 0-Местный функциональный символ называется константным символом или простоконстантой. Если α — функциональный или предикатный символ, то его местность обозначается через µ(α). n-Местные предикатные и функциональ- ные символы часто будем обозначать соответственно через P(n)и f(n). Если в рассматриваемой сигнатуре используются стандартные символы, такие,например, как + для операции сложения, 6 для отношения порядка, | для 52Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫотношения делимости, 0 для константного символа и другие, то мы просто пишем Σ = {6}, Σ = {6, +, ·, 0}, Σ = {+, −, |, 0, 1} и т. д.Алгебраической системой A = hA; Σi сигнатуры Σ называется непустое множество A, где каждому n-местному предикатному (функциональному)символу из Σ поставлен в соответствие n-местный предикат (соответственно операция), определенный на множестве A. Множество A называется носите-лем или универсумом алгебраической системы hA; Σi. Предикаты и функ- ции, соответствующие символам из Σ, называются их интерпретациями.Обозначать интерпретации будем теми же буквами, что и соответствую- щие символы сигнатуры. Заметим, что интерпретацией любого константного символа является некоторый элемент (константа) из A.Алгебраические системы в дальнейшем будут обозначаться готическими буквами A, B, . . . (возможно, с индексами), а их носители — соответствующи- ми латинскими буквами A, B, . . . (с соответствующими индексами). Иногда мы будем отождествлять носитель с алгебраической системой.Мощностью алгебраической системы A называется мощность ее носите- ля A. В дальнейшем будем часто опускать слово “алгебраическая” и назы- вать A системой или структурой.Непустая сигнатура Σ называется функциональной (предикатной), если она не содержит предикатных (функциональных) символов. Система A на- зывается алгеброй (моделью или реляционной системой), если ее сигнатура функциональна (предикатна).Пример 2.1.1. 1. Набор hω; +, ·i является алгеброй с двумя двухмест- ными операциями.2. Набор hω; 6, +, ·,0, 0, 1i является системой с бинарным отношением 6(µ(6) = 2), двухместными операциями +, · (µ(+) = µ(·) = 2), одноместной операцией0: n 7→ n + 1 (µ(0) = 1) и двумя нуль-местными операциями(константами) 0, 1 (µ(0) = µ(1) = 0).3. Набор hZ; +, :,√2i не образует алгебру, поскольку деление не является операцией на множестве Z (например, 2 : 3 /∈ Z), а элемент√2 не принадле- жит Z.4. Набор hP(U); ∩, ∪, , 0, 1i с двухместными операциями ∩, ∪, одномест- ной операцией : A 7→ A, константами 0 = ∅ и 1 = U является алгеброй,называемой алгеброй Кантора.5. Алгеброй является любое кольцо.6. Пара­{f (x) | f : R → R};ddx®(гдеddx— операция дифференцирова- ния) не является алгеброй, поскольку не всякая функция дифференцируема, 2.1. ОПРЕДЕЛЕНИЯ И ПРИМЕРЫ53но если рассмотреть множество A = {f (x) | f (x) дифференцируема беско- нечное число раз}, то отображение дифференцированияddx: f 7→dfdxявляется операцией на A и пара­A;ddx®образует алгебру. ¤Заметим, что частичную операцию f , отображающую Anв A, можно рассматривать как (n + 1)-местное отношениеRf­ {(x1, x2, . . . , xn, y) | (x1, . . . , xn) ∈ Anи y = f (x1, . . . , xn)}.Поэтому в последнем примере пару­{f (x) | f : R → R};ddx®можно считать алгебраической системой, если рассматриватьddxкак бинарное отношение©(f, g) | g =dfdxªАлгебра A сигнатуры Σ = {f }, где µ(f ) = 2, называется группоидом.Единственная здесь операция f обычно обозначается символом ·: A = hA; ·i.Если A — конечное множество, действия операции · можно задать квадрат- ной таблицей, в которой для каждой пары (ai, aj) ∈ A2записан результат действия ·(ai, aj). Такая таблица называется таблицей Кэли группоида A.Группоид A называется полугруппой, если · — ассоциативная операция, т. е.для всех элементов x, y, z ∈ A верно x · (y · z) = (x · y) · z. Полугруппа A на- зывается моноидом, если существует элемент e ∈ A, называемый единицей,такой, что e · x = x · e = x для всех x ∈ A. Полугруппы и моноиды имеют особое значение в теории языков при обработке слов.Пример 2.1.2. Пусть W (X) — множество слов алфавита X. Определим на W (X) операцию конкатенации ˆследующим образом: если α, β ∈ W (X),то αˆβ = αβ, т. е. результатом является слово, полученное соединением словα и β (например, xyzˆzx = xyzzx). Операция ˆ ассоциативна, т. е. для лю- бых слов α, β, γ верно (αˆβ)ˆγ = αˆ(βˆγ). Следовательно, система hW (X);ˆiявляется полугруппой. Так как для всех α ∈ W (X) верно Λˆα = αˆΛ = α,где Λ — пустое слово, то Λ удовлетворяет свойству единицы. Таким образом,система hW (X);ˆi является моноидом. ¤Моноид A = hA; ·i называется группой, если для любого элементаx ∈ A существует элемент x−1∈ A, называемый обратным к x, такой, чтоx · x−1= x−1· x = e. Группа A называется коммутативной или абелевой,если x · y = y · x для всех x, y ∈ A.Пример 2.1.3. 1. Если hK; +, ·i — кольцо, то hK; +i — абелева группа.2. Система hGLn(K); ·i, где GLn(K) ­ {A | A — матрица порядка nнад полем K, и det A 6= 0} является группой, которая некоммутативна приn > 2. ¤ 54Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ§ 2.2.МорфизмыПусть даны алгебраические системы A = hA; Σi и B = hB; Σi. Отобра- жение ϕ: A → B называется гомоморфизмом системы A в систему B, если выполняются следующие условия:1) для любого функционального символа f(n)∈ Σ, соответствующих функций fAи fBв системах A и B и любых a1, a2, . . . , an∈ A выполня- етсяϕ(fA(a1, a2, . . . , an)) = fB(ϕ(a1), ϕ(a2), . . . , ϕ(an));2) для любого предикатного символа P(n)∈ Σ, соответствующих преди- катов PAи PBв системах A и B и любых a1, a2, . . . , an∈ A выполняется(a1, a2, . . . , an) ∈ PA⇒ (ϕ(a1), ϕ(a2), . . . , ϕ(an)) ∈ PB.Если ϕ: A → B — гомоморфизм, то будем его обозначать черезϕ: A → B.При гомоморфизме сохраняются действия операций и отношения. Это позволяет переносить изучение свойств с одной системы на другую.Пример 2.2.1. Рассмотрим системы A = hZ; +, 6i и B = hZ2; +, 6i, где в системе B сложение задается по правилу(a1, b1) + (a2, b2) = (a1+ a2, b1+ b2),а отношение порядка —(a1, b1) 6 (a2, b2) ⇔ a1 6 a2и b1 6 b2.Отображение ϕ: Z → Z2, при котором ϕ(a) = (a, 0), является гомоморфиз- мом. Действительно, для любых a, b ∈ Z имеемϕ(a + b) = (a + b, 0) = (a, 0) + (b, 0) = ϕ(a) + ϕ(b),и если a 6 b, то (a, 0) 6 (b, 0), т. е. ϕ(a) 6 ϕ(b). ¤Гомоморфизм ϕ: A → B, являющийся инъекцией, называется мономор-физмом. Гомоморфизм ϕ: A → B, являющийся сюръекцией, называетсяэпиморфизмом, и при этом система B называется гомоморфным образом 2.2. МОРФИЗМЫ55системы A. Гомоморфизм ϕ: A → A называется эндоморфизмом. Сюръек- тивный мономорфизм ϕ: A → B, для которого ϕ−1— гомоморфизм, называ- ется изоморфизмом A на B и обозначается через ϕ: A ∼→ B. Если существует изоморфизм ϕ: A ∼→ B, то системы A и B называются изоморфными и обо- значается это так: A ' B.Таким образом, условие A ' B означает, что существует биекцияϕ: A ↔ B, удовлетворяющая следующим условиям:1) для любого функционального символа f(n)∈ Σ, соответствующих функций fAи fBв системах A и B и любых a1, a2, . . . , an∈ A выполня- етсяϕ(fA(a1, a2, . . . , an)) = fB(ϕ(a1), ϕ(a2), . . . , ϕ(an));2) для любого предикатного символа P(n)∈ Σ, соответствующих преди- катов PAи PBв системах A и B и любых a1, a2, . . . , an∈ A выполняется(a1, a2, . . . , an) ∈ PA⇔ (ϕ(a1), ϕ(a2), . . . , ϕ(an)) ∈ PB.Изоморфизм ϕ: A ∼→ A называется автоморфизмом системы A. Заметим,что, поскольку изоморфизм ϕ: A ∼→ B является биекцией A ↔ B, изоморф- ные системы равномощны.Утверждение 2.2.1. 1. idA: A ∼→ A.2. Если ϕ: A ∼→ B, то ϕ−1: B ∼→ A.3. Если ϕ: A1∼→ A2и ψ: A2∼→ A3, то ϕ ◦ ψ: A1∼→ A3. ¤Таким образом, отношение изоморфизма ' является эквивалентностью на любом множестве алгебраических систем (отметим, что класс всех алгеб- раических систем не является множеством, поскольку не существует множе- ства всех множеств). Это означает, что отношение изоморфизма разбивает множества алгебраических систем на классы эквивалентности, в каждом из которых содержатся системы, имеющие “одинаковое устройство”. Это да- ет возможность переносить изучение свойств с одной системы на другую,изоморфную ей. Так, используя факт изоморфизма геометрического вектор- ного пространства пространству строк, работу с геометрическими объекта- ми можно свести к действиям с наборами чисел, что позволяет применять компьютеры.Пример 2.2.2. 1. Рассмотрим множество векторов E3геометрическо- го векторного пространства с операциями сложения векторов и умножения 56Глава 2. АЛГЕБРАИЧЕСКИЕ СИСТЕМЫвекторов на вещественные числа. Получим систему A = hE3; +, {λ·}λ∈Ri бес- конечной сигнатуры, где одноместные функции λ· ставят в соответствие век- тору a вектор 1   2   3   4   5   6   7   8   9   ...   29

λa. Рассмотрим также систему B = hR3; +, {λ·}λ∈Ri, носитель которой состоит из троек вещественных чисел (x, y, z), + — двухместная операция покоординатного сложения троек, а функция λ· — операция умно- жения троек на число λ для всех вещественных чисел λ. Системы A и B яв- ляются линейными пространствами над полем R. Отображение ϕ, ставящее в соответствие вектору a ∈ E3его координатную строку (x, y, z) в некотором фиксированном базисе e1, e2, e3, является биекцией (ϕ: E3↔ R3), при кото- рой сохраняются действия операций: ϕ(a+b) = ϕ(a)+ϕ(b) и ϕ(λ·a) = λ·ϕ(

1) является ли граф, соответствующий рассматриваемой принципиаль- ной схеме, планарным?2) если граф планарен, то как получить его изображение без пересечения ребер?На первый вопрос принципиальный ответ дает теорема Понтрягина—Куратовского, а методы получения плоских изображений планарных графов можно найти в книге Б. Н. Деньдобренько, А. С. Малика [7].Если граф G непланарен, то для его геометрической реализации удаля- ют отдельные ребра (переносят на другую плоскость). Минимальное число ребер, которое необходимо удалить из графа для получения его плоского изображения, называется числом планарности графа G. При вынесении этих ребер на вторую плоскость получают часть графа, которая также может оказаться неплоской. Тогда вновь решают задачу вынесения отдельных ре- бер на следующую плоскость и т. д. Минимальное число плоскостей m, при котором граф G разбивается на плоские части G1, G2, . . ., Gm(разбиение ведется по множеству ребер), называется толщиной графа G.Таким образом, толщина планарного графа равна 1.Пример 4.15.2. Каждый из графов K5и K3,3имеет толщину 2. ¤Задачи и упражнения1. Представить граф (рис. 4.50) в аналитической и матричной формах, списком дуг и структурой смежности.2. Составить матрицу инцидентности для мультиграфа, изображенного на рис. 4.51.3. Найти все неизоморфные подграфы и части графа K3 4. Представить в геометрической и матричной формах графы G1∪ G2,G1∩ G2, G1⊕ G2(рис. 4.52).5. Для графов G1и G2из предыдущей задачи найти G1× G2, G1[G2] и G2[G1]. ЗАДАЧИ И УПРАЖНЕНИЯ163•••••¡¡¡¡¡¡@@@@@@R ?¾-±°²¯••••¡¡¡¡¡¡µ¸?YK*¼g±°²¯Рис. 4.50Рис. 4.516. С помощью матрицы смежности графа (рис. 4.53) найти его матрицы дости- жимости, контрдостижимости и сильных компонент.7. Найти матрицу расстояний, диаметр, радиус, центральные и периферийные вершины графа, изображенного на рис. 4.54.8. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа(рис. 4.55).9. Доказать, что в любом конечном бесконтурном графе существуют вершины с нулевой полустепенью исхода и с нулевой полустепенью захода.10. Проверить на эйлеровость и найти минимальное множество покрывающих цепей:а) графа K5; б) графа K3,3; в) графа, изображенного на рис. 4.56.•••¢¢¢¢¢¸AAAAAU1 23G1••••¾AAAAAU¢¢¢¢¢®1 23 4G2••••@@@I¡¡¡µ?@@@Rh1 23 4Рис. 4.52Рис. 4.53•••••••¡¡¡¡@@@@@@•••••½½½½>ZZZZ?-@@@@@@R¡¡¡¡¡¡µ¾6K®1 23 54(3)(4)(6)(2)(1)(2)(2)(3)(−2)(−5)Рис. 4.54Рис. 4.55 164Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ•••••••¶¶¶¶¶¶³³³³³³³³´´´´PPPPPPPPQQQQEEEEEEEE¢¢¢¢¢¢¡¡¡•••••••¶¶¶¶¶¶@@@´´´´@@@@@@EEEEEEEESSSSSS¡¡¡¡¡¡¢¢¢¢¢¢(2)(2)(3)(3)(1)(2)(2)(4)(3)(1)Рис. 4.56Рис. 4.57••••••••••••••••@@R¡¡ª¡¡ª ??¡¡ª@@R@@R@@R@@R¡¡ª¡¡ª¡¡ª¡¡ª@@R¡¡ª1 23 45 67 89 10 11 12 13 14 15 16•••••••JJJJ1 23 45 97 86 10Рис. 4.58Рис. 4.5911. Построить все неизоморфные трех-, четырех- и пятивершинные деревья.12. Найти остов минимального веса взвешенного графа (рис. 4.57).13. Найти упорядоченный лес, соответствующий бинарному дереву, изображен- ному на рис. 4.58.14. Найти матрицы фундаментальных циклов и фундаментальных разрезов гра- фа (рис. 4.59).15. Найти хроматическое число графа (рис. 4.60).16. Найти толщину графа (рис. 4.61).•••••••¡¡¡@@@@@@@@@SSSSSS¦¦¦¦¦¦¦¦••••••¡¡¡¡@@@@HHHHHHHHHHHHHH©©©©©©©©©©©©©©Рис. 4.60Рис. 4.61 Глава 5КОМБИНАТОРИКАКомбинаторика — раздел математики, посвященный решению задач вы- бора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множе- ства, называемой комбинаторной конфигурацией. Поэтому целями комби- наторного анализа являются изучение комбинаторных конфигураций, алго- ритмов их построения, оптимизация таких алгоритмов, а также решение за- дач перечисления. Простейшими примерами комбинаторных конфигураций являются перестановки, размещения, сочетания и разбиения. При подсчете комбинаторных конфигураций используются правила суммы, произведения и степени, сформулированные в § 1.4.§ 5.1.Перестановки и подстановкиПусть дано множество M = {a1, a2, . . . , an}. Перестановкой элементов множества M называется любой кортеж (ai1, ai2, . . . , ain), состоящий из nразличных элементов множества M.Перестановки отличаются друг от друга только порядком входящих в них элементов. Покажем, что число Pnвсех перестановок множества Mравно n!. Действительно, на первое место в кортеже можно подставить лю- бой из n элементов, на второе место — любой из n − 1 оставшихся и т. д. Для последнего места остается единственный элемент. Поэтому получаем всегоn(n − 1)(n − 2) . . . 2 · 1 = n! перестановок. 166Глава 5. КОМБИНАТОРИКАПример 5.1.1. 1. Расставить на полке 10 книг можно P10= 10! == 3 628 800 различными способами.2. Список студентов группы, состоящей из 25 человек, можно составитьP25= 25! способами. ¤Напомним, что биекция σ: M ↔ M называется подстановкой множе- ства M. Пусть σ — подстановка множества M = {1, 2, . . . , n}. Тогдаσ(k) = sk, где 1 6 sk6 n, k = 1, 2, . . . , n, {s1, s2, . . . , sn} = {1, 2, . . . , n},и поэтому подстановку σ можно представить в виде матрицы, состоящей из двух строк:[σ] ­µ1 2 . . . ns1s2. . . sn¶.Ясно, что если в матрице [σ] переставить столбцы, то полученная матрица будет также определять подстановку σ. Множество всех подстановок мно- жества {1, 2, . . . , n} обозначается через Sn. Для подстановок σ, τ ∈ Snможно определить произведение σ · τ как произведение двух функций. Зная матри- цы подстановок[σ] =µ1 2 . . . ns1s2. . . sn¶и [τ ], переставив столбцы матрицы [τ ] так, чтобы ее первая строка совпала со второй строкой матрицы [σ]:µs1s2. . . snt1t2. . . tn¶,получаем[στ ] =µ1 2 . . . ns1s2. . . sn¶ µs1s2. . . snt1t2. . . tn¶=µ1 2 . . . nt1t2. . . tn¶.Пример 5.1.2. Если [σ] =µ1 2 3 4 2 1 4 3¶, [τ ] =µ1 2 3 4 3 1 4 2¶, то[στ ] =µ1 2 3 4 2 1 4 3¶ µ2 1 4 3 1 3 2 4¶=µ1 2 3 4 1 3 2 4¶. ¤Теорема 5.1.1. Алгебра hSn; ·i является группой. При n > 3 она неком-мутативна. 5.1. ПЕРЕСТАНОВКИ И ПОДСТАНОВКИ167Доказательство. Операция · ассоциативна как операция произведе- ния функций. Легко проверяется, что существует единичная подстановка εс матрицей [ε] =µ1 2 . . . n1 2 . . . n¶и для любой подстановки σ с матрицей[σ] =µ1 2 . . . ns1s2. . . sn¶существует обратная подстановка σ−1, соответству- ющая матрицеµs1s2. . . sn1 2 . . . n¶Если n > 3, то рассмотрим подстановки σ и τс матрицами[σ] =µ1 2 3 4 . . . n2 1 3 4 . . . n¶и [τ ] =µ1 2 3 4 . . . n3 2 1 4 . . . n¶Имеем [στ ] =µ1 2 3 4 . . . n2 3 1 4 . . . n¶, [τ σ] =µ1 2 3 4 . . . n3 1 2 4 . . . n¶, т. е.στ 6= τ σ. Таким образом, группа hSn; ·i некоммутативна. ¤Группа hSn; ·i называется симметрической группой степени n. Число элементов этой группы |Sn| равно Pn­ n!.Подстановка σ называется циклом длины r, если матрицу [σ] переста- новкой столбцов можно привести к видуµs1s2s3. . . sr−1srsr+1. . . sns2s3s4. . .srs1sr+1. . . sn¶.Очевидно, что в этом случае σ задает биекцию, в которой s17→ s2,s27→ s3, . . ., sr7→ s1, а остальные элементы неподвижны. Описанный цикл σобозначается через (s1s2. . . sr).Пример 5.1.3. Подстановка с матрицейµ1 2 3 4 5 6 1 5 6 4 3 2¶является циклом (2 5 3 6), а подстановка с матрицейµ1 2 3 4 5 6 4 5 2 1 6 3¶циклом не яв- ляется, так как из нее можно выделить два цикла (1 4) и (2 5 6 3). ¤Циклы (s1s2. . . sr) и (t1t2. . . tp) называются независимыми, если{s1, s2, . . . , sr} ∩ {t1, t2, . . . , tp} = ∅.Теорема 5.1.2. Каждую подстановку можно однозначно, с точностьюдо порядка сомножителей, представить в виде произведения независимыхциклов. ¤ 168Глава 5. КОМБИНАТОРИКАВ примере 5.1.3 имеемµ1 2 3 4 5 6 1 5 6 4 3 2¶= (2 5 3 6) иµ1 2 3 4 5 6 4 5 2 1 6 3¶= (1 4)(2 5 6 3).Двухэлементный цикл (i j) называется транспозицией. При транспози- ции i-й и j-й элементы меняются местами, а остальные сохраняют свое по- ложение.Теорема 5.1.3. Каждая подстановка есть произведение транспозиций.Доказательство. По теореме 5.1.2 достаточно установить, что любой цикл (s1s2. . . sr) можно представить в виде произведения транспозиций,но легко проверяется, что (s1s2. . . sr) = (s1s2)(s1s3) . . . (s1sr). ¤Пример 5.1.4. (1 2 3 4) = (1 2)(1 3)(1 4). ¤§ 5.2.Размещения и сочетанияПусть M — множество, состоящее из n элементов, m 6 n. Размещениемиз n элементов по m или упорядоченной (n, m)-выборкой, называется любой кортеж (ai1, ai2, . . . , aim), состоящий из m попарно различных элементов мно- жества M. Размещение можно рассматривать как разнозначную функциюf : {1, 2, . . . , m} → M, для которой f (j) = aijПример 5.2.1. Для множества M = {a, b, c} пары (a, b) и (b, a) являются размещениями из 3 по 2, тройка (a, c, b) — размещением из 3 по 3, а тройка(b, a, b) размещения не образует. ¤Число размещений из n по m обозначается через Amnили P (n, m). Пока- жем, чтоAmn=n!(n − m)!= n(n − 1) . . . (n − m + 1)(5.1)(напомним, что 0! = 1). Действительно, размещение m элементов мож- но представить как заполнение некоторых m позиций элементами множе- ства M. При этом первую позицию можно заполнить n различными спосо- бами. После того как 1-я позиция заполнена, элемент для заполнения 2-й позиции можно выбрать (n − 1) способами. Если продолжить этот процесс, 5.2. РАЗМЕЩЕНИЯ И СОЧЕТАНИЯ169то после заполнения позиций с 1-й по (m − 1)-ю будем иметь (n − m + 1) спо- собов заполнения последней, m-й позиции. Перемножая эти числа, получаем формулу (5.1).Пример 5.2.2. Из десяти различных книг произвольным образом бе- рутся и ставятся на полку одна за другой 3 книги. Имеется A3 10вариантов расстановок, где A3 10=10!7!= 10 · 9 · 8 = 720. ¤Cочетанием из n элементов по m или неупорядоченной (n, m)-выборкойназывается любое подмножество множества M, состоящее из m элементов.Пример 5.2.3. Если M = {a, b, c}, то {a, b}, {a, c}, {b, c} — все сочетания из 3 по 2. ¤Число сочетаний из n по m обозначается через Cmn,¡nm¢или C(n, m).Если объединить размещения из n элементов по m, состоящие из од- них и тех же элементов (не учитывая порядка их расположения), в клас- сы эквивалентности, то можно установить биекцию ϕ между сочетаниями и полученными классами по следующему правилу: ϕ({ai1, ai2, . . . , aim}) ­­ {(b1, b2, . . . , bm) | {b1, b2, . . . , bm} = {ai1, ai2, . . . , aim}}. Так как из каждого сочетания C можно получить m! размещений (упорядочивая m! способами элементы из множества C по числу перестановок этого множества), то каж- дый класс эквивалентности содержит m! размещений и, значит, Amn= m!·Cmn,т. е. Cmn=Amnm!. Таким образом,Cmn=n!(n − m)! m!.Пример 5.2.4. Из десяти чисел четыре можно выбрать C4 10=10!6!4!==7·8·9·10 4!=7·8·9·10 1·2·3·4= 210 способами. ¤Число Cmnобладает следующими свойствами:1) Cmn= Cn−mn;2) Cmn+ Cm+1n= Cm+1n+1(правило Паскаля);3) (a + b)n=nPm=0Cmnambn−mдля любых a, b ∈ R, n ∈ ω (бином Ньютона).В силу последнего свойства числа Cmnназываются биномиальными коэф-фициентами.Пример 5.2.5. Из свойства 3 следует, что 2n=nPm=0Cmn. Действительно,2n= (1 + 1)n=nPm=0Cmn1m1n−m=nPm=0Cmn. ¤ 170Глава 5. КОМБИНАТОРИКА§ 5.3.Размещения и сочетания с повторениемРазмещением с повторением из n элементов по m или упорядоченной(n, m)-выборкой с возвращениями называется любой кортеж (a1, a2, . . . , am)элементов множества M, для которого |M| = n.Поскольку в кортеж (a1, a2, . . . , am) на каждое место может претендовать любой из n элементов множества M, число размещений с повторениямиˆP (n, m) равно n · n · . . . · n|{z}m раз= nm:ˆP (n, m) = nm.Пример 5.3.1. Из цифр 1, 2, 3, 4 можно составить ˆP (4, 3) = 4 3= 64трехзначных числа. ¤Определим отношение эквивалентности на множестве размещений с по- вторениями из n по m:(a1, a2, . . . , am) ∼ (b1, b2, . . . , bm) ⇔ для любого c ∈ M число элементов ai,равных c, совпадает с числом элементов bi, равных c.Сочетанием с повторением из n элементов по m или неупорядоченной(n, m)-выборкой с возвращениями называется любой класс эквивалентности по отношению ∼ множества размещений с повторениями из n элементов поm. Другими словами, сочетания с повторениями суть множества, которые состоят из элементов, выбранных m раз из множества M, причем один и тот же элемент допускается выбирать повторно.Число сочетаний с повторениями из n элементов по m обозначается через ˆC(n, m) и вычисляется по формулеˆC(n, m) = Cmn+m−1=(n + m − 1)!m!(n − 1)!.Пример 5.3.2. Число различных бросаний двух одинаковых кубиков равно ˆC(6, 2) = C2 7= 21. ¤§ 5.4.РазбиенияПусть M — множество мощности n, {M1, M2, . . . , Mk} — разбиение мно- жества M на k подмножеств, |Mi| = mi, m1+ m2+ . . . + mk= n. Кортеж(M1, . . . , Mk) называется упорядоченным разбиением множества M. 5.4. РАЗБИЕНИЯ171Если k = 2, то упорядоченное разбиение множества M на два подмноже- ства, имеющие соответственно m1и m2элементов, определяется сочетанием(без повторений) из n элементов по m1или из n по m2(m2= n − m1). Следо- вательно, число разбиений R(m1, m2) равно биномиальному коэффициентуCm1n= Cm2n. Таким образом,R(m1, m2) =n!m1!(n − m1)!=n!m1! m2!.В общем случае число R(m1, m2, . . . , mk) упорядоченных разбиений(M1, M2, . . . , Mk), для которых |Mi| = mi, равноn!m1! m2! . . . mk!, а числоR0(n, k) упорядоченных разбиений на k подмножеств вычисляется по фор- мулеR0(n, k) =Xm1+ ... +mk=n,mi>0R(m1, m2, . . . , mk).Числа R(m1, m2, . . . , mk) называются полиномиальными коэффициентами,поскольку для всех a1, a2, . . . , ak∈ R справедливо соотношение(a1+ a2+ . . . + ak)n=Xm1+ ... +mk=n,mi>0n!m1! . . . mk!· am1 1am2 2. . . amkk.Пример 5.4.1. В студенческой группе, состоящей из 25 человек, при вы- боре старосты за выдвинутую кандидатуру проголосовали 12 человек, про- тив — 10, воздержались — 3. Сколькими способами могло быть проведено такое голосование?Пусть M — множество студентов в группе, M1— множество студентов,проголосовавших за выдвинутую кандидатуру, M2— множество студентов,проголосовавших против, M3— множество студентов, воздержавшихся от голосования. Тогда |M| = 25, |M1| = 12, |M2| = 10, |M3| = 3, (M1, M2, M3) —упорядоченное разбиение множества M. Искомое число R(12, 10, 3) равно25!12!10!3!= 1487285800. ¤Число ˆR(l1, l2, . . . , lr; m1, m2, . . . , mr) разбиений исходного множества Mна k подмножеств, неупорядоченных между собой, среди которых liмножеств 172Глава 5. КОМБИНАТОРИКАимеет мощность mi, i = 1, . . . , r, l1+ . . . + lr= k, m1l1+ . . . + mrlr= n,вычисляется по формулеˆR(l1, . . . , lr; m1, . . . , mr) =n!l1! . . . lr!(m1!)l1. . . (mr!)lr,а число всех возможных разбиений множества M на k подмножеств, неупо- рядоченных между собой, равноXl1+...+lr=k,m1l1+ ... +mrlr=n,mi>0приli>0ˆR(l1, . . . , lr; m1, . . . , mr).1   ...   14   15   16   17   18   19   20   21   ...   29


34
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Отметим, что антисимметричность не совпадает с несимметрично- стью. Действительно, отношение P = {(1, 2), (2, 3), (3, 2)} на множестве
A = {1, 2, 3} не симметрично (так как (1, 2) ∈ P , а (2, 1) /
∈ P ) и не анти- симметрично (поскольку 2 6= 3, но (2, 3) ∈ P и (3, 2) ∈ P ). Тождественное отношение id
A
является одновременно симметричным и антисимметричным.
Пример 1.5.4. Проверим, какими свойствами обла-



6
¡
¡
¡
¡
¡
¡
µ
-
±°
²¯
j
2 3
1
Рис. 1.10
дает отношение P ⊆ A
2
, A = {1, 2, 3}, изображенное на рис. 1.10. Составим матрицу отношения P :
[P ] =


0 1 1 0 1 1 0 0 0

.
Так как в матрице [P ] на главной диагонали имеются ну- левые элементы, отношение P не рефлексивно. Несиммет- ричность матрицы [P ] означает, что отношение P не симметрично. Для проверки антисимметричности вычислим матрицу [P ∩ P
1
] = [P ] [P ]
T
Имеем
[P ] [P ]
T
=


0 1 1 0 1 1 0 0 0




0 0 0 1 1 0 1 1 0

 =


0 0 0 0 1 0 0 0 0

.
Поскольку в полученной матрице все элементы, стоящие вне главной диа- гонали, нулевые, отношение P антисимметрично. Так как [P ◦ P ] = [P ]
(проверьте!), то P ◦ P ⊆ P , т. е. P является транзитивным отношением. ¤
Пример 1.5.5. Отношение < ­ {(x, y) | x, y ∈ Q и x < y} на множестве рациональных чисел Q не рефлексивно, не симметрично, антисимметрично и транзитивно. ¤
Пример 1.5.6. Рассмотрим отношение P = {(x, y) | x, y ∈ Z и x − y < 1}
на множестве целых чисел Z.
Так как x − x = 0 < 1 для любого x ∈ Z, отношение P рефлексивно.
Поскольку (2, 4) ∈ P , а (4, 2) /
∈ P , отношение P не симметрично. Заметим,
что если x − y < 1 и y − x < 1, то x = y, так как из x 6= y следует |x − y| > 1.
Таким образом, отношение P антисимметрично. Предположим теперь, что
(x, y), (y, z) ∈ P , т. е. x − y < 1 и y − z < 1. Имеем x 6 y и y 6 z, тогда
x 6 z, значит, x − z < 1, т. е. (x, z) ∈ P . Следовательно, отношение P
транзитивно. ¤

1.6. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ И РАЗБИЕНИЯ
35
§ 1.6.
Отношения эквивалентности и разбиения.
Фактор-множества
Отношение P называется отношением эквивалентности (эквивалентно-
стью), если P рефлексивно, симметрично и транзитивно. Эквивалентности часто обозначают символами E и (тильда): x E y, x ∼ y.
Пример 1.6.1. 1. Отношение равенства x = y является эквивалентно- стью на любом множестве A, так как оно рефлексивно (x = x), симметрично
(x = y ⇒ y = x) и транзитивно (x = y, y = z ⇒ x = z).
2. Отношение подобия на множестве треугольников есть отношение эк- вивалентности.
3. На любом множестве P(U) отношение равномощности |A| = |B|
является отношением эквивалентности (см. § 1.4).
4. Отношение принадлежности к одной студенческой группе на множе- стве студентов НГТУ — отношение эквивалентности.
5. Рассмотрим множество M программ, вычисляющих некоторые функ- ции. Отношение E = {(x, y) | программы x и y вычисляют одну и ту же функцию} является эквивалентностью. ¤
Пусть E — эквивалентность на множестве A. Классом эквивалентно-
сти элемента x ∈ A называется множество E(x) ­ {y | x E y}. Клас- сы эквивалентности E будут также называться E-классами. Множество
A/E ­ {E(x) | x ∈ A} называется фактор-множеством множества A по от- ношению E.
Пример 1.6.2. 1. Для отношения равенства = на множестве A каждый
=-класс состоит только из одного элемента: =(x) = {x} для любого x ∈ A.
Таким образом, фактор-множество A/= имеет вид {{x} | x ∈ A} и, следова- тельно, биективно множеству A.
2. Для отношения принадлежности к одной студенческой груп- пе классом эквивалентности является множество студентов одной группы.
Фактор-множество множества студентов НГТУ по этому отношению экви- валентности представляет собой множество студенческих групп НГТУ. ¤
Предложение 1.6.1. Множество A/E является разбиением множе-
ства A. Обратно, если R = {A
i
} — некоторое разбиение множества A,
то можно задать соответствующее ему отношение эквивалентности E
по следующему правилу:
x E y ⇔ x, y ∈ A
i
для некоторого i.


36
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Доказательство. Пусть E — отношение эквивалентности на множе- стве A; A/E — фактор-множество множества A по E. Так как в силу ре- флексивности отношения E выполнимо x ∈ E(x) для любого x ∈ A, то каждое множество из A/E непусто и
x∈A
E(x) = A. Чтобы установить, что
A/E — разбиение множества A, осталось показать, что если E(x)∩E(y) 6= ∅,
то E(x) = E(y).
Пусть z ∈ E(x) ∩ E(y) и u ∈ E(x), т. е. (x, z), (y, z), (x, u) ∈ E. Так как отношение E симметрично, (z, x) ∈ E. Тогда из транзитивности отношения
E следует (y, u) ∈ E, т. е. u ∈ E(y). Таким образом, E(x) ⊆ E(y). Включение
E(y) ⊆ E(x) доказывается аналогично.
Предположим, что E — отношение на множестве A, соответствующее разбиению R = {A
i
}. Рефлексивность и симметричность E очевидны. Пусть теперь x E y и y E z. Тогда x, y ∈ A
i
, y, z ∈ A
j
, где A
i
, A
j
∈ R. Поскольку
y ∈ A
i
и y ∈ A
j
, то A
i
= A
j
. Следовательно, x, z ∈ A
i
и x E z. ¤
Таким образом, существует биекция между множеством всех отноше- ний эквивалентности на множестве A и множеством всех разбиений мно- жества A.
В любом классе E(x) эквивалентности E каждый элемент y ∈ E(x) свя- зан отношением E с любым элементом z ∈ E(x). Поэтому если E — эк- вивалентность на конечном множестве A, A/E = {E(x
1
), . . . , E(x
n
)},
E(x
i
) = {b
i
1
, . . . , b
i
m
i
}, i = 1, . . . , n, и множество A перенумеровано в следу- ющем порядке: b
1 1
, . . . , b
1
m
1
, b
2 1
, . . . , b
2
m
2
, . . . , b
n
1
, . . . , b
n
m
n
, то матрица [E] имеет блочно-диагональный вид:
[E] =
m
1
m
2
m
n
z}|{ z}|{
z}|{
m
1
n
m
2
n
m
n
n






1 0
1 0
1






,
где блоки 1 состоят из единиц, а остальные элементы равны 0.
Если же множество A перенумеровано произвольным образом:
A = {a
1
, . . . , a
n
}, E — отношение эквивалентности на A, то матрица
[E] = (e
ij
) приводится к блочно-диагональному виду некоторыми одновре-


1.7. ОТНОШЕНИЯ ПОРЯДКА
37
менными перестановками строк и столбцов. Элементы a
i
и a
j
эквивалентны по отношению E тогда и только тогда, когда i-я и j-я строки (а также столб- цы) матрицы [E] совпадают. Класс эквивалентности E(a
i
) состоит из элемен- тов a
j
, для которых e
ij
= 1.
Пример 1.6.3. Рассмотрим множество A = {1, 2, 3, 4, 5} с разбиением
R = {{1, 3, 5}, {2, 4}}, задающим отношение эквивалентности E с двумя E- классами {1, 3, 5} и {2, 4}. Матрица [E] имеет вид







1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1







.
По этой матрице легко определить, что класс E(3) равен {1, 3, 5}, так как в 3-й строке только e
31
, e
33
и e
35
равны 1. ¤
Пример 1.6.4. Рассмотрим геометрическое векторное пространство E
3
и множество направленных отрезков в нем. Направленные отрезки
−−−→
A
1
B
1
и
−−−→
A
2
B
2
называются эквивалентными:
−−−→
A
1
B
1

−−−→
A
2
B
2
, если они имеют одина- ковые длину и направление. Отношение — это отношение эквивалентно- сти. Вектором (геометрическим вектором)

a в E
3
называется класс экви- валентности направленных отрезков (
−→
AB) для некоторого
−→
AB. Фактор- множество множества направленных отрезков по отношению образует множество векторов пространства E
3
. ¤
§ 1.7.
Отношения порядка
Отношение эквивалентности является обобщением отношения равенства:
эквивалентные элементы считаются “равными”. Обобщением обычного отно- шения 6 служат отношения порядка.
Отношение P ⊆ A
2
называется предпорядком или квазипорядком, если
P рефлексивно и транзитивно.
Пример 1.7.1. Отношение P = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3),
(1, 3)} на множестве {1, 2, 3} является предпорядком (рис. 1.11). ¤

38
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Отметим, что симметричный предпорядок является отношением эквива- лентности.
Отношение P ⊆ A
2
называется частичным по-



@
@
@
@
R
-
*
¼
m
¼
m
¸
m
K
2 1
3
Рис. 1.11
рядком, если P рефлексивно, транзитивно и анти- симметрично. Таким образом, частичный порядок —
это антисимметричный предпорядок. Частичный по- рядок обычно обозначается символом 6, а обратное ему отношение 6
1
— символом >. Отношение > так- же является частичным порядком и называется двой-
ственным порядку 6. Используя отношение 6, определим отношение <,
называемое строгим порядком, по следующему правилу:
x < y ⇔ x 6 y и x 6= y.
Заметим, что отношение строгого порядка не является частичным порядком,
так как не выполняется условие рефлексивности (неверно, что x < x).
Пример 1.7.2. Частичным порядком является



- j
j j
¼
¼
¼
a
b
c
Рис. 1.12
обычное отношение 6 на множестве N. Действитель- но, это отношение рефлексивно (x 6 x), транзитив- но (x 6 y, y 6 z ⇒ x 6 z) и антисимметрично (x 6 y,
y 6 x ⇒ x = y). ¤
Пример 1.7.3. Отношение, изображенное на рис.
1.12, является частичным порядком, а отношение из примера 1.7.1 — нет. ¤
Пример 1.7.4. Отношение включения на булеане P(U) образует ча- стичный порядок. ¤
Заметим, что в примерах 1.7.3 и 1.7.4 имеются элементы x и y, про ко- торые нельзя сказать, что x 6 y или y 6 x (например, при a = x, y = c
из примера 1.7.3). Такие элементы называются несравнимыми. Частичный порядок 6 ⊆ A
2
называется линейным порядком, если любые два элемен- та x и y из множества A сравнимы, т. е. x 6 y или y 6 x (линейным является частичный порядок из примера 1.7.2).
Непустое множество A, на котором зафиксирован некоторый частичный
(линейный) порядок, называется частично (линейно) упорядоченным мно-
жеством (сокращенно ч.у.м. или л.у.м.).
Пример 1.7.5. Пары ; 6i, h[0, 1]; 6i с обычными отношениями 6 об- разуют линейно упорядоченные множества. ¤


1.7. ОТНОШЕНИЯ ПОРЯДКА
39
Пусть hA; 6i — частично упорядоченное множество. Определим на мно- жестве A
2
отношение Π условием
(a
1
, b
2
) Π (a
2
, b
2
) ⇔ a
1 6 a
2
и b
1 6 b
2
.
Отношение Π есть отношение частичного порядка. Оно называется отноше-
нием Парето. Пара hA
2
; Πi образует частично, но не линейно упорядоченное множество, если |A| > 1.
Элемент a ∈ A частично упорядоченного множества A = hA; 6i называ- ется максимальным (минимальным), если для всех x ∈ A из a 6 x (x 6 a)
следует x = a. Элемент a ∈ A называется наибольшим (наименьшим), если
x 6 a (a 6 x) для всех x ∈ A. Наибольший (наименьший) элемент ч.у.м. A
(если он существует) обозначается через max A (min A). Наибольший эле- мент часто называют единицей, а наименьший — нулем множества A. За- метим, что всякий наибольший элемент является максимальным, а всякий наименьший элемент — минимальным. Обратное утверждение, вообще гово- ря, неверно (см. пример 1.7.6). Всякое конечное ч.у.м. содержит как макси- мальные, так и минимальные элементы.
Пример 1.7.6. Частично упорядоченное множе-



³³
³³
³³
³³
1
PPP
PPP
PP
q i
i i
¸
¸
K
1 3
2
Рис. 1.13
ство h{1, 2, 3}; 6i, изображенное на рис. 1.13, имеет наибольший элемент 2, минимальные элементы 1, 3,
но не имеет наименьшего элемента. ¤
Пример 1.7.7. Линейно упорядоченное множе- ство h[0, 1); 6i имеет наименьший элемент 0, но не имеет наибольшего элемента. ¤
Пусть A = hA; 6i — ч.у.м., B — подмножество A. Элемент a ∈ A называ- ется верхней (нижней) гранью множества B и пишут B 6 a (соответственно
a 6 B), если b 6 a (a 6 b) для всех b ∈ B.
Пример 1.7.8. Рассмотрим ч.у.м. hR; 6i и интервал B = (0, 1]. Тогда любое число x > 1 является верхней гранью B, а любое число x 6 0 —
нижней гранью B. ¤
Элемент a ∈ A называется точной верхней гранью (супремумом) мно- жества B (обозначается sup B), если a — наименьшая из верхних граней множества B. Элемент a ∈ A называется точной нижней гранью (инфиму-
мом) множества B (обозначается inf B), если a — наибольшая из нижних граней множества B.

40
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
В примере 1.7.8 имеем sup B = 1, inf B = 0.
Линейный порядок 6 на множестве A называется полным, если каж- дое непустое подмножество множества A имеет наименьший элемент. Пара
hA; 6i, в которой отношение 6 является полным порядком на множестве A,
называется вполне упорядоченным множеством (сокращенно в.у.м.).
Пример 1.7.9. Пара ; 6i является в.у.м., а пара h[0, 1]; 6i — нет,
поскольку, например, полуоткрытый интервал (1/2, 1], являющийся подмно- жеством [0, 1], не содержит наименьшего элемента. ¤
Определим отношение, на котором основано упорядочение слов в словарях.
Рассмотрим непустое множество символов X = {x, y, z, . . .}, называемое
алфавитом. Конечные наборы написанных друг за другом символов из X
называются словами (например, x, y, xy, yx, zxx, xyyz и т. д.). Элемент x
i
слова x
1
x
2
. . . x
n
называется его i-й координатой. Число n называется длиной
слова x
1
x
2
. . . x
n
. Множество слов алфавита X обозначим через W (X). При этом будем считать, что W (X) содержит слово Λ, не имеющее символов и называемое пустым словом. Длина пустого слова Λ по определению равна нулю. Заметим, что каждое слово x
1
x
2
. . . x
n
из W (X) взаимно однозначно соответствует упорядоченному набору hx
1
, x
2
, . . . , x
n
i из X
n
. Следовательно,
множество W (X) биективно множеству
n∈ω
X
n
, и, значит, бесконечно.
Пусть 6 — отношение порядка на множестве X. Определим на множестве
W (X) отношение лексикографического порядка L по следующему правилу:
x
1
x
2
. . . x
m
L y
1
y
2
. . . y
n
(m 6 n и x
i
= y
i
для всех 1 6 i 6 m) или (суще- ствует i 6 m такое, что x
i
< y
i
, и для всех j < i выполняется x
j
= y
j
).
Утверждение 1.7.1. Если hX; 6i — л.у.м., то hW (X); Li — л.у.м.
Доказательство. Рефлексивность и транзитивность отношения L
очевидны.
Для проверки антисимметричности предположим,
что x
1
x
2
. . . x
m
L y
1
y
2
. . . y
n
и y
1
y
2
. . . y
n
L x
1
x
2
. . . x
m
. Так как отношение 6
антисимметрично, не существует i такого, что x
i
6= y
i
и x
j
= y
j
для всех
j < i. Тогда по определению отношения L получаем m 6 n, n 6 m, т. е.
m = n, и x
1
x
2
. . . x
m
= y
1
y
2
. . . y
n
. Покажем теперь, что любые два слова
ˆ
X = x
1
x
2
. . . x
m
и ˆ
Y = y
1
y
2
. . . y
n
сравнимы. Пусть i — максимальный индекс,
такой, что x
j
= y
j
для всех j < i. Если x
i
< y
i
или i = m + 1 6 n, то ˆ
X L ˆ
Y .
Если y
i
< x
i
или i = n + 1 6 m, то ˆ
Y L ˆ
X. Если же указанные случаи не выполняются, то m = n = i − 1 и ˆ
X = ˆ
Y . ¤


1.7. ОТНОШЕНИЯ ПОРЯДКА
41
Как показывает следующий пример, если |X| > 2, система hW (X); Li
не является в.у.м.
Пример 1.7.10. Рассмотрим в.у.м. hX; 6i, где X = {0, 1}, 6 = {(0, 0),
(0, 1), (1, 1)}. Бесконечное множество, состоящее из слов
1, 01, 001, . . . , 00 . . . 01, . . .
не имеет наименьшего элемента по отношению L. Следовательно, система
hW (X); Li не является в.у.м. ¤
Обозначим через W
n
(X) множество слов алфавита X, длина которых не превосходит n, через L
n
— ограничение отношения L на множество W
n
(X):
L
n
­ L ∩ (W
n
(X))
2
Утверждение 1.7.2. Если hX; 6i — в.у.м., то hW
n
(X); L
n
i — в.у.м.
для любого n ∈ ω.
Доказательство. В силу утверждения 1.7.1 достаточно показать,
что любое непустое подмножество Y множества W
n
(X) имеет наименьший элемент по отношению L
n
. Если Λ ∈ Y , то Λ является наименьшим эле- ментом. Предположим теперь, что Λ /
∈ Y . Рассмотрим множество Y
1
⊆ Y ,
состоящее из слов, у которых первая координата является наименьшей среди первых координат слов из Y . Если Y
1
содержит слово длины 1, то оно будет наименьшим элементом множества Y . В противном случае рассмотрим мно- жество Y
2
⊆ Y
1
, состоящее из слов, у которых вторая координата является наименьшей среди вторых координат слов из Y
1
. Если Y
2
содержит слово длины 2, то оно будет наименьшим элементом множества Y . В противном случае аналогично определим множество Y
3
и будем продолжать построение множеств Y
k
до тех пор, пока в Y
k
не найдется слово длины k, которое будет наименьшим элементом множества Y . По определению множества W
n
(X)
такое слово определится не более чем за n шагов. ¤
Пример 1.7.11. Рассмотрим множество букв русского алфавита, кото- рое обозначим через A. Определим на A полный порядок 6 в соответствии с обычным упорядочением букв по алфавиту. Пусть n — натуральное чис- ло, ограничивающее длину слов, употребляемых в русском языке, например
n = 1000. Отношение L
n
на множестве W
n
(A) определяет упорядочение слов,
по которому составляются словари. ¤

42
Глава 1. ЭЛЕМЕНТЫ ТЕОРИИ МНОЖЕСТВ
Рассмотрим частично упорядоченное множество hA; 6i. Говорят, что эле- мент y покрывает элемент x (обозначается x ≺ y), если x 6 y и не су- ществует такого элемента z, что x < z < y. Если множество A конечно,
частично упорядоченное множество hA; 6i можно представить в виде схе- мы, в которой каждый элемент изображается точкой на плоскости, и если
y покрывает x, то точки x и y соединяют отрезком, причем точку, соответ- ствующую x, располагают ниже y. Такие схемы называются диаграммами
Хассе. На рис. 1.14 показаны две диаграммы Хассе. Вторая диаграмма со- ответствует линейно упорядоченному множеству.
Пример 1.7.12. 1. Рассмотрим частично упорядо-






¡
¡
¡
@
@
@
¡
¡
¡
@
@
@





а
б
Рис. 1.14
ченное множество hP(A); ⊆i, где A = {1, 2, 3}. Множе- ство P(A) содержит восемь элементов: {0, {1}, {2}, {3},
{1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. На рис. 1.15a изображена диаграмма Хассе, соответствующая hP(A); ⊆i.
2. Пусть A = {1, 2, 3, 5, 6, 10, 15, 30}. Рассмотрим отношение частичного порядка 6 на множестве A, зада- ваемое по правилу: x 6 y ⇔ y делится на x. Диаграмма
Хассе для ч.у.м. hA; 6i изображена на рис. 1.15б.
3. На рис. 1.15в изображена диаграмма Хассе линейно упорядоченного множества h{0, 1, 2, 3, 4, 5, 6, 7}; 6i c обычным отношением порядка на мно- жестве натуральных чисел, не превосходящих семи. ¤








¡
¡
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
@
@
¡
¡
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
@
@

{1}
{2}
{3}
{1,2}
{2,3}
{1,3}
{1,2,3}








¡
¡
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
@
@
¡
¡
¡
¡
¡
¡
¡
¡
@
@
@
@
@
@
@
@
1 2
3 5
6 10 15 30








0 1
2 3
4 5
6 7
а
б
в
Рис. 1.15