Множества, операции над ними и парадокс Рассела

Доска 1 — множество, способы задания и операции; диаграмма Венна

Доска 2 — парадокс Рассела, типы по сторонам знака принадлежности, универсум и симметрическая разность

Наш курс дискретной математики — один из трёх самых длинных курсов в вашей учебной программе. Три курса, которые продолжаются четыре семестра, — это дискретная математика, математический анализ и алгоритмы и структуры данных. Эти три курса будут с вами все первые четыре семестра. На нашем курсе дискретной математики мы с вами пройдём, в определённом смысле обзорно — что-то более глубоко, что-то менее глубоко, — вещи, связанные с основаниями всего того, что мы делаем на компьютере, и с теоретическими вопросами, с этим связанными.

В первом семестре, который сейчас начинается, мы будем говорить в основном о следующих вопросах. Сначала о теоретических основах представления информации в компьютере, о булевых функциях и методах работы с ними: как вообще устроена информация, как школьный предмет информатика связан с компьютерами и как он связан с математикой. С этого мы начнём. Потом поговорим об алгоритмах представления и преобразования информации — именно с теоретической точки зрения. А в конце семестра перейдём к комбинаторике. Вы увидите, что каждая тема будет плавно перетекать в следующую; резких переходов, когда мы закончили одну тему и начали другую, не будет — курс получится плавным.

В первом семестре курс продолжается до декабря. Подробнее о формах отчётности и о том, что у нас будет происходить на курсе, расскажу я и мои коллеги, которые ведут у вас практику: как раз на этой первой неделе практик мы всё это обсудим. Все материалы своего курса я стримлю в Twitch. Для вас это, наверное, не главное — вы все пришли сюда, и стрим вам не очень интересен. Но если вы, не дай бог, заболели или с вами что-то случилось, то лекцию можно посмотреть в стриме. Кроме того, записи лекций я выкладываю на свой YouTube-канал: у меня там тот же ник, что и в Телеграме, — andrewzta. Там же выложены лекции прошлых лет, но пересматривать их я вам не советую; если по какой-то теме прошлогодняя лекция освещает вопрос иначе, я скажу об этом отдельно. Правда, за первый семестр лекций там нет — выкладывать я начал только в конце прошлого семестра, когда мы перешли в онлайн-обучение, так что эти лекции будут опубликованы впервые.

Ещё одна организационная деталь: у вас два лектора — это я и Артём Тарасович. Мы читаем лекции подряд: сначала он в этой же аудитории, потом я. Он тоже выкладывает свои лекции на YouTube, поэтому, если вы какую-то тему не поняли в моём изложении, можете посмотреть его видеозапись — возможно, он расскажет это чуть по-другому и будет понятнее. В прошлом году некоторые ходили на лекцию виртуально даже дважды: сначала смотрели одну лекцию, потом другую. Если у вас слишком много свободного времени, в принципе, можете так делать. А если наоборот, времени слишком мало, можете пересматривать на удвоенной скорости.

Давайте потихоньку перейдём к дискретной математике. Сейчас будет немножко грустная часть нашей лекции, потому что мы будем говорить о банальных и понятных вещах, про которые вы наверняка либо уже слышали, либо их знаете. Но нам нужно это проговорить, чтобы мы с вами говорили на одном языке — как настраивают радиоприёмник на частоту или фокус камеры. Мы хотим, чтобы одни и те же вещи назывались у нас одинаковыми именами. Поэтому было бы очень хорошо дать в самом начале определения всем базовым понятиям дискретной математики и с этого начать.

К сожалению, первое же определение, которое мы хотели бы дать, дать нельзя: вся математика базируется на неопределяемом понятии, которое представляется людям чисто интуитивно, — это понятие множества. Мы можем пытаться дать ему определение, но любая попытка приводит к зацикливанию. Множество — это совокупность каких-то объектов; неплохо, но что такое совокупность? Это набор каких-то объектов; а что такое набор? И так, как бы мы ни пытались, формального определения множества дать не получается. Деваться некуда — придётся жить на этом довольно хилом фундаменте. В современной математике считается, что у людей есть некоторое внутреннее интуитивное понимание множества.

Когда вы будете изучать математическую логику или определённые разделы математического анализа, вам придётся работать с очень большими множествами, в которых элементов столько, что их нельзя занумеровать натуральными числами даже до бесконечности, — это несчётные множества. Вот там возникают сложные вопросы, на которые либо неизвестен ответ, либо известно, что ответ дать нельзя, либо несколько разных ответов одинаково совместимы с современной аксиоматикой теории множеств. Бывают ли вообще очень большие множества, сколько у них разных градаций и так далее. К счастью для нас, для дискретной математики этот вопрос не очень актуален: дискретная математика — она дискретная. Мы будем работать с конечными или счётными множествами, то есть с множествами, в которых либо какое-то конкретное количество элементов — 0, 1, 2, 3 и так далее, — либо бесконечное число элементов, но эти элементы можно занумеровать натуральными числами. Несчётные множества будут возникать у нас только в самых пограничных темах, когда мы будем немножко расширять нашу сферу обсуждения, и это всегда будут optional, дополнительные темы.

Итак, в базе всего того, что мы изучаем, лежит понятие множества, которому формального определения не даётся. Тем не менее мы будем работать с этими объектами. Традиционно мы будем обозначать множества большими буквами латинского алфавита — по умолчанию, хотя в разных ситуациях можем захотеть обозначать и по-другому. С множествами связаны их элементы: множества состоят из элементов, и эти элементы множеству принадлежат. Для этого используется такая запись: если у нас есть какой-то элемент, скажем aa, и он лежит в множестве AA, мы пишем a∈Aa \in A — aa принадлежит множеству AA.

Конечное множество можно задать, просто перечислив все его элементы. Например, скажем, что множество AA состоит из чисел 2, 3 и 9: A={2,3,9}A = \{2, 3, 9\}. Мы получили множество из трёх чисел и задали его конкретными элементами. Если же множество бесконечное — например, все натуральные числа, — то так задать его нельзя, и мы даём тогда описательное определение. Здесь можно было бы построить аксиоматическое определение натуральных чисел, но это предмет другого курса, математической логики, поэтому вдаваться в это мы не будем.

Иногда мы хотим взять какое-то известное нам множество и дальше его ограничить. Например, возьмём множество всех чётных натуральных чисел. Как мы это запишем? Мы пишем так: A={n∣n чётно}A = \{n \mid n \text{ чётно}\}. Вот эта вертикальная палка означает, что после неё написано условие на числа. Вообще говоря, я написал плохо: nn чётно, но какое nn? Может быть, оно целое, может быть отрицательное — непонятно. Поэтому, если запись не снабжена устным комментарием, нужно писать условие полностью: A={n∣n чётно, n∈N}A = \{n \mid n \text{ чётно},\ n \in \mathbb{N}\}. Вертикальная палочка называется фильтр: мы говорим, что берём те элементы, которые удовлетворяют этому условию. Некоторые авторы вместо палки пишут двоеточие.

С множествами можно делать разные операции. Наиболее естественные теоретико-множественные операции — это объединение и пересечение. Если у нас есть два множества AA и BB, мы можем рассмотреть A∪BA \cup B — множество всех элементов, которые лежат в одном множестве или в другом: A∪B={a∣a∈A∨a∈B}A \cup B = \{a \mid a \in A \lor a \in B\}. Обратите внимание, мы воспользовались обозначением, которое только что ввели: написали вертикальную палку и дальше критерий на элементы. «Или» здесь не исключающее, поэтому элементы, которые лежат в обоих множествах, разумеется, тоже попадают в объединение. Аналогично определяется пересечение: A∩B={a∣a∈A∧a∈B}A \cap B = \{a \mid a \in A \land a \in B\} — множество элементов, которые лежат и в AA, и в BB.

Следующая операция — вычитание множеств: A∖B={a∣a∈A∧a∉B}A \setminus B = \{a \mid a \in A \land a \notin B\}. Зачёркнутым значком принадлежности мы обозначаем тот факт, что элемент множеству не принадлежит. Как только у нас появилось «не принадлежит», сразу возникла следующая проблема, которая в начале XX века очень сильно озадачила учёных — в частности, такого специалиста, как Бертран Рассел. А какие вообще элементы можно включать в множество, а какие нельзя? Например, можно ли составить множество всех множеств? Можно ли составить множество всех элементов, которые не лежат в каком-то множестве, то есть рассмотреть дополнение Aˉ={a∣a∉A}\bar{A} = \{a \mid a \notin A\}? Можно так записать или нет? Я поставил здесь на доске вопросительные знаки, потому что возникает вопрос: а каких именно «всех» элементов?

Рассмотрим наше множество A={2,3,9}A = \{2, 3, 9\}. Число 5 в нём явно не лежит, и 5 в некотором смысле имеет для нас ту же природу, что элементы 2, 3 и 9, поэтому нам психологически приятно сказать, что 5 принадлежит дополнению к AA. А вот возьмём, скажем, этот маркер. Он лежит в множестве AA? В принципе, нет: маркер — это не 2, не 3 и не 9, это маркер. Но здесь уже не совсем очевидно, есть ли вообще смысл разбираться с этим вопросом — принадлежит ли маркер этому множеству, — ведь множество вроде составлено из чисел, а тут маркер.

А можно ли составить множество из маркера, дырокола и моего мобильного телефона? В принципе, непонятно, почему бы нет: три элемента, не бесконечность, никаких парадоксов пока не возникает. Но когда мы составили такое множество, то микрофон, который стоит у меня и записывает звук, этому множеству не принадлежит, и это логично: предметы лежат тут на столе — множество мы составили из маркера, дырокола и телефона, а микрофон тоже на столе, но составленному множеству не принадлежит. А вот средство для дезинфекции, которое на том столе, в этом множестве не лежит, но оно вроде близко к этим элементам, хотя и не на этом столе. Возникают такие тонкости. И если на эти тонкости совсем забить и сказать, что множество можно составить из чего угодно, то возникает логический парадокс, известный как парадокс Рассела.

Давайте рассмотрим множество всех множеств — точнее, не всех множеств, а всех множеств, которые не содержат себя: R={a∣a — множество, a∉a}R = \{a \mid a \text{ — множество},\ a \notin a\}. Попробуем выяснить, лежит ли само множество RR в себе. Оба варианта приводят к парадоксу: если оно принадлежит себе, то по определению оно должно себе не принадлежать; если оно себе не принадлежит, то оно должно себе принадлежать. Это стало мотивацией для учёных начала XX века создать аксиоматическую теорию множеств, в которой такие конструкции запрещены, — и этот парадокс отодвинули. Может быть, возникли какие-то другие, про которые пока неизвестно.

— А маленькое aa — это тоже множество? Может ли множество само себе принадлежать?

— Почему бы нет? Множество всех множеств взяли — можем взять. Оказывается, нет: а почему оно должно себе принадлежать? Вот этому множеству принадлежат три элемента — 2, 3 и 9, — а само множество AA множеству элементов 2, 3 и 9 не принадлежит. Оно не является его подмножеством, но, что важно, именно не принадлежит; про подмножества мы вообще ещё даже не говорили.

Обратите внимание на значок принадлежности: у него разного типа объекты слева и справа. Программистам это объяснить достаточно легко. Когда я пишу a∈Aa \in A, то aa у меня типа TT, а AA — типа set⟨T⟩\mathrm{set}\langle T \rangle. Поэтому запись вида a∈aa \in a в этом смысле подозрительна: C++ такое бы не скомпилировал, ему бы это не понравилось. Но если забить на систему типов и считать, что у нас всё что угодно можно составить из чего угодно, то кажется, что множество всех таких множеств составить можно, — а на самом деле нельзя.

Это я говорю не к тому, что хочу перейти к математической логике, а к тому, что, когда мы пишем «не принадлежит», из наших примеров — и с числами, и с предметами на столе — возникает желание как-то ограничить спектр элементов, из которых мы вообще выбираем. Поэтому традиционно — в дискретной математике по крайней мере, да и в анализе более-менее тоже — чтобы не сражаться с парадоксами теории множеств каждый раз, когда мы обсуждаем множества и дополнения к ним, рассматривая какое-то множество, всегда говорят, что есть некоторый универсум UU, из которого мы выбираем элементы. По парадоксам теории множеств можно прочитать отдельный семестровый курс — довольно бесполезный, надо сказать, и ничего особо ценного он не даст.

Часто универсум зафиксирован неявно. Например, когда мы говорим о множестве чисел, мы обычно подразумеваем какой-то универсум: либо натуральные числа, либо целые, либо вещественные. Мы не подразумеваем, что берём в качестве объектов вообще абстрактно всё что угодно. Аналогично, когда я рассматривал предметы у себя на столе, логично было взять в качестве универсума либо предметы на этом столе, либо предметы в этой комнате, либо вообще все предметы, когда-либо созданные человеком. Любое из этих множеств конечно и чётко очерчено универсумом. Если у нас есть универсум, то дополнение к AA становится более понятным, и можно дать более точное определение: Aˉ=U∖A\bar{A} = U \setminus A. Ещё раз повторю: обычно универсум либо подразумевается — есть какое-то естественное множество объектов, которые мы рассматриваем, и мы из него при необходимости вычитаем или рассматриваем только его подмножество, — либо он оговаривается явно, если не очевиден из контекста. А в парадоксы теории множеств мы дальше, если это специально не оговорено, углубляться не будем: это предмет немножко другого курса.

Кстати, если у нас есть операция дополнения, то вычитание можно переписать через пересечение: A∖B=A∩BˉA \setminus B = A \cap \bar{B}. На множествах можно задать и много других операций. Например, операцию симметрической разности. Обозначается она по-разному: либо треугольничком, A △ BA \,\triangle\, B, либо плюсиком в кружочке, A⊕BA \oplus B. Это множество элементов, которые лежат ровно в одном из множеств AA и BB, то есть A △ B=A⊕B=(A∪B)∖(A∩B)A \,\triangle\, B = A \oplus B = (A \cup B) \setminus (A \cap B).

Когда речь идёт о множествах, то для того, чтобы визуализировать взаимоотношения между ними, часто используют так называемые диаграммы — их называют кругами Эйлера или диаграммами Венна. Это просто картинки, на которых множество обозначается кружочком. Вот есть множество AA, есть множество BB; всё это вместе, всё пространство внутри обоих кружков — это A∪BA \cup B. Вот эта область, общая часть, — это A∩BA \cap B. А вот эта территория, которая обозначена одним кружочком без общей части, — это A∖BA \setminus B.

Круги Эйлера, декартово произведение и подмножества

Доска 3 — три конфигурации трёх множеств: почему круги Эйлера только иллюстрируют

Доска 4 — декартово произведение, ассоциативность и декартова степень

Доска 5 — пример A × A и различие знаков принадлежности и включения

Симметрическая разность — это что? Это вот эта часть и вот эта. Хорошо. Теперь я хочу обратить ваше внимание на следующее: хотя диаграммы Венна, круги Эйлера, часто служат иллюстрацией, использовать их как доказательство можно только в совсем простых случаях, когда на картинке действительно очевидно, что всё правильно. Если множеств уже три или четыре, то диаграмма годится лишь как иллюстрация, но не как доказательство каких-то свойств. Когда множеств два, они либо не пересекаются, либо пересекаются — особых вариантов нет. А вот если мы пытаемся изобразить три множества, то здесь возникают значительные вариации в том, как именно они могут выглядеть взаимно.

Например, три множества могут образовывать цепочку: A∩B≠∅A \cap B \neq \varnothing, B∩C≠∅B \cap C \neq \varnothing, а первое и третье вообще не пересекаются, A∩C=∅A \cap C = \varnothing. Могут иметь общее пересечение — это классическая диаграмма Венна, где A∩B∩C≠∅A \cap B \cap C \neq \varnothing. А могут иметь все попарные пересечения, но не иметь общего: A∩B∩C=∅A \cap B \cap C = \varnothing. Поэтому, когда речь идёт о доказательстве свойств каких-то объектов, иллюстрация — это хорошо, но сама по себе доказательством она, конечно, не является. Гораздо подробнее о том, что такое доказательство, как вообще решать задачи и как правильно формулировать мысли про доказательства, мы поговорим с вами на практике.

Давайте теперь посмотрим на следующее. Если мы работаем только с множествами и теоретико-множественными операциями, нам довольно тяжело: для построения нормальных математических теорий нужна ещё одна операция над множествами. В теории множеств она существует даже как аксиоматическая и называется конструкцией пары, хотя формулируется там чуть иначе. Во многих языках программирования пара тоже является фундаментальным инструментом работы. Что такое пара? Пусть у нас есть множество AA и множество BB. Тогда мы можем рассмотреть множество пар элементов, где первый элемент выбран из множества AA, а второй — из множества BB.

Это множество называется декартовым произведением, или просто произведением, множеств AA и BB и обозначается A×BA \times B. Итак, A×BA \times B — это множество упорядоченных пар {(a,b)∣a∈A, b∈B}\{(a, b) \mid a \in A,\ b \in B\}. Соответственно, если оба множества совпадают и мы берём A×AA \times A, то получается в определённом смысле степень множества, и её поэтому можно обозначать как A2A^2.

Раз квадрат мы возвели, естественно возникает желание возвести и в какую-нибудь другую степень. Возникает у вас такое желание? Давайте посмотрим. Здесь появляется следующий вопрос. Мы можем рассмотреть (A×B)×C(A \times B) \times C — давайте попробуем формально раскрыть это по определению. Это будет множество пар (x,y)(x, y), где x∈A×Bx \in A \times B, а y∈Cy \in C. Теперь раскроем xx: получаем (A×B)×C={((a,b),y)∣a∈A, b∈B, y∈C}(A \times B) \times C = \{((a, b), y) \mid a \in A,\ b \in B,\ y \in C\}, причём yy дальше уже не расчленить никак — он имеет максимально примитивный тип.

А можем рассмотреть иначе: взять AA и составить пару с B×CB \times C. Думаю, не расписывая промежуточное состояние, мы можем сразу записать, что A×(B×C)={(a,(y,z))∣a∈A, y∈B, z∈C}A \times (B \times C) = \{(a, (y, z)) \mid a \in A,\ y \in B,\ z \in C\}. Формально говоря, если так на это посмотреть, это два разных множества: первое — множество пар, где первый компонент есть пара, второе — множество пар, где второй компонент есть пара. Но по смыслу и то, и другое — это, в принципе, тройки. А мы могли бы захотеть написать ещё и так: A×B×C={(a,b,c)∣a∈A, b∈B, c∈C}A \times B \times C = \{(a, b, c) \mid a \in A,\ b \in B,\ c \in C\} — множество троек.

С точки зрения теории типов это разные вещи. Если так написать в C++ и считать, что AA, BB, CC — это int, то в первом случае у нас будет pair<pair<int,int>,int>, во втором — pair<int,pair<int,int>>, а в третьем такого готового типа в C++ нет, но можно сказать, что это tuple<int,int,int> — кортеж из трёх int. С точки зрения программирования это, конечно, важно, а с точки зрения дискретной математики, да и вообще чаще всего, не важно. Более того, запись с тремя сомножителями плоха тем, что мы считаем крест операцией на множествах, которая берёт два множества и возвращает новое, и хотелось бы придать ей какую-то ассоциативность — либо левую, либо правую. Плохо, когда два креста обозначают на самом деле тройку.

Поэтому для простоты здесь и далее, если не оговорено обратное, — а обратное, насколько я помню, за весь курс до конца семестра не будет оговорено никогда, — мы будем считать операцию взятия произведения множеств ассоциативной и будем считать, что она всегда раскрывается в тройку. То есть (A×B)×C(A \times B) \times C и A×(B×C)A \times (B \times C) переходят в A×B×CA \times B \times C, и мы не будем различать, как именно расчленены пары. Если с помощью конструкции произведения множеств мы слева направо задаём множество объектов — здесь (a,b)(a, b) и yy, здесь aa и (y,z)(y, z), здесь a,b,ca, b, c, — то на самом деле всё это просто задаёт порядок на трёх элементах разными технологическими способами, но идеологически одно и то же: три элемента, первый, второй, третий. Здесь и далее мы будем считать, что это просто произведение A×B×CA \times B \times C, и не будем отдельно выделять левоассоциативные или правоассоциативные конструкции.

Если так сделать, нам особенно удобно определять степени. Вот A×A×A=A3A \times A \times A = A^3 — это тройки, каждый элемент которых принадлежит AA. И так далее: можно определить любую степень, получится AnA^n. У нас пока есть только декартова степень. Вообще говоря, дальше, когда вы будете изучать другие разделы математики, множества будут перемножаться не только декартово: если множество наделено какой-то операцией, то можно перемножить множества, распространив эту операцию и на результат. Там будут всякие более сложные конструкции — произведения множеств, наделённых операцией, внешние, внутренние произведения и так далее, и тогда около степени пишут значок, какая именно степень имеется в виду.

У нас пока всё просто: множества не наделены никакой внутренней структурой или операцией, поэтому единственное, что мы можем с ними сделать, — это декартово перемножить, поэтому пишем просто степень. По определению An=AA^n = A, если n=1n = 1, и An=A×An−1A^n = A \times A^{n-1}, если n>1n > 1.

Но хочется обсудить ещё один вопрос. Как вы думаете, можно ли множество декартово возвести в нулевую степень? Какая ваша точка зрения на этот вопрос? Интуиция подсказывает, что получится какой-то нейтральный элемент относительно умножения. Но что такое у нас умножение? Умножение — это, грубо говоря, запись подряд: мы умножаем AA на B×CB \times C и записываем элемент из AA перед парой из B×CB \times C. Что можно записывать перед чем-то или после чего-то, чтобы ничего не менялось? Какую-то пустоту.

Соответственно, что такое A0A^0? Что такое AnA^n? Это наборы из nn элементов, каждый из которых принадлежит множеству AA, правильно? Тогда A0A^0 — это наборы из нуля элементов, каждый из которых — ну там уже не важно, их всё равно ноль — пусть принадлежит множеству AA. Значит, A0A^0 — это множество, которое содержит единственный элемент: пустую последовательность. Обозначается она по-разному: иногда как ε\varepsilon, иногда пустыми квадратными или круглыми скобками, то есть A0={ε}={[ ]}A^0 = \{\varepsilon\} = \{[\,]\}. Но чтобы не возникало неоднозначности понимания, обычно её обозначают именно ε\varepsilon.

Почему этот элемент всего один? У тех, кто только начинает формально знакомиться с этой теорией, здесь возникает вопрос следующего характера: сколько существует пустых последовательностей, то есть последовательностей длины ноль, — ноль или одна? Это обычно называют философским вопросом: пустых последовательностей ноль или она одна, и почему она одна, а вдруг их больше. Здесь можно привести разные аргументы в пользу того или иного, но по смыслу пустая последовательность есть. Если элементы последовательности — это какие-то действия, то можно ничего не делать, и это будет пустая последовательность. Почему ничего не делать — это ровно один способ? Если делать что-то можно разными способами, то ничего не делать есть только один способ. Хотя, говорят, студенты знают много способов ничего не делать, но с математической точки зрения они все одинаковые. Это и есть пустая последовательность.

Теперь к вопросу, который я видел.

— Может ли в определении пары множество AA совпадать с множеством BB?

— Конечно, может. Почему же не может? Давайте посмотрим на определение A×AA \times A. Подставим в определение, чтобы всё не переписывать, только чуть-чуть поменяем: у нас тут (a,b)(a, b). Написано ли в определении где-нибудь, что A≠BA \neq B? У меня на доске не написано, и поэтому, в частности, может быть и A=BA = B.

Давайте рассмотрим пример. Если мы возьмём наше множество A={2,3,9}A = \{2, 3, 9\}, как мы уже делали, то A×AA \times A мне лень выписывать полностью, но если начать: что можно взять в качестве первого компонента? Например, 22. Тогда в качестве второго можем взять 22, 33 и 99 — получаем (2,2), (2,3), (2,9)(2,2),\ (2,3),\ (2,9). Дальше можно сказать, что первый элемент — это 33, и тогда будет (3,2), (3,3)(3,2),\ (3,3) и так далее. Обратите внимание: во-первых, один и тот же элемент можно брать и как первый компонент, и как второй; во-вторых, порядок важен — (2,3)(2,3) и (3,2)(3,2) это разные пары, у пары есть первый компонент и есть второй.

— А может ли множество содержать два одинаковых элемента?

— Хороший вопрос. Множество по определению не может содержать двух одинаковых элементов. Что это значит, как это понять? Что значит, что в множестве есть одинаковые элементы? Формально мы множество не определяли — это было наше неформальное, внутреннее понятие совокупности элементов. Но если перейти к физическому смыслу, когда перед нами выставлены предметы: вот эти два маркера, они в множестве, и они вроде как одинаковые, но на самом деле это же вот этот маркер и вот этот, и в этом смысле, формально говоря, они разные. А если у нас какой-то математический объект, например две единицы, — можно ли включить обе? Ответ: нельзя, либо единица входит в множество, либо нет.

Можно обобщить конструкцию множества и разрешить учитывать в нём один и тот же элемент не один раз. Тогда возникает вопрос, как это формально записать, то есть появится какая-то кратность вхождения элемента в множество. Такой математический объект есть, он называется мультимножеством. С точки зрения матлогики там есть свои заморочки: если мы разрешаем элементу входить в множество несколько раз, то он может входить и бесконечное число раз, и тогда бесконечность плюс один — если элемент входит бесконечно много раз и мы добавили ещё один, изменилось мультимножество или нет? Эти вопросы нас с вами интересовать не будут, а с точки зрения комбинаторики, когда мы рассматриваем совокупности объектов, в которых порядок не важен, а один и тот же объект может входить несколько раз, мы мультимножества рассмотрим ближе к концу семестра. Для конечных множеств, с точки зрения подсчёта или генерации, этот объект имеет право на существование. С математической точки зрения вопрос, как формально определить его для бесконечных множеств, трудный, а для конечных, в принципе, можно определить мультимножество как функцию — сейчас мы рассмотрим формальное понятие функции, и вы поймёте.

— А порядок элементов в множестве?

— Порядок внутри множества действительно роли не играет, а вот когда мы рассматривали пару, в паре порядок важен. Давайте ещё раз зафиксируем про множество. У множества есть элементы, и каждый элемент из некоторого универсума, заданного явно или неявно, либо входит в множество, либо нет — возможны только два варианта. Он не может входить в множество несколько раз, и он не может входить на какую-то позицию. Порядок внутри множества роли тоже не играет.

Теперь следующий объект, связанный с множествами, который мы с вами рассматриваем, называется функцией. Что такое функция формально? Формально функция — это отображение, которое каждому элементу одного множества, из AA в BB, ставит в соответствие какой-то элемент множества BB. Как это формально записать? Записывается это с помощью инструмента, который мы с вами уже сформулировали, — с помощью прямого (декартова) произведения. Мы рассмотрим функцию формально как её график. Графиком функции называется множество пар {(x,f(x))}\{(x, f(x))\}.

Это, в принципе, совпадает с вашим школьным пониманием смысла слова «график»: мы рисуем график функции x2x^2, у нас есть множество точек на плоскости, где каждому xx мы сопоставили координату y=x2y = x^2 и эту точку отметили. Соответственно, с формальной точки зрения мы будем отождествлять понятие функции и её графика — разумеется, не постоянно, но когда мы формализуем понятие функции, мы так делаем. И тогда по определению функцией называется подмножество f⊂A×Bf \subset A \times B такое, что для любого a∈Aa \in A существует единственное — это одно новое обозначение, мы его с вами обсудим — существует единственное b∈Bb \in B такое, что пара (a,b)(a, b) принадлежит множеству ff. Коротко: ∀a∈A ∃! b∈B:(a,b)∈f\forall a \in A\ \exists!\, b \in B: (a, b) \in f.

Вот это определение формальной функции; оно может быть вам немного непривычно, но зато оно сформулировано на языке теории множеств. Итак, что такое функция ещё раз? Функция — это некоторое множество пар: A×BA \times B — это все пары, а мы взяли только некоторые. Для этого есть специальный значок — подмножество, — который многие часто путают со значком принадлежности, поэтому давайте обсудим этот вопрос отдельно.

У нас были множества — какие-то наборы элементов, каждый элемент либо входил в них, либо нет, и мы писали, что элемент принадлежит множеству: a∈Aa \in A. А вот если у нас есть два множества AA и BB и выполнено следующее: для любого aa, если aa входит в AA, то aa входит и в BB, то есть все элементы AA являются также элементами BB — я специально записал это пока без дополнительных обозначений, — если это условие выполнено, то говорят, что множество AA является подмножеством множества BB, и записывают A⊂BA \subset B. Формально: A⊂B  ⟺  ∀a (a∈A⇒a∈B)A \subset B \iff \forall a\,(a \in A \Rightarrow a \in B).

Давайте перейдём к примерам. Например, все числа, кратные четырём, — назовём это множество D4D_4: D4={n∣n кратно 4}D_4 = \{n \mid n \text{ кратно } 4\}. И есть множество чётных чисел, назовём его EE, от even: E={n∣n чётно}E = \{n \mid n \text{ чётно}\}. Понятно, что любое кратное четырём число чётно — если число кратно четырём, то оно тем более кратно двум, — поэтому мы можем записать, что D4⊂ED_4 \subset E. Аналогично, когда у нас конечные множества, там вообще всё понятно: например, если у нас было множество {2,3,9}\{2, 3, 9\}, то оно является подмножеством множества {2,3,4,…,9}\{2, 3, 4, \ldots, 9\}, то есть {2,3,9}⊂{2,3,4,…,9}\{2, 3, 9\} \subset \{2, 3, 4, \ldots, 9\}. Кроме того, любое множество является подмножеством самого себя, A⊂AA \subset A, и пустое множество является подмножеством любого множества, ∅⊂A\varnothing \subset A.

Функции: сюръекция, инъекция, биекция и мощность

Доска 6 — функция как подмножество A × B; сюръективность и инъективность по столбцам таблицы

Доска 7 — мощность, равномощность и множество функций B^A

Заметим, в частности, что если подставить в качестве AA и BB одно и то же множество, то условие включения окажется выполнено: ∀a (a∈A⇒a∈A)\forall a\ (a \in A \Rightarrow a \in A) — верно. Поэтому любое множество является подмножеством самого себя: A⊂AA \subset A. Аналогично можно взять пустое множество: в нём нет никаких элементов, и условие «если элемент принадлежит пустому множеству, то он принадлежит BB» выполнено автоматически — если бы такой элемент вдруг нашёлся, про него после этого можно было бы сказать что угодно. Поэтому пустое множество входит в любое множество: ∅⊂A\varnothing \subset A. И наоборот: тот самый легендарный универсум, который мы сформулировали в начале, содержит любое множество как подмножество — A⊂UA \subset U.

Видите, я сейчас сам сделал такую же описку, какую очень часто делают многие: спутал значки принадлежности и включения. Поэтому я отношусь к ней достаточно толерантно и просто исправляю вас так же, как вы только что исправили меня. Математикам, может быть, и тяжело, а вот программистам, мне кажется, должно быть легко различать значки ∈\in и ⊂\subset: слева и справа от них находятся объекты разных типов. Ещё раз напомню: если вы не хотите столкнуться со всякими интересными парадоксами, нет смысла рассматривать совокупности множеств без ограничения, что все они являются подмножествами некоторого универсума. А когда мы работаем внутри универсума, любое множество, которое у нас в рассмотрении, является его подмножеством. Например, если мы рассматриваем только натуральные числа, то любое наше множество будет подмножеством множества натуральных чисел.

Вернёмся к функциям. Функцией называется любое подмножество A×BA \times B, то есть любое семейство пар, которое дополнительно обладает следующим свойством: ∀a∈A ∃!b∈B: (a,b)∈f\forall a \in A\ \exists! b \in B:\ (a, b) \in f. Разберём значки. Значок ∀\forall обозначает «для любого»; он происходит от английского слова for all (или от соответствующего латинского прообраза) — это перевёрнутая буква AA. Значок ∃\exists означает «существует»; это перевёрнутая буква EE, от слова exists.

А восклицательный знак иногда ставят после значка существования, и это синтаксический сахар для «существует единственный». Формально, если обратиться к математической логике, в логике кванторов такого значка нет, и это нужно было бы расписать так: ∃b b∈B (a,b)∈f\exists b\ b \in B\ (a, b) \in f, и если (a,b)∈f(a, b) \in f и (a,c)∈f(a, c) \in f, то b=cb = c. Вот расшифровка синтаксического сахара «существует единственный». Но расписывать такое каждый раз не очень интересно, поэтому мы будем пользоваться обозначением ∃!\exists!.

Обратите внимание на структуру функции. Множество AA — это множество её аргументов, то есть тех элементов, от которых она вызывается. Множество BB — это множество тех элементов, которые могут быть значениями функции. При этом отметим важный факт: не обязательно каждый элемент BB является значением функции на каком-то элементе. Например, функция возведения в квадрат sqr ⁣:N→N\mathrm{sqr}\colon \mathbb{N} \to \mathbb{N} действует на натуральных числах, но те числа, которые полными квадратами не являются, значениями этой функции не оказываются. Нас это не пугает — просто у функций есть дополнительные классы, выделяемые как раз такими свойствами.

Если же каждый элемент BB оказывается результатом действия функции на каком-то элементе, то есть ∀b∈B ∃a∈A: b=f(a)\forall b \in B\ \exists a \in A:\ b = f(a), то такая функция называется сюръекцией, или, иначе, отображением «на».

— Насчёт значков включения есть разные обозначения, принятые разными авторами книг и лекторами. Иногда пишут ⊆\subseteq для нестрогого включения, а ⊂\subset — для строгого. Иногда ⊂\subset обозначает нестрогое включение, а строгое либо подчёркивают отдельным значком, либо вообще не вводят особого обозначения и просто дополнительно пишут, что множества не равны. Я использую второй подход: мой значок ⊂\subset обозначает нестрогое вхождение, а отдельного значка для строгого вхождения у меня нет.

— Может ли функция совпасть со всем декартовым произведением? Формально да, но для функций добиться равенства тяжело: для каждого aa должно быть ровно одно bb, поэтому равенство возможно лишь когда BB одноэлементно. Посмотрите: вот AA, вот BB, вот таблица всех пар. Декартово произведение — это все клетки, а функция — это выбор одного значения в каждой строчке. Чтобы при выборе одного значения в каждой строчке оказались выбраны все клетки, столбцов должно быть ровно один. Так что равенство возможно, но случай этот достаточно редкий.

В терминах этой же картинки сюръективность означает, что в каждом столбце тоже выделено значение. Вот здесь, например, не выделено — это график обычного, не сюръективного отображения. Чтобы оно стало сюръекцией, достаточно переставить одну галочку, например вот так.

Есть ещё один класс функций — инъекции. Различным элементам AA вообще говоря могут соответствовать одинаковые элементы BB: вот как на нашем примере — этому элементу соответствует это значение, и этому тоже, в одном столбце две галочки. Если же в каждом столбце не более одной галочки — сюръекция требовала не менее одной, а здесь не более одной, — то отображение не склеивает элементы, и такое отображение называется инъекцией. Формально: если ∀a∈A ∀b∈A, a≠b⇒f(a)≠f(b)\forall a \in A\ \forall b \in A,\ a \neq b \Rightarrow f(a) \neq f(b), то функция — инъекция.

Можно ли построить инъекцию из пятиэлементного множества в четырёхэлементное? Нельзя — просто не хватит элементов. Мы хотим сопоставить каждому из пяти элементов какой-то из четырёх так, чтобы все они были различны; очевидно, что это невозможно. Иногда это называют принципом Дирихле: не существует инъекции из большего множества в меньшее. Если кроликов больше, чем клеток, и вы каждому кролику сопоставляете клетку, то в какой-то клетке будет сидеть два кролика, а может быть, и больше. Можно сформулировать и обратное утверждение — специального названия у него нет: не существует сюръекции из меньшего множества в большее, не хватит аргументов. То есть если кроликов меньше, чем клеток, и вы рассадите их по клеткам, то обязательно найдётся клетка, в которой никто не сидит.

Если функция одновременно и сюръекция, и инъекция, то она называется биекцией. Что можно сказать про два конечных множества, если между ними существует биекция? Что у них одинаковое количество элементов. Количество элементов множества часто называют мощностью множества и обозначают ∣A∣|A|. Таким образом, если между конечными множествами существует биекция, то они равны по мощности.

Оказывается, верно и обратное: если у множеств равное количество элементов, то между ними можно построить биекцию. Инструментов, чтобы это аккуратно доказать, у нас пока нет, но утверждение выглядит очевидным: элементов одинаковое количество, рассмотрим их в каком-нибудь порядке и сопоставим первому первый, второму второй, третьему третий. Скажем, если у нас есть равное количество студентов и стульев, мы можем рассадить студентов на стулья, то есть как-то сопоставить студентам стулья. Но если пытаться доказать это формально, сразу возникают вопросы оснований математики: а что вообще значит «можем», что нам разрешено делать, как это доказывается? Этим мы задаваться не будем — для конечных множеств примем утверждение как достаточно очевидное.

А вот для бесконечных множеств сразу возникают нюансы: существуют множества, которые оба бесконечны, но биекции между ними не существует. Поэтому для бесконечных множеств понятие мощности вводится заметно сложнее. Пока мы его вводить не будем, хотя к концу сегодняшней лекции сможем это почти сделать — по модулю одного маленького недостатка. Введём пока только определение: два множества называются равномощными, если между ними существует биекция. Для конечных множеств это более-менее очевидно означает равное количество элементов; в частности, никакое конечное множество не равномощно никакому бесконечному. А для бесконечных определение кажется простым, но нюансов там немало.

Когда мы определяли функцию, она сопоставляла каждому элементу множества AA какой-то элемент множества BB. Значит, имея множества AA и BB, мы можем рассмотреть все возможные функции из AA в BB. Это множество обозначается BAB^A. Мы уже вводили понятие степени множества, где показателем было число; теперь мы вводим определение, где показатель степени — это множество.

У этого обозначения есть следующий смысл, и определения оказываются согласованы между собой. Функцию можно задать её таблицей значений. Пусть у нас есть конечное множество AA с элементами a1,a2,…,aka_1, a_2, \ldots, a_k, то есть kk элементов. Каждому элементу мы сопоставляем какой-то элемент множества BB: b1,b2,…,bkb_1, b_2, \ldots, b_k. Верхняя строчка таблицы — элементы множества AA, она зафиксирована, а в нижнюю строчку, значения функции ff, мы можем в каждую ячейку поставить любой элемент множества BB. Получается, что множество всех возможных таблиц значений нашей функции — это как раз BB, возведённое в степень kk, где kk — количество элементов AA.

Но нам важно не просто заиндексировать значения номерами «первый, второй, третий», а сказать, какому элементу AA какое значение соответствует. Именно в этом смысле мы пишем BAB^A — очень красиво и логично. А когда мы писали BkB^k, мы в некотором смысле рассматривали функцию из чисел от 11 до kk в множество BB: какой элемент будет первым — это значение функции от единицы, какой вторым — значение функции от двойки, какой третьим — значение функции от тройки, и так далее. Итак, BAB^A — это множество всех функций из AA в BB, и между ним и декартовыми произведениями есть естественное соответствие, по сути биекция, особенно наглядная для конечных множеств. Для бесконечных множеств возникает даже вопрос, существует ли такое множество. Оно существует: доказать это сложно, обычно это принимается как аксиома, и изучать это множество можно.

Давайте быстро разберём последние два вопроса про множества и перейдём к следующей теме лекции. Пусть AA и BB конечны, ∣A∣=a|A| = a, ∣B∣=b|B| = b. Чему равна мощность ∣A×B∣|A \times B|? Произведению a⋅ba \cdot b — логично: первый компонент пары можно взять aa способами, второй bb способами. А как вы думаете, чему равна мощность ∣BA∣|B^A|? Было бы глупо вводить такое обозначение, если бы ответ был aba^b — это было бы самое неудачное обозначение в мире. Конечно же, ∣BA∣=ba|B^A| = b^a. И это логично: вернёмся к картинке с таблицей, только вместо kk поставим aa, то есть верхняя строчка — это x1,x2,…,xax_1, x_2, \ldots, x_a. У нас aa ячеек, и каждую из них мы можем заполнить bb способами.

— Почему же свобода выбора остаётся во всех ячейках? Потому что мы не обязаны рассматривать инъекции: у любой функции разным аргументам может соответствовать одно и то же значение. Возьмём, например, функцию f(x)=x mod 3f(x) = x \bmod 3. Для нуля вы написали 00, для единицы 11, для двойки 22, а для тройки снова пишете 00 — ноль уже использован, но никаких проблем это не создаёт, такую функцию рассматривать можно. Эта функция неинъективна, она склеивает элементы: у нуля и тройки одинаковые значения.

Повторим ещё раз. Определяя функцию, мы брали некоторое подмножество A×BA \times B и накладывали на него ограничение: каждому элементу сопоставляется ровно один элемент. А можно эти ограничения не накладывать и рассмотреть просто произвольное подмножество A×BA \times B. Спрашивайте, пока стираю.

Посмотрим, что происходит с пустым множеством — рассмотрим функции из пустого множества и в пустое множество. Здесь довольно интересно. Начнём с A∅A^{\varnothing}: мы должны каждому элементу пустого множества сопоставить какое-то значение из множества AA. Но сопоставлять нечего и делать ничего не надо, а, как мы уже обсуждали, ничего не делать можно одним способом. Поэтому функция из пустого множества одна, и она ничего не делает: аргументов, которые можно подставить, нет, поэтому она никогда ничего не возвращает. Это абстрактная функция: она существует, но её нельзя потрогать и нельзя никак на неё посмотреть, потому что её нельзя запустить — ей нельзя передать никакой аргумент.

Обратите внимание, что это сильно отличается от функции без аргументов. Функция без аргументов — это функция из одноэлементного множества, грубо говоря из множества void\mathrm{void}. Ей можно передать аргументы единственным способом — ничего не передать. Такая функция — это просто константа, она всегда возвращает одно и то же значение, какое-то из элементов AA. Итак, множество A∅A^{\varnothing} имеет мощность ∣A∅∣=1|A^{\varnothing}| = 1 — это та эфемерная функция, которую нельзя вызвать: она отказывается принимать даже пустой аргумент, никакой элемент ей передать нельзя, и она такая одна. А множество AvoidA^{\mathrm{void}} имеет мощность ∣Avoid∣=∣A∣=a|A^{\mathrm{void}}| = |A| = a.

Теперь функции в пустое множество — с ними всё ещё хуже. Если рассмотреть ∅A\varnothing^A, то мы должны каждому элементу множества AA сопоставить какое-то значение из пустого множества. Сколькими способами это можно сделать? Здесь как раз ноль, а не один, потому что сопоставить нечего: если A≠∅A \neq \varnothing, то ∅A=∅\varnothing^A = \varnothing. А пустое множество в степени пустого множества подпадает под предыдущий случай: ∣∅∅∣=1|\varnothing^{\varnothing}| = 1, то есть 00=10^0 = 1. Действительно: если у вас пустое множество аргументов, то значения вы вернуть не можете, но поскольку вас никогда и не вызовут — передать вам аргумент невозможно, — это компенсирует вашу неспособность что-либо вернуть. Получается, что такая функция одна, и она никогда ничего не делает. Что же она делает? Она существует — одна-единственная. Очень грустно, потому что её существование абсолютно бессмысленно.

Бинарные отношения: эквивалентность и частичный порядок

Доска 8 — пять свойств бинарных отношений и их графовое изображение

Доска 9 — классы эквивалентности, фактор-множество и частичный порядок

Теперь отойдём от функций и поговорим про произвольные подмножества декартовых произведений, то есть про множества пар. Такое множество — множество пар элементов — называется отношением, или бинарным отношением: R⊂A×BR \subset A \times B. Отношение — это на самом деле центральный элемент математики, и смысл у него следующий. У нас есть различные связи между различными объектами; эти связи могут выполняться, а могут не выполняться. Например, рассмотрим числа: одно число может быть больше другого, одно число может делиться на другое, одно число может быть равно другому или не равно другому.

Можно рассмотреть и другие объекты. Например, студент и аудитория: какой-то студент может находиться в какой-то аудитории, а может не находиться. Или возьмём людей: один человек может быть родителем другого, один человек может быть другом другого, человек может находиться в одной комнате с другим. Есть много таких естественных понятий, в которых фигурируют два объекта — однородных или разнородных, — и между ними есть какая-то связь. Математическое обобщение этой концепции и называется отношением. Мы просто аксиоматически говорим: мы не пытаемся придумать, какие описания являются валидными отношениями, а какие нет, — мы объявляем отношением любое множество пар.

Запишу несколько примеров, чтобы они не подвисли. Например, A=B=NA = B = \mathbb{N}, а отношение R={(a,b)∣a<b}R = \{(a,b) \mid a < b\}. Когда вы так пишете, здесь, конечно, куча синтаксического мусора: фигурные скобки, вертикальная черта, круглые скобки, запятые и прочее. Так обычно не делают, а просто пишут R = <R\ =\ < — отношение «меньше». Точно так же можно рассмотреть отношение ⩽\leqslant.

Дальше можно рассмотреть отношение «aa делится на bb», то есть «aa кратно bb»; оно обозначается тремя вертикальными точками: a⋮ba \vdots b. Например, 6⋮26 \vdots 2 — шесть находится в отношении делимости с двойкой, а 6̸⋮56 \mathrel{\not\vdots} 5 — на пять шесть не делится.

Можно рассмотреть пример с разными множествами: AA — люди, BB — собаки, и R={(a,b)∣a — хозяин b}R = \{(a,b) \mid a \text{ — хозяин } b\}. Это, конечно, не абсолютно точно определённое отношение: если, допустим, у вас с братом есть собака, кто из вас находится в этом отношении? Может быть, оба. Обратите внимание: здесь нет, как у функции, требования, чтобы каждому элементу соответствовал ровно один и чтобы в другую сторону никто не повторялся, — может быть несколько. Например, 6⋮26 \vdots 2 и 6⋮36 \vdots 3; и число 200⋮2200 \vdots 2 — тоже никакой проблемы нет. И слева, и справа каждый элемент теперь может фигурировать сколько угодно раз, в отличие от функции.

Пока понятие отношения сформулировано очень абстрактно: отношением может быть что угодно, любое множество пар. Среди отношений выделяют некоторые интересные классы. Классически рассматривают пять классов отношений в ситуации, когда множества AA и BB совпадают — такую ситуацию рассматривают достаточно часто. Разберём эти пять классов отношений и примеры к ним.

Первый класс — рефлексивные отношения. Рефлексивное отношение — это отношение, в котором каждый элемент находится в этом отношении с собой: ∀a  a R a\forall a\ \ a\,R\,a. Посмотрим на наши отношения. Является ли рефлексивным отношение «меньше»? Нет: например, 22 не меньше 22. А «меньше либо равно»? Является. А строго «меньше» — нет. Является ли рефлексивным отношение делимости? Скорее всего, да. Здесь есть вопрос о том, что мы включаем в наше множество: на натуральных числах всё точно хорошо, число само на себя делится. Если же мы рассмотрим целые числа, то возникает вопрос с нулём: делится ли 00 на 00? На нуль вроде делить нельзя, но, может быть, сам нуль можно. Это тонкий момент; по модулю этого вопроса отношение делимости рефлексивно.

На отношениях между разными множествами — люди и собаки — понятие рефлексивности вообще не определено, потому что элемент нельзя подставить и как первый, и как второй компонент отношения. Если мы возьмём собаку, она не может быть хозяином, то есть не может выступать первым компонентом. Если возьмём человека, он не может быть животным, которое является собственностью, поэтому его нельзя подставить как второй элемент. Поэтому рефлексивность определена только для бинарных отношений на одном множестве, когда оба компонента берутся из одного и того же множества. Если же рассмотреть примеры не из математики, а из жизни — например, дружбу, — то вопрос, рефлексивно отношение дружбы или нет, философский: это вопрос определения, сам себе человек друг или нет. В таких случаях обычно доопределяют: говорят, считается или не считается.

Если у нас есть некоторое отношение, можно рассмотреть его рефлексивное замыкание RC(R)RC(R) — reflexive closure. Это когда мы пополняем отношение всеми парами вида (a,a)(a,a). Например, если мы возьмём рефлексивное замыкание отношения дружбы, то мы тем самым просто объявляем, что каждый человек обязательно друг себе самому.

Если есть рефлексивные отношения, можно рассмотреть и наоборот — антирефлексивные. Антирефлексивное отношение — это такое, что ∀a  aR̸a\forall a\ \ a \mathrel{\not R} a. Рассмотрим примеры. Является ли «меньше» антирефлексивным отношением? Да. А «меньше либо равно»? Нет. Делимость антирефлексивной не является. «Быть другом» — опять вопрос философский; мы можем, наоборот, вычесть диагональ из отношения, то есть сказать по определению, что друг человека — это обязательно другой человек, и тогда отношение будет антирефлексивным. На людях можно рассмотреть и другие естественные антирефлексивные отношения, например «быть отцом» или «быть родителем»: оно антирефлексивно, поскольку человек сам себе родителем не является. А вот если взять «быть предком», то здесь мы можем на своё усмотрение считать отношение рефлексивным или антирефлексивным.

При этом отношение может быть ни тем, ни другим: некоторые элементы могут находиться в нём сами с собой, а некоторые нет. Например, рассмотрим отношение «правый глаз человека XX имеет тот же цвет, что левый глаз человека YY». Это отношение, в котором некоторые пары людей могут находиться; человек сам с собой обычно в нём находится, у него оба глаза обычно одинаковые, но бывает генетическая особенность: у некоторых людей глаза разного цвета. Тогда такие люди сами с собой в этом отношении не находятся. Соответственно, может так случиться, что отношение не является ни рефлексивным, ни антирефлексивным.

— Хотел уточнить про рефлексивное замыкание: то есть мы…

— Рефлексивное замыкание — это новое отношение, которое получается из отношения RR добавлением всех пар одинаковых элементов. RR здесь аргумент: мы взяли reflexive closure от RR.

Следующий класс — симметричные отношения. Это центр изучения романтической литературы, но и математическая литература частично им посвящена. Симметричность означает, что если aa находится в отношении RR с bb, то и bb находится в отношении RR с aa: a R b⇒b R aa\,R\,b \Rightarrow b\,R\,a. Является ли симметричным отношение «меньше»? Не является. А отношение «меньше или равно» симметричным является? Тоже не является: 2⩽32 \leqslant 3, а 3⩽23 \leqslant 2 — нет. Делимость является симметричным отношением? Не является. Дружба — это философский вопрос, оставим его писателям. «Быть предком» симметричным не является. А «быть родственником» — допустим, будем считать, что является. Или, например, сравнимость по модулю три на числах, a≡b(mod3)a \equiv b \pmod 3, — это пример симметричного отношения. Или «в сумме дают пять»: тоже пример симметричного отношения на числах, которое при этом, в отличие от предыдущего, уже не рефлексивно.

Теперь следующее свойство — антисимметричность. Это, разумеется, не отношение, а класс отношений, и он определён только для отношений на одном множестве; к отношениям между разными множествами это понятие не применимо. Антисимметричность означает, что связь может быть только в одном направлении. Но здесь возникает вопрос: а когда aa находится в отношении само с собой, можно так или нет? Поскольку вопросами связи элемента с самим собой занимается рефлексивность, чтобы не перекладывать его на симметричность, давайте этот случай просто игнорировать: антисимметричность требуется во всех случаях, кроме диагонали. А именно: если a R ba\,R\,b и a≠ba \neq b, то bR̸ab \mathrel{\not R} a. Логически то же самое можно переписать иначе: если a R ba\,R\,b и b R ab\,R\,a, то это возможно в единственном случае — когда a=ba = b, но обратное не требуется. То есть если a=ba = b, то связь может быть, а может и не быть: пара (a,a)(a,a) может как присутствовать, так и отсутствовать в антисимметричном отношении.

— А почему мы не можем использовать здесь разные множества?

— Потому что мы не сможем тогда поменять элементы местами.

— А если у них будет какое-то общее свойство?

— Непонятно. Ещё раз: если мы берём разные множества, то в A×BA \times B первый элемент обязательно из AA, второй — из BB. Если AA и BB не равны, то поменять их местами мы не можем: некоторые элементы не сойдутся, так нельзя. Если у вас функция в C++ принимает первым аргументом char, а вторым — std::string, то вы не можете передать их наоборот.

— А если принимать первым аргументом какой-нибудь объект с полем a, а вторым аргументом объект другого класса с полем a?

— Всё равно вы не можете передать их наоборот. Тогда вы можете вместо этого сделать множество DD элементов, у которых есть поле a. Правильно подсказывают.

Итак, разберём антисимметричность на примерах. Является ли «меньше» антисимметричным? Да. А «меньше либо равно» является антисимметричным? Почему? Тоже является. Мы специально придумали этот финт с равными элементами, чтобы рефлексивность не запрещать и не требовать. Оба отношения антисимметричны. Является ли антисимметричной делимость? Само на себя делить можно, но вот если элементы не равны, могут ли они оба делиться друг на друга? Это зависит от множества элементов. Если взять натуральные числа, то отношение делимости антисимметрично. А если взять целые, то антисимметричным оно не будет: например, 22 и −2-2 оба делятся друг на друга и при этом не равны. Отношения на людях — «быть родителем» или «быть предком» — антисимметричны: не могут два человека быть друг другу родителями или предками.

Пятое свойство — транзитивность. Транзитивность утверждает следующее: если aa находится в отношении RR с bb, а bb находится в отношении RR с cc, то из этого следует, что aa находится в отношении RR с cc: a R b, b R c⇒a R ca\,R\,b,\ b\,R\,c \Rightarrow a\,R\,c. Если это свойство выполнено, отношение RR называется транзитивным.

Рассмотрим примеры. Является ли «меньше» транзитивным? Является: если a<ba < b и b<cb < c, то логично, что a<ca < c, — согласны? «Меньше или равно» транзитивно. Делимость является транзитивной? Является. А сравнимость по модулю три является транзитивной? Здесь ситуация другая, мы вроде переключились совсем на другое, но тоже является: если aa и bb имеют одинаковый остаток по модулю три, а bb и cc имеют одинаковый остаток по модулю три, то этот общий остаток, который есть у bb, есть и у aa, и у cc, поэтому отношение транзитивно.

А придумайте мне нетранзитивное отношение. Вот «быть отцом» является транзитивным отношением? Не является: если Иван — отец Петра, а Пётр — отец Сергея, то Иван Сергею уже не отец, а дед.

— Просто родственники?

— Тут вопрос, на самом деле не обязательно. Давайте лучше считать нетранзитивным отношением дружбу: Петя может дружить с Васей, Вася может дружить с Ирой, а Петя с Ирой может быть вообще не знаком. Ещё пример нетранзитивного отношения — «не равно». Смотрите: 1≠21 \neq 2, 2≠12 \neq 1; мы ведь не обязаны брать в качестве a,b,ca, b, c все разные элементы, можно брать одинаковые. Но при этом 1=11 = 1. Значит, неравенство транзитивным отношением не является.

Время подходит к концу, но мне придётся вас задержать на десять минут, потому что иначе вы не сможете решить домашку. У этих пяти свойств есть некоторые комбинации, которые имеют особое значение. Первая комбинация — это 1+3+51 + 3 + 5: рефлексивное, симметричное, транзитивное отношение. Такое отношение называется отношением эквивалентности. Какие из тех отношений, что мы рассматривали, были отношениями эквивалентности? Просто равенство; равенство остатков по некоторому модулю; или, если вспомнить, «находиться в одной комнате». Приведу ещё пример из информатики: в неориентированном графе отношение «две вершины связаны путём» — это отношение эквивалентности. Если от aa до bb можно дойти и от bb до cc можно дойти, то и от aa до cc тоже можно дойти.

Чем ценны отношения эквивалентности? Про них есть следующая теорема. Доказывать мы её не будем — не потому, что её сложно доказать, а потому, что не очень понятно, что именно там доказывать: у нас пока нет инструментов, чтобы это понять. Она очевидна, но тем не менее важна. Теорема: если RR — отношение эквивалентности на XX, то элементы XX можно разбить на так называемые классы эквивалентности относительно отношения RR, причём элементы в одном классе эквивалентны друг другу: если aa и bb лежат в одном классе, то a R ba\,R\,b; а если aa и bb лежат в различных классах, то aR̸ba \mathrel{\not R} b.

Итак, рефлексивные, симметричные, транзитивные отношения — это отношения эквивалентности, и если на множестве введено отношение эквивалентности, то его элементы можно разбить на классы. Эти классы называются классами эквивалентности, а множество классов эквивалентности обозначается X/RX/R — мы как бы разделили элементы XX по отношению RR; здесь XX — это множество, на котором задано отношение. Например, если мы возьмём множество натуральных чисел со сравнимостью по модулю три, какие получатся классы эквивалентности и сколько их будет? Их будет три. В первый войдут числа 1,4,7,101, 4, 7, 10 и так далее — те, которые дают остаток 11 по модулю три. Внутри этого класса все пары эквивалентны, они дают одинаковый остаток 11, а снаружи они не эквивалентны. Во второй войдут 2,5,8,112, 5, 8, 11 и так далее — они дают остаток 22 по модулю три. А в третий класс войдут 3,6,9,123, 6, 9, 12 и так далее — нуля у нас как раз нет. Внутри каждого класса элементы эквивалентны между собой.

Почему это можно сделать? Строго доказать тяжело, потому что, как я уже сказал, инструментов такого низкого уровня, на уровне аксиом, у нас просто нет. Но по смыслу посмотрим, почему именно нужно отношение эквивалентности — почему элементы внутри одного класса эквивалентны, а элементы из разных классов не эквивалентны. Если бы не было рефлексивности, то элемент не лежал бы в одном классе сам с собой, а это бред. Если бы не было симметричности — то «aa и bb в одном классе» само по себе отношение симметричное. Транзитивность тоже нужна: если aa и bb находятся в отношении RR, они лежат в одном классе, и если bb и cc в одном классе, значит, aa и cc тоже должны лежать в одном. А если в разных — то в разных.

Давайте рассмотрим примеры. Как устроены классы эквивалентности для простого равенства? Каждое число просто лежит в своём классе. Отношение «студенты находятся в одной комнате» — как будет выглядеть класс? Каждый класс — это своя комната. «В графе вершины связаны путём» — что будет классами эквивалентности? Компоненты связности. Вижу, вы всё поняли.

Теперь — то, что я обещал примерно час назад: мы наконец сможем поговорить про мощность множества. Равномощность множеств — это отношение эквивалентности. Рефлексивность очевидна: множество само с собой равномощно, между ними можно построить биекцию, сопоставив каждый элемент самому себе. Симметричность не абсолютно очевидна, но в принципе легко обосновывается: если мы элементу aa сопоставляем элемент f(a)f(a), то, поскольку у нас биекция, все они различны, и поэтому мы можем сопоставить в обратную сторону g(f(a))=ag(f(a)) = a, и это тоже будет функция. Значит, отношение равномощности симметрично. Транзитивность, думаю, тоже более-менее очевидна: композиция двух биекций — биекция.

Раз это отношение эквивалентности, можно рассматривать его классы эквивалентности. Классы эквивалентности этого отношения называются мощностями множеств. Соответственно, есть конечные мощности 0,1,2,3,…0, 1, 2, 3, \ldots — это количество элементов множества; это классы эквивалентности конечных множеств по равномощности: мощность 00, мощность 11, мощность 22 и так далее. Бесконечные множества разбиваются на большое число различных классов: вообще говоря, они не все равномощны. Почему я сказал «почти»? Потому что на самом деле я вас сейчас немного обманываю: так, как я сказал, делать нельзя. Нельзя применить эту теорему к семейству всех множеств, потому что, как мы помним из парадокса Рассела, все множества нельзя рассматривать как множество. Поэтому, вообще говоря, непонятно, можно ли вообще все множества разбивать на классы эквивалентности. Это можно дополнить так, чтобы стало можно, но сейчас мы этого делать не будем.

Теперь возьмём другую комбинацию — 1+4+51 + 4 + 5, то есть вместо симметричности возьмём антисимметричность. Таких отношений у нас как раз было много примеров: «меньше или равно», делимость, «быть предком». У всех этих отношений есть общее свойство: они рефлексивны — каждый элемент находится в отношении сам с собой; они антисимметричны — между неравными элементами связь может быть только в одну сторону; и они транзитивны. Такие отношения называются частичными порядками. Частичный порядок — это отношение рефлексивное, антисимметричное и транзитивное. Множество, на котором введён частичный порядок, называется частично упорядоченным множеством, кратко — ч.у.м. По-английски это называется partially ordered set, или poset. И если по-русски «ч.у.м.» всё-таки пишут с точечками, раскрывая как «частично упорядоченное множество», то по-английски слово poset уже вошло в лексикон как единое слово. Это множество, на котором введён частичный порядок.

Что ещё нам нужно быстро сказать для домашки? Определения и свойства уже есть, всё остальное мы распишем прямо в домашке. Скажу вам последнее перед домашкой. Когда вы хотите задать отношение — а что такое отношение? множество пар, правильно? — как его можно задать? Можно нарисовать просто все эти пары, но это не очень удобно. Поэтому обычно, когда рисуют отношение, используют следующую визуализацию: элементы множества, на котором оно задано, изображают кружками, то есть используют ориентированный граф, а если два элемента находятся в отношении, то между ними рисуется стрелочка — вот aa и bb. Давайте посмотрим, как будут выглядеть эти графы для наших пяти классов, и на этом лекцию сегодня закончим.

Что можно сказать про граф рефлексивного отношения? У каждой вершины обязательно есть петля. А у антирефлексивного? Петель нет вообще, ни одной. Симметричные: условно говоря, можно сказать «неориентированные», но, вообще говоря, это не совсем правда, мы не имеем права называть их неориентированными. Симметричность означает, что между каждой парой обязательно есть рёбра и туда, и обратно, при этом петли могут как быть, так и не быть. Это действительно можно визуализировать как неориентированный граф: соединять не двумя стрелочками навстречу, а просто линией. А антисимметричные? Условно говоря, нет кратных рёбер, даже встречных: между любой парой ребро может идти только в одну сторону, в обратную — нет.

И наконец транзитивность. Если у нас между двумя вершинами есть путь из рёбер, то есть и ребро напрямую. Если развивать эту идею дальше, граф не обязательно получится полным — вот вам пример неполного. Понятие компоненты связности для ориентированного графа не очень хорошо определено. Такой граф называется транзитивным графом. На языке графов транзитивность переформулируется так: если есть путь, то есть и ребро. Это легко развить по индукции: если есть путь длины 22, то ребро есть; если есть путь длины 33, то берём его префикс длины 22 — ребро есть, теперь путь стал длины два, значит, ребро снова есть, и так далее. Легко доказать по индукции, что с точки зрения теории графов транзитивность переформулируется как «если есть путь, то есть ребро».

На этом теперь остановимся.