Множества, отношения и функции

Язык курса

Следующий урок определяет натуральные числа с помощью функции следования, которая инъективна и не принимает значения $1$. Следующий раздел строит целые и рациональные числа как классы отношения эквивалентности; урок по комбинаторике определяет число элементов с помощью биекций; порядок натуральных чисел есть отношение порядка; а третий раздел составляет композиции вещественных функций и обращает их. Все эти слова принадлежат одному языку, который следует установить прежде, чем им пользоваться, вместе с первыми теоремами, на которые курс будет опираться в дальнейшем.

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

Что принимается

Множество есть совокупность объектов, его элементов; пишут $a \in A$, чтобы сказать, что $a$ принадлежит $A$, и $a \notin A$, чтобы это отрицать. Множество и принадлежность не определяются: это первичные понятия, как $1$ и следование в арифметике. Однако не всякое свойство задаёт множество. Если бы существовало множество $R$ всех множеств, которые не принадлежат самим себе, вопрос о том, принадлежит ли $R$ множеству $R$, не имел бы ответа, потому что по определению $R$ выполнялось бы $R \in R \leftrightarrow R \notin R$. Это противоречие, открытое Расселом в 1901 году, вынуждает ограничить образование множеств: свойство лишь выделяет элементы из уже данного множества.

Факт, принимаемый без доказательства (правила наивной теории множеств). Без доказательства принимаются те правила наивной теории множеств, которыми пользуется этот урок: два множества с одними и теми же элементами равны; из данного множества $A$ и свойства $P$ образуется множество $\{ x \in A : P(x) \}$ тех элементов $A$, которые им обладают; и существуют пустое множество, множество $\{a, b\}$, единственными элементами которого являются $a$ и $b$, объединение элементов множества множеств и множество подмножеств данного множества. Существование множества со свойствами множества натуральных чисел принимается в следующем уроке.

Эти правила входят в аксиомы Цермело и Френкеля, изучение которых относится к теории множеств и выходит за рамки этого курса; поэтому они принимаются и явно перечисляются, чтобы было точно известно, что используется.

Логика кванторов

Доказательства соединяют высказывания связками $\neg$, $\wedge$, $\vee$, $\rightarrow$ и $\leftrightarrow$, законы которых изучаются в дополнительном курсе Математическая логика I: логика высказываний, начиная с её языка; здесь достаточно напомнить, что импликация $p \rightarrow q$ ложна лишь тогда, когда $p$ истинно, а $q$ ложно, что она равносильна своей контрапозиции $\neg q \rightarrow \neg p$ и что законы де Моргана строят отрицание конъюнкции и дизъюнкции:

Чтобы говорить о множествах, нужны, кроме того, высказывания обо всех элементах или о некотором из них. Если $P(x)$ есть свойство элементов $A$, то высказывание $(\forall x \in A)\,P(x)$, которое читается «для всякого $x$ из $A$ верно $P(x)$», утверждает, что этим свойством обладают все элементы $A$; высказывание $(\exists x \in A)\,P(x)$, «существует $x$ из $A$, такой что $P(x)$», утверждает, что им обладает хотя бы один элемент; а $(\exists! x \in A)\,P(x)$ утверждает, что им обладает ровно один элемент. Знаки $\forall$ и $\exists$ называются кванторами, всеобщности и существования.

Факт, принимаемый без доказательства (отрицание кванторов). Отрицать, что все элементы обладают свойством, значит утверждать, что некоторый элемент им не обладает, а отрицать, что некоторый элемент им обладает, значит утверждать, что им не обладает ни один:

Эти правила, принадлежащие логике первого порядка, принимаются; они обобщают законы де Моргана, потому что если $A = \{a, b\}$, то высказывание с квантором всеобщности есть $P(a) \wedge P(b)$, а высказывание с квантором существования есть $P(a) \vee P(b)$. Порядок кванторов важен: высказывание $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ говорит, что для всякого натурального числа есть другое, большее его, и оно истинно; высказывание $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ говорит, что есть натуральное число, большее всех, в том числе большее самого себя, и оно ложно.

Логическая форма высказывания диктует способ его доказательства. Этот урок пользуется следующими стратегиями; их логическое обоснование изучается в уроке о приёмах вывода.

• Чтобы доказать $(\forall x \in A)\,P(x)$, берут произвольный элемент $x$ из $A$, не предполагая о нём ничего, кроме его принадлежности $A$, и доказывают $P(x)$.
• Чтобы доказать $(\exists x \in A)\,P(x)$, предъявляют конкретный элемент из $A$, обладающий свойством $P$; чтобы опровергнуть $(\forall x \in A)\,P(x)$, достаточно контрпримера, элемента, который этим свойством не обладает.
• Чтобы доказать $p \rightarrow q$, предполагают $p$ и выводят $q$; или доказывают контрапозицию $\neg q \rightarrow \neg p$; или предполагают $p \wedge \neg q$ и приходят к противоречию.
• Чтобы доказать $p \leftrightarrow q$, доказывают обе импликации $p \rightarrow q$ и $q \rightarrow p$.

Множества

Принадлежность, равенство и включение

Множество задаётся перечислением, когда его элементы перечисляются в фигурных скобках, как $\{1, 2, 3\}$, или описанием, с помощью свойства, как $\{ n \in \mathbb{N} : n \leq 3 \}$, и это одно и то же множество. Правило экстенсиональности говорит, что множество определяется своими элементами:

Отсюда следует, что при задании перечислением не важны ни порядок, ни повторения: $\{1, 2, 2\}$ и $\{2, 1\}$ есть одно и то же множество, потому что у них одни и те же элементы. Следует также, что существует лишь одно множество без элементов, пустое множество $\emptyset$: у двух множеств без элементов одни и те же элементы, а именно никаких.

Определение (включение). Множество $A$ содержится в множестве $B$, или является подмножеством $B$, если всякий элемент $A$ является элементом $B$:

Если, кроме того, $A \neq B$, то говорят, что $A$ есть собственное подмножество $B$.

Пустое множество содержится во всяком множестве $A$, потому что у импликации $x \in \emptyset \rightarrow x \in A$ посылка всегда ложна, и поэтому она истинна. Следует различать принадлежность и включение: $1 \in \{1, 2\}$ и $\{1\} \subseteq \{1, 2\}$ истинны, тогда как $\{1\} \in \{1, 2\}$ ложно, потому что единственные элементы $\{1, 2\}$ суть $1$ и $2$, а множество $\{1\}$ не равно ни одному из них: $\{1\} \neq 1$, потому что множество, единственным элементом которого является $1$, не совпадает с $1$, и $\{1\} \neq 2$.

Объединение, пересечение и разность

Определение (операции над множествами). Объединение $A$ и $B$ есть множество элементов, принадлежащих хотя бы одному из них; пересечение есть множество элементов, принадлежащих обоим; а разность $A \setminus B$ есть множество элементов, принадлежащих $A$ и не принадлежащих $B$:

Если $B \subseteq A$, то разность $A \setminus B$ называется дополнением $B$ до $A$. Два множества называются непересекающимися, если их пересечение пусто.

Каждая операция переводит связку: объединение есть дизъюнкция; пересечение есть конъюнкция; разность есть конъюнкция с отрицанием. Если это так, то каждый логический закон порождает закон для множеств: объединение и пересечение коммутативны, ассоциативны и дистрибутивны одно относительно другого, потому что таковы связки, и все эти законы доказываются так же, как следующая теорема. Дополнение всегда берётся до некоторого объемлющего множества, потому что множество всего, что не лежит в $B$, воспроизвело бы парадокс Рассела.

Булеан

Подмножества множества сами образуют множество, существование которого было принято в начале. Булеан множества $A$, который обозначается $\mathcal{P}(A)$, есть множество, элементами которого являются подмножества $A$:

Например, булеан множества $\{1, 2, 3\}$ имеет восемь элементов: пустое множество, три одноэлементных множества, три двухэлементных и само $\{1, 2, 3\}$.

Для всякого множества $A$ пустое множество и само $A$ являются элементами $\mathcal{P}(A)$, и для каждого $a$ из $A$ выполняется $\{a\} \in \mathcal{P}(A)$, тогда как $a$, вообще говоря, не является элементом $\mathcal{P}(A)$. В уроке по комбинаторике будет доказано, что множество из $n$ элементов имеет $2^n$ подмножеств.

Упорядоченные пары и декартово произведение

Точка плоскости, дробь или ещё не выполненное вычитание описываются двумя объектами в определённом порядке: пара $(3, 5)$ не есть пара $(5, 3)$. Множество $\{3, 5\}$ не годится для её представления, потому что оно равно $\{5, 3\}$. От упорядоченной пары требуется лишь её характеристическое свойство: две пары равны тогда и только тогда, когда у них одна и та же первая компонента и одна и та же вторая компонента. Куратовский заметил в 1921 году, что для построения объекта с таким свойством достаточно понятия множества.

Определение (упорядоченная пара). Упорядоченная пара с первой компонентой $a$ и второй компонентой $b$ есть множество

После того как характеристическое свойство доказано, о построении Куратовского можно забыть: всё, что курс говорит о парах, выводится из этого свойства.

Определение (декартово произведение). Декартово произведение $A$ и $B$ есть множество пар, первая компонента которых принадлежит $A$, а вторая компонента принадлежит $B$:

Запись $\{ (a, b) : a \in A \wedge b \in B \}$ сама по себе не является ни одним из принятых правил, которые позволяют лишь выделять элементы из уже образованного множества. Однако такое множество существует: если $a \in A$ и $b \in B$, то множества $\{a\}$ и $\{a, b\}$ содержатся в $A \cup B$ и, следовательно, являются элементами $\mathcal{P}(A \cup B)$; отсюда следует, что пара $(a, b) = \{ \{a\}, \{a, b\} \}$ содержится в $\mathcal{P}(A \cup B)$, то есть является элементом $\mathcal{P}(\mathcal{P}(A \cup B))$. Следовательно, декартово произведение образуется выделением внутри этого множества, которое существует по принятым правилам: $A \cup B$ есть объединение элементов $\{A, B\}$, и булеан берётся дважды.

Название напоминает о Декарте: плоскость аналитической геометрии есть $\mathbb{R} \times \mathbb{R}$. Произведение не коммутативно: $\{1\} \times \{2\}$ содержит лишь $(1, 2)$, а $\{2\} \times \{1\}$ лишь $(2, 1)$, которая отлична от первой по характеристическому свойству.

Отношения

Сказать, что $2$ делит $6$, что $3$ меньше $5$ или что две даты приходятся на один и тот же день недели, значит утверждать, что некоторые пары объектов находятся в отношении. Если это так, то отношение определяется парами, которые оно связывает, и его можно определить как множество пар.

Определение (отношение). Отношение из $A$ в $B$ есть подмножество $R$ произведения $A \times B$; отношение на $A$ есть отношение из $A$ в $A$. Если $(a, b) \in R$, то говорят, что $a$ связан с $b$ отношением $R$.

Например, отношение «меньше или равно» на $\{1, 2, 3\}$ есть множество пар $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$. Для часто используемых отношений между членами пишут знак, как $a \leq b$ или $a \mid b$, вместо $(a, b) \in R$. Четыре свойства отношения на множестве встречаются на протяжении всего курса.

Определение (свойства отношений). Отношение $R$ на $A$ называется рефлексивным, симметричным, антисимметричным или транзитивным, если оно удовлетворяет соответственно следующим условиям.

• Оно рефлексивно, если каждый элемент находится в отношении с самим собой: $(\forall a \in A)\,((a, a) \in R)$;
• Оно симметрично, если из того, что $a$ находится в отношении с $b$, следует, что $b$ находится в отношении с $a$: $(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$;
• Оно антисимметрично, если два элемента, находящиеся в отношении в обе стороны, равны: $(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$;
• Оно транзитивно, если из того, что $a$ находится в отношении с $b$, а $b$ с $c$, следует, что $a$ находится в отношении с $c$: $(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$.

На сетке $A \times A$ отношение есть множество точек. Оно рефлексивно, когда содержит всю диагональ, то есть пары $(a, a)$; симметрично, когда его изображение симметрично относительно диагонали; и антисимметрично, когда ни у одной точки вне диагонали симметричная ей точка не входит в отношение. Антисимметричное не означает «несимметричное»: равенство является и тем и другим, а задача для самостоятельного решения 1 просит найти отношение, не являющееся ни тем, ни другим.

Отношения эквивалентности

Отношение «иметь одинаковую чётность» ведёт себя как частичное равенство: оно отождествляет числа, совпадающие в одном отношении, в чётности, и забывает об остальных. Три свойства, благодаря которым оно так себя ведёт, получают название.

Определение (отношение эквивалентности). Отношение на $A$ называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно. Тогда пишут $a \sim b$ и говорят, что $a$ эквивалентен $b$. Класс элемента $a$ есть множество элементов, эквивалентных $a$, и каждый из них есть представитель этого класса:

Множество всех классов называется фактормножеством и обозначается $A/{\sim}$.

Отношениями эквивалентности являются равенство, классы которого содержат по одному элементу; одинаковая чётность, с двумя классами; одинаковый остаток при делении на $3$, с тремя; и совпадение дня недели, с семью, чему посвящена решённая задача 3. Вообще, если $g$ есть функция, определённая на $A$, то отношение $g(x) = g(y)$ наследует от равенства все три свойства, а решённая задача 5 показывает, что всякая эквивалентность имеет такой вид.

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

Определение (разбиение). Разбиение множества $A$ есть множество подмножеств $A$, называемых блоками, которые непусты, попарно не пересекаются и в объединении дают $A$; равносильно, каждый элемент $A$ принадлежит ровно одному блоку.

Следовательно, задать эквивалентность на $A$ и задать разбиение $A$ есть два способа сказать одно и то же; решённая задача 4 пользуется этим, чтобы подсчитать эквивалентности. Фактормножество есть разбиение, рассматриваемое как новое множество: при переходе от $A$ к $A/{\sim}$ эквивалентные элементы сливаются в один.

Точно так же в уроке о рациональных числах две дроби $(p, q)$ и $(r, s)$ эквивалентны, если $ps = qr$, и рациональное число есть класс; а в уроке о сравнениях вычеты по модулю $n$ суть классы эквивалентности на целых числах.

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

Делимость из предыдущего примера не симметрична, а антисимметрична: вместо того чтобы отождествлять элементы, она их упорядочивает. Отношения такого рода получают собственное название.

Определение (порядок). Отношение на $A$ называется отношением порядка, или частичным порядком, если оно рефлексивно, антисимметрично и транзитивно; тогда пишут $a \preceq b$ и говорят, что $a$ предшествует $b$. Порядок называется линейным, если любые два элемента сравнимы, то есть если для любых $a$ и $b$ выполняется $a \preceq b$ или $b \preceq a$.

Порядками являются отношение $\leq$ на натуральных числах, которое линейно по трихотомии, доказанной в уроке об операциях с натуральными числами; включение, по теореме о его свойствах, которое не линейно, потому что $\{1\}$ и $\{2\}$ не сравнимы; и делимость на натуральных числах, антисимметричность которой доказывается в уроке о делимости, которая не линейна, потому что неверно ни $2 \mid 3$, ни $3 \mid 2$. Конечный порядок изображают диаграммой Хассе: по точке на элемент, причём $b$ располагается выше $a$, когда $a$ предшествует $b$, и отрезок проводится, когда между ними нет никакого другого элемента; транзитивность позволяет опустить остальные отрезки.

Определение (границы и крайние элементы). Пусть $\preceq$ есть порядок на $A$, а $X$ есть подмножество $A$. Границы и крайние элементы $X$ определяются следующим образом.

• Элемент $c$ из $A$ есть нижняя граница $X$, если он предшествует всем элементам $X$, и верхняя граница, если все элементы $X$ предшествуют ему.
• Наименьший элемент $X$ есть нижняя граница $X$, принадлежащая $X$, а наибольший элемент есть верхняя граница, принадлежащая $X$.
• Элемент $m$ из $X$ называется минимальным, если ему не предшествует ни один отличный от него элемент $X$, и максимальным, если сам он не предшествует ни одному отличному от него элементу $X$.
• Точная нижняя грань $X$ есть наибольший элемент множества его нижних границ, а точная верхняя грань есть наименьший элемент множества его верхних границ, когда они существуют.