Лекция 2. Отображения, натуральный ряд и индукция, мощность множеств

Лекция 1 ввела отображения, образ и прообраз. Здесь отображения классифицируются: инъекции, сюръекции, биекции, композиция и обратное отображение. Затем натуральные числа строятся аксиоматически — через функцию следования $S$ и пять аксиом Пеано, — и из аксиомы индукции выводятся метод математической индукции и вполне упорядоченность $\mathbb N$. Индукцией доказываются неравенство Бернулли и бином Ньютона. Последний раздел — мощность множеств: биекции позволяют сравнивать по размеру даже бесконечные множества.

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

1.1. Инъекция, сюръекция, биекция

Определение 1. Отображение $f\colon A\to B$ называется инъективным (инъекцией, мономорфизмом), если оно переводит разные элементы в разные: $\forall x_1,x_2\in A:\quad x_1\ne x_2\ \Rightarrow\ f(x_1)\ne f(x_2).$ Эквивалентная форма (контрапозиция): $f(x_1)=f(x_2)\ \Rightarrow\ x_1=x_2.$

На практике инъективность проверяют именно во второй форме: предполагаем $f(x_1)=f(x_2)$ и выводим $x_1=x_2$. Например, для $f(x)=2x+1$ из $2x_1+1=2x_2+1$ сразу следует $x_1=x_2$. Чтобы опровергнуть инъективность, достаточно одной пары: $f(x)=x^2$ на $\mathbb R$ не инъективно, так как $f(1)=f(-1)$.

Определение 2. $f\colon A\to B$ называется сюръективным (сюръекцией, эпиморфизмом, отображением «на»), если у каждого элемента $B$ есть прообраз: $\forall y\in B\ \ \exists x\in A:\ f(x)=y.$ Эквивалентно: $f(A)=B$ (образ совпадает со всей областью прибытия). Чтобы доказать сюръективность, для произвольного $y\in B$ предъявляют $x$: для $f\colon\mathbb R\to[0;+\infty)$, $f(x)=x^2$ годится $x=\sqrt y$.

Определение 3. $f$ называется биективным (биекцией, взаимно однозначным соответствием), если оно одновременно инъективно и сюръективно. Иначе говоря, у каждого $y\in B$ ровно один прообраз: $\forall y\in B\ \ \exists!\,x\in A:\ f(x)=y.$

Примеры с одной и той же формулой $f(x)=x^2$:

Инъективность и сюръективность зависят не только от формулы, но и от того, какие именно $A$ и $B$ выбраны. Образ $f(A)$ может быть меньше области прибытия $B$ — поэтому сюръективность и выделяют в отдельное свойство.

1.2. Композиция отображений

Определение 4. Пусть $f\colon X\to Y$ и $g\colon Y\to Z$ — значения $f$ лежат там, где определено $g$. Композицией $f$ и $g$ называется отображение $g\circ f\colon X\to Z,\qquad (g\circ f)(x)=g\big(f(x)\big).$

Читается «$g$ после $f$»: первым применяется то отображение, что записано справа.

Теорема 1 (ассоциативность композиции). Если $f\colon X\to Y$, $g\colon Y\to Z$, $h\colon Z\to W$, то $h\circ(g\circ f)=(h\circ g)\circ f.$

Упражнение 1 (с лекции). Доказать ассоциативность композиции.

Подсказка: два отображения с общей областью определения и общей областью прибытия равны, если равны их значения в каждой точке. Посчитайте обе части в произвольной точке $x$.

Решение упражнения 1

Обе части — отображения $X\to W$. Пусть $x\in X$. Раскрываем композиции по определению, каждый раз снаружи внутрь: $\big(h\circ(g\circ f)\big)(x)=h\big((g\circ f)(x)\big)=h\big(g(f(x))\big),$ $\big((h\circ g)\circ f\big)(x)=(h\circ g)\big(f(x)\big)=h\big(g(f(x))\big).$ Значения совпадают при каждом $x\in X$, значит, отображения равны. $\blacksquare$

Поэтому скобки можно опускать: $h\circ g\circ f$.

Композиция не коммутативна. $f(x)=x+1$, $g(x)=2x$: $(g\circ f)(x)=2x+2$, а $(f\circ g)(x)=2x+1$.

Утверждение 1. Пусть $f\colon X\to Y$, $g\colon Y\to Z$.

1. Если $f$ и $g$ инъективны, то $g\circ f$ инъективно: из $g(f(x_1))=g(f(x_2))$ по инъективности $g$ получаем $f(x_1)=f(x_2)$, а по инъективности $f$ — $x_1=x_2$.
2. Если $f$ и $g$ сюръективны, то $g\circ f$ сюръективно: для $z\in Z$ найдём $y$ с $g(y)=z$, затем $x$ с $f(x)=y$; тогда $(g\circ f)(x)=z$.
3. Поэтому композиция биекций — биекция.
4. Если $g\circ f$ инъективно, то $f$ инъективно: из $f(x_1)=f(x_2)$ следует $g(f(x_1))=g(f(x_2))$, откуда $x_1=x_2$.
5. Если $g\circ f$ сюръективно, то $g$ сюръективно: каждое $z=g(f(x))$ имеет прообраз $f(x)$ при $g$.

1.3. Тождественное отображение

Определение 5. Отображение $\mathrm{id}_X\colon X\to X$ называется тождественным, если $\mathrm{id}_X(x)=x$ для всех $x\in X$.

Для любого $f\colon X\to Y$: $f\circ\mathrm{id}_X=f$ и $\mathrm{id}_Y\circ f=f$ — тождественное отображение нейтрально относительно композиции.

1.4. Обратное отображение и критерий обратимости

Определение 6. Пусть $f\colon X\to Y$, $g\colon Y\to X$. Отображение $g$ называется обратным к $f$, если $f\circ g=\mathrm{id}_Y\qquad\text{и}\qquad g\circ f=\mathrm{id}_X.$ Обозначение: $g=f^{-1}$. Отображение $f$ называется обратимым, если у него существует обратное.

Утверждение 2 (единственность обратного). Если $g_1$ и $g_2$ обратны к $f$, то $g_1=g_1\circ\mathrm{id}_Y=g_1\circ(f\circ g_2)=(g_1\circ f)\circ g_2=\mathrm{id}_X\circ g_2=g_2.$ Поэтому обозначение $f^{-1}$ корректно.

Нужны оба равенства. Пусть $f\colon\mathbb N\to\mathbb N$, $f(n)=n+1$ и $g(n)=\max(n-1,\,1)$. Тогда $g\circ f=\mathrm{id}_{\mathbb N}$, но $f\circ g\ne\mathrm{id}_{\mathbb N}$, так как $f(g(1))=2$. Отображение $f$ не обратимо — оно не сюръективно.

Теорема 2 (критерий обратимости). Отображение $f\colon X\to Y$ обратимо $\Leftrightarrow$ $f$ биективно.

Доказательство.

($\Rightarrow$) Пусть $f$ обратимо, $g=f^{-1}$.

1. Инъективность. Пусть $f(x_1)=f(x_2)$. Применим $g$ к обеим частям: $g(f(x_1))=g(f(x_2))$, то есть $(g\circ f)(x_1)=(g\circ f)(x_2)$, то есть $x_1=x_2$.
2. Сюръективность. Возьмём произвольный $y\in Y$ и положим $x=g(y)\in X$. Тогда $f(x)=f(g(y))=(f\circ g)(y)=y$ — прообраз найден.

($\Leftarrow$) Пусть $f$ биективно. Для каждого $y\in Y$ по сюръективности существует $x$ с $f(x)=y$, а по инъективности такой $x$ единственный. Положим $g(y)=x$. Определение корректно: $g$ задано на всём $Y$ и однозначно. Проверка: $f(g(y))=f(x)=y$, значит $f\circ g=\mathrm{id}_Y$; далее $g(f(x))$ — единственный элемент, который $f$ переводит в $f(x)$, то есть сам $x$, значит $g\circ f=\mathrm{id}_X$. $\blacksquare$

Утверждение 3. $(f^{-1})^{-1}=f$ — определение обратного симметрично относительно $f$ и $g$. Для биекций $f\colon X\to Y$, $g\colon Y\to Z$ $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$ — порядок меняется на обратный: надевали носки, потом обувь; снимаем обувь, потом носки.

Доказательство. Проверяем оба равенства из определения обратного, пользуясь ассоциативностью: $(f^{-1}\circ g^{-1})\circ(g\circ f)=f^{-1}\circ(g^{-1}\circ g)\circ f=f^{-1}\circ\mathrm{id}_Y\circ f=f^{-1}\circ f=\mathrm{id}_X,$ $(g\circ f)\circ(f^{-1}\circ g^{-1})=g\circ(f\circ f^{-1})\circ g^{-1}=g\circ\mathrm{id}_Y\circ g^{-1}=\mathrm{id}_Z.$ Значит, $f^{-1}\circ g^{-1}$ — обратное к $g\circ f$, а по единственности оно и есть $(g\circ f)^{-1}$. $\blacksquare$

---

2. Аксиоматика Пеано и натуральный ряд

2.1. Функция следования

Школьное «натуральные числа — это $1,2,3$ и так далее» опирается на слова «и так далее». Аксиоматика Пеано делает их точными: вместо сложения и сравнения берётся одна-единственная операция — переход к следующему элементу.

Пусть $\mathbb N$ — непустое множество, в котором выделен элемент $1$ и задано отображение $S\colon\mathbb N\to\mathbb N$. Оно называется функцией следования (от англ. successor): $S(n)$ читается «элемент, следующий за $n$».

• Интуитивно $S(n)=n+1$, но формально так писать пока нельзя: сложения ещё нет. Наоборот, сложение потом определяется через $S$ (§2.5), и $m+1=S(m)$ — первое правило этого определения.
• Числа $2,3,4,\dots$ — просто имена: $2=S(1)$, $3=S(S(1))$, $4=S(S(S(1)))$ и так далее.
• Сама по себе $S$ — произвольное отображение множества в себя. Запись $S(a)$ означает то же, что $f(a)$ для любой функции: значение $S$ на элементе $a$, то есть элемент, который по определению следует за $a$. Какой именно — задаётся вместе с $S$.

Аксиомы ниже — требования к $S$. Они отсекают «неправильные» функции следования и оставляют только привычную цепочку $1\to2\to3\to\dots$: Дедекинд доказал, что любые две модели пяти аксиом устроены одинаково с точностью до переименования элементов.

2.2. Пять аксиом

Определение 7. Множество $\mathbb N$ с выделенным элементом $1$ и функцией следования $S$ называется натуральным рядом, если выполнены пять аксиом:

1. Существование единицы: $1\in\mathbb N$.
2. Замкнутость относительно следования: $\forall n\in\mathbb N:\ S(n)\in\mathbb N$.
3. Единица не следует ни за кем: $\forall n\in\mathbb N:\ S(n)\ne1$. Иначе говоря, $S$ не сюръективно — у единицы нет прообраза.
4. Следование инъективно: $\forall n_1,n_2\in\mathbb N:\ n_1\ne n_2\Rightarrow S(n_1)\ne S(n_2)$ — у каждого элемента не более одного предыдущего.
5. Аксиома индукции: для любого подмножества $M\subseteq\mathbb N$ $\big(1\in M\big)\ \wedge\ \big(\forall n\in M:\ S(n)\in M\big)\ \Rightarrow\ M=\mathbb N.$

Замечания.

• В оригинале Пеано (1889) девять аксиом, но четыре из них описывают равенство; содержательных ровно пять — эти.
• В разных курсах натуральный ряд начинают с $0$ или с $1$; на смысл аксиом это не влияет, меняется только имя начального элемента.
• Аксиома 2 повторяет условие «$S$ — отображение из $\mathbb N$ в $\mathbb N$»; её выписывают отдельно ради явности.
• Аксиома 5 — единственная, говорящая обо всех подмножествах $\mathbb N$. Она запрещает «лишние» элементы, недостижимые из $1$ конечным числом шагов $S$.

2.3. Зачем нужна каждая аксиома

Чтобы показать, что аксиома не выводится из остальных, строят модель — множество с выделенной единицей и какой-нибудь функцией $S$, — в которой все остальные аксиомы выполнены, а эта нет. На лекции было два таких примера.

Без аксиомы 4. Множество $\{1;2\}$, $S(1)=2$, $S(2)=2$. Аксиомы 1, 2 очевидны; 3: $S(1)=2\ne1$ и $S(2)=2\ne1$; 5: если $M\ni1$ и $M$ замкнуто, то $2=S(1)\in M$, значит $M=\{1,2\}$. Но $S(1)=S(2)$ при $1\ne2$ — аксиома 4 нарушена. Ряд «зацикливается» на двойке.

Без аксиомы 5. Добавим к обычному ряду два лишних элемента, $\mathbb N'=\mathbb N\cup\{a;b\}$, и доопределим на них функцию следования: $S(n)=n+1\ \ (n\in\mathbb N),\qquad S(a)=b,\qquad S(b)=a.$ Здесь $S(a)$ — значение функции следования на новом элементе $a$: за $a$ следует $b$, за $b$ — снова $a$. Элементы $a$ и $b$ образуют замкнутый цикл, не связанный с цепочкой, начинающейся в $1$.

Проверим аксиомы:

1. $1\in\mathbb N'$.
2. Значения $n+1$, $b$, $a$ лежат в $\mathbb N'$.
3. $S(n)=n+1\ne1$, $S(a)=b\ne1$, $S(b)=a\ne1$.
4. На $\mathbb N$ значения — разные натуральные числа, а $S(a)=b$ и $S(b)=a$ различны между собой и не являются натуральными числами. Разные элементы переходят в разные.
5. Нарушена: $M=\mathbb N=\{1,2,3,\dots\}$ содержит $1$ и замкнуто ($S(n)=n+1\in M$), но $M\ne\mathbb N'$ — в нём нет $a$ и $b$.

Аксиома 5 говорит, что всё в $\mathbb N$ достижимо из $1$ конечным числом шагов $S$. Элементы $a$ и $b$ недостижимы, поэтому $\mathbb N'$ натуральным рядом не является.

А можно $S(a)=a$? Можно: модель $\mathbb N\cup\{a\}$ с петлёй $S(a)=a$ тоже нарушает только аксиому 5. $S(a)=a\ne1$, а инъективность не страдает, потому что в $a$ не переходит никакой другой элемент. Пара $a\leftrightarrow b$ с лекции — такой же пример, только с циклом длины $2$. Годится и цикл любой длины, и целый второй ряд $1'\to2'\to3'\to\dots$ А вот «приклеить» лишний элемент к основной цепочке нельзя:

Лишние элементы могут жить только отдельными циклами или цепочками, и такие отдельные куски отсекает аксиома 5.

Без аксиомы 3 (для полноты): $\{1\}$ с $S(1)=1$ или цикл $\{1,2,3\}$ с $S(1)=2$, $S(2)=3$, $S(3)=1$. Аксиомы 1, 2, 4, 5 выполнены, но единица следует за другим элементом.

2.4. Принцип математической индукции

Теорема 3 (классический принцип ММИ). Пусть $P(n)$ — предикат (утверждение, зависящее от $n\in\mathbb N$). Если

1. база индукции: $P(1)$ истинно;
2. индукционный переход: $\forall n\in\mathbb N:\ P(n)=T\ \Rightarrow\ P(n+1)=T$,

то $P(n)$ истинно для всех $n\in\mathbb N$. Здесь $T$ — «истина», а предположение «$P(n)$ истинно» в переходе называют индукционным предположением.

Доказательство. Рассмотрим множество тех $n$, для которых утверждение верно: $M=\{n\in\mathbb N\mid P(n)=T\}.$ По базе $1\in M$. По переходу: если $n\in M$, то $P(n+1)$ истинно, то есть $S(n)=n+1\in M$. Для $M$ выполнены обе посылки аксиомы 5, значит $M=\mathbb N$ — $P(n)$ истинно при всех $n$. $\blacksquare$

Замечания.

• ММИ — это аксиома 5, переписанная на языке предикатов. Обратно, из ММИ следует аксиома 5: взять $P(n)$ = «$n\in M$».
• База может начинаться с любого $n_0$; тогда вывод — «для всех $n\ge n_0$» (применить ММИ к $Q(k)=P(n_0+k-1)$).
• Без базы индукция не работает: для $P(n)$ = «$n=n+1$» переход $P(n)\Rightarrow P(n+1)$ формально верен, а утверждение ложно.

2.5. Сложение и умножение

Аксиомы дают только $S$. Арифметические операции определяются через $S$ рекурсивно — по второму аргументу.

Определение 8. Сложение $(+)$ в $\mathbb N$ — бинарная операция, заданная правилами

1. $m+1=S(m)$;
2. $m+S(n)=S(m+n)$ для всех $m,n\in\mathbb N$.

То есть $m+(n+1)=(m+n)+1$. Пример: $2+2=2+S(1)=S(2+1)=S(S(2))=S(3)=4$.

Определение 9. Произведение $(\cdot)$ в $\mathbb N$ — операция, заданная правилами

1. $m\cdot1=m$;
2. $m\cdot S(n)=m+m\cdot n$, то есть $m(n+1)=m+mn$.

Пример: $2\cdot2=2\cdot S(1)=2+2\cdot1=2+2=4$.

То, что такие операции существуют и единственны, — теорема о рекурсии (Дедекинд); в курсе она принимается без доказательства.

Утверждение 4. Сложение ассоциативно и коммутативно: $(a+b)+c=a+(b+c)$ и $a+b=b+a$.

Доказательство ассоциативности — индукция по $c$. База $c=1$: $(a+b)+1=S(a+b)=a+S(b)=a+(b+1)$. Переход: пусть верно для $c$; тогда $(a+b)+S(c)=S\big((a+b)+c\big)=S\big(a+(b+c)\big)=a+S(b+c)=a+(b+S(c))$. $\blacksquare$

Доказательство коммутативности

Лемма 1: $1+n=n+1$. Индукция по $n$: при $n=1$ очевидно; если $1+n=S(n)$, то $1+S(n)=S(1+n)=S(S(n))$.

Лемма 2: $S(m)+n=S(m+n)$. Индукция по $n$: $S(m)+1=S(S(m))=S(m+1)$; если верно для $n$, то $S(m)+S(n)=S(S(m)+n)=S(S(m+n))=S(m+S(n))$.

Коммутативность $m+n=n+m$ — индукция по $n$. База $m+1=1+m$ — лемма 1. Переход: $m+S(n)=S(m+n)=S(n+m)=S(n)+m$ — последнее равенство по лемме 2. $\blacksquare$

Так же по индукции проверяются дистрибутивность и свойства умножения.

2.6. Порядок на натуральных числах

Определение 10. Отношение строгого линейного порядка $<$ на $\mathbb N$ задаётся условием $n<m\ \Leftrightarrow\ \exists k\in\mathbb N:\ m=n+k.$ Нестрогий порядок: $n\le m\Leftrightarrow (n<m)\vee(n=m)$.

Все свойства порядка выводятся из аксиом. Для теоремы о вполне упорядоченности нужны четыре — докажем их, а не будем считать «очевидными».

Утверждение 5. Для всех $n,m,k\in\mathbb N$:

1. если $n\ne1$, то $n=S(m)$ для некоторого $m$ — у каждого элемента, кроме единицы, есть предшественник;
2. $1\le n$;
3. $n+k\ne n$, то есть $n\not<n$;
4. если $n<m$, то $n+1\le m$ (дискретность: между $n$ и $n+1$ других натуральных чисел нет).

Доказательство.

1. Пусть $M=\{1\}\cup\{S(m)\mid m\in\mathbb N\}$ — единица и все «следующие». $1\in M$, и если $n\in M$, то $S(n)\in M$ по построению. По аксиоме 5 $M=\mathbb N$.
2. Если $n\ne1$, то по п. 1 $n=S(m)=m+1=1+m$, то есть $1<n$ (подходит $k=m$).
3. По коммутативности достаточно доказать $k+n\ne n$ — индукцией по $n$ при фиксированном $k$. База: $k+1=S(k)\ne1$ по аксиоме 3. Переход: если $k+n\ne n$, то $k+S(n)=S(k+n)\ne S(n)$ — иначе по аксиоме 4 было бы $k+n=n$.
4. Пусть $m=n+k$. Если $k=1$, то $m=n+1$. Иначе по п. 1 $k=j+1$ для некоторого $j$, и $m=n+(1+j)=(n+1)+j$ по коммутативности и ассоциативности, то есть $n+1<m$. $\blacksquare$

Остальные свойства тоже доказываются по индукции:

• транзитивность: $n<m,\ m<p\Rightarrow n<p$ (если $m=n+k$, $p=m+l$, то $p=n+(k+l)$);
• линейность (трихотомия): для любых $n,m$ верно ровно одно из $n<m$, $n=m$, $m<n$;
• согласованность с операциями: $n<m\Rightarrow n+p<m+p$ и $np<mp$.

2.7. Теорема о вполне упорядоченности

Линейно упорядоченное множество называют вполне упорядоченным, если у каждого его непустого подмножества есть наименьший элемент. Для $\mathbb Z$, $\mathbb Q$, $\mathbb R$ это неверно: у самого $\mathbb Z$ и у интервала $(0;1)$ наименьшего элемента нет. Для $\mathbb N$ — верно.

Теорема 4 (о вполне упорядоченности множества $\mathbb N$). Всякое непустое подмножество $\mathbb N$ имеет наименьший элемент: $\forall A\subseteq\mathbb N,\ A\ne\varnothing\quad \exists m_0\in A:\ \forall m\in A\ \ m_0\le m.$

Упражнение 2 (с лекции). Доказать теорему о вполне упорядоченности.

Подсказка: от противного. Если у $A$ нет наименьшего элемента, докажите индукцией, что ни одно натуральное число не лежит в $A$.

Решение упражнения 2 (как на лекции)

Предположим противное: $A\subseteq\mathbb N$, $A\ne\varnothing$, и наименьшего элемента в $A$ нет. Положим $B=\mathbb N\setminus A$ и докажем сильной индукцией (§2.8), что $B=\mathbb N$.

База: $1\in B$. Если бы $1\in A$, то $1$ был бы наименьшим элементом $A$, потому что $1\le m$ для любого натурального $m$ (утверждение 5, п. 2). Наименьшего элемента нет, значит, $1\notin A$, то есть $1\in B$.

Переход. Пусть $1,2,\dots,n\in B$, то есть ни одно из этих чисел не лежит в $A$. Докажем, что $n+1\in B$. Пусть, напротив, $n+1\in A$. Любое натуральное $m<n+1$ удовлетворяет $m\le n$: иначе $n<m$, по дискретности $n+1\le m$, и вместе с $m<n+1$ получилось бы $m<m$ (п. 3). Значит, все числа, меньшие $n+1$, — это $1,\dots,n$, и ни одно из них не лежит в $A$. Тогда $n+1$ — наименьший элемент $A$, а его нет по предположению. Противоречие, так что $n+1\in B$.

По принципу сильной индукции $B=\mathbb N$, то есть $A=\mathbb N\setminus B=\varnothing$. Это противоречит условию $A\ne\varnothing$, значит, наименьший элемент есть. $\blacksquare$

Круга в рассуждении нет: сильная индукция (теорема 5) выводится из обычной ММИ, а не из вполне упорядоченности.

Ниже другое доказательство — прямое, без «от противного» и без сильной индукции: оно опирается только на аксиому 5.

Идея. Рассмотрим числа, лежащие строго левее всех элементов $A$. Для $A=\{4,7,9,\dots\}$ это $B=\{1,2,3\}$. Множество $B$ растёт от единицы шагами $+1$, пока не упрётся в первый элемент $A$: $3\in B$, а $4\notin B$ — и $4$ как раз наименьший элемент. Аксиома 5 гарантирует, что упирание произойдёт: $B$ не может оказаться всем $\mathbb N$.

Доказательство. Пусть $A\subseteq\mathbb N$, $A\ne\varnothing$. Положим $B=\{n\in\mathbb N\mid \forall a\in A:\ n<a\}.$

Шаг 1: $B\ne\mathbb N$. Возьмём любой $a\in A$. Если бы $a\in B$, было бы $a<a$, что невозможно (утверждение 5, п. 3). Значит, $a\notin B$.

Шаг 2. Раз $B\ne\mathbb N$, посылка аксиомы 5 для $B$ не выполнена: либо $1\notin B$, либо найдётся $n\in B$, для которого $n+1\notin B$.

Случай 1: $1\notin B$. Тогда есть $a\in A$, для которого неверно $1<a$. Но $1\le a$ (п. 2), значит $a=1$, то есть $1\in A$. А $1\le m$ для всех $m\in A$ — единица и есть наименьший элемент.

Случай 2: $n\in B$, но $n+1\notin B$. Из $n\in B$: $n<a$ для всех $a\in A$, и по дискретности (п. 4) $n+1\le a$ для всех $a\in A$. Из $n+1\notin B$: есть $a_0\in A$, для которого неверно $n+1<a_0$; вместе с $n+1\le a_0$ это даёт $a_0=n+1$. Итак, $n+1\in A$ и $n+1\le a$ для всех $a\in A$: наименьший элемент $m_0=n+1$. $\blacksquare$

Замечания.

• Наименьший элемент единственный: два наименьших были бы $\le$ друг друга, а при $m_0\ne m_1$ это означало бы $m_0<m_1<m_0$ и по транзитивности $m_0<m_0$.
• Обратно: из вполне упорядоченности следует ММИ. Пусть база и переход выполнены, но множество контрпримеров $A=\{n\mid P(n)\ \text{ложно}\}$ непусто. Возьмём его наименьший элемент $n_0$. По базе $n_0\ne1$, значит $n_0=m+1$ (утверждение 5, п. 1) и $m<n_0$, поэтому $m\notin A$ — $P(m)$ истинно. По переходу истинно $P(m+1)=P(n_0)$ — противоречие. Такой приём называют методом наименьшего контрпримера.
• Аксиома индукции, ММИ, сильная индукция (§2.8) и вполне упорядоченность попарно эквивалентны (при остальных аксиомах).

2.8. Сильная индукция

Теорема 5 (сильный метод математической индукции). Утверждение $P(n)$ истинно для всех $n\in\mathbb N$, если

1. база: $P(1)$ истинно;
2. переход: если истинны $P(1),P(2),\dots,P(n)$, то истинно $P(n+1)$.

Доказательство. Применим обычную ММИ к предикату $Q(n)$ = «$P(1),\dots,P(n)$ все истинны». База: $Q(1)=P(1)$ — истинно. Переход: из $Q(n)$ по условию 2 следует $P(n+1)$, а $Q(n)\wedge P(n+1)=Q(n+1)$. Значит, $Q(n)$ верно для всех $n$, тем более $P(n)$. $\blacksquare$

Когда нужна. Логически обычная и сильная индукция равносильны, разница — в удобстве индукционного предположения. Обычная удобна, когда $P(n+1)$ естественно выводится из $P(n)$; сильная — когда объект размера $n+1$ распадается на меньшие объекты разных размеров: числа Фибоначчи (нужны два предыдущих), разложение на простые (нужно утверждение для произвольного делителя). Если переход использует $P(n-1)$, база должна покрывать два значения, $n=1$ и $n=2$.

Пример (основная теорема арифметики, существование). Каждое целое $n\ge2$ раскладывается в произведение простых. База $n=2$: само простое. Переход: пусть все числа от $2$ до $n$ раскладываются. Если $n+1$ простое — готово. Если составное, $n+1=ab$, где $2\le a,b\le n$. По сильному предположению и $a$, и $b$ раскладываются, значит и $n+1=ab$ раскладывается. $\blacksquare$ Обычной индукции здесь недостаточно: делители $a$ и $b$ — произвольные числа, меньшие $n+1$, а не обязательно $n$.

---

3. Примеры применения индукции

3.1. Сумма квадратов

Утверждение 6. $\displaystyle 1^2+2^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}$ для всех $n\in\mathbb N$.

База $n=1$: слева $1$, справа $\dfrac{1\cdot2\cdot3}{6}=1$.

Переход. Пусть $\displaystyle\sum_{i=1}^{k}i^2=\frac{k(k+1)(2k+1)}{6}$. Тогда $\sum_{i=1}^{k+1}i^2=\frac{k(k+1)(2k+1)}{6}+(k+1)^2=\frac{(k+1)\big(k(2k+1)+6(k+1)\big)}{6}=\frac{(k+1)(2k^2+7k+6)}{6}=\frac{(k+1)(k+2)(2k+3)}{6},$ а это формула при $n=k+1$: $(k+1)\big((k+1)+1\big)\big(2(k+1)+1\big)$. $\blacksquare$

Родственные формулы: $\displaystyle\sum_{i=1}^n i=\frac{n(n+1)}{2}$, $\displaystyle\sum_{i=1}^n i^3=\Big(\frac{n(n+1)}{2}\Big)^2$.

3.2. Числа Фибоначчи и формула Бине

Определение 11. $F_1=1$, $F_2=1$, $F_n=F_{n-1}+F_{n-2}$ при $n\ge3$: $\ 1,1,2,3,5,8,13,21,\dots$

Иногда нумерацию начинают с $F_0=0$, $F_1=1$ — это та же последовательность со сдвигом индекса; формула Бине верна и при $n=0$.

Утверждение 7 (формула Бине). $F_n=\frac{1}{\sqrt5}\big(\varphi^n-\psi^n\big),\qquad \varphi=\frac{1+\sqrt5}{2}\approx1{,}618,\quad \psi=\frac{1-\sqrt5}{2}\approx-0{,}618.$ Здесь $\varphi$ — золотое сечение, $\psi$ — сопряжённое к нему число; оба — корни уравнения $t^2=t+1$. Полезные соотношения: $\varphi+\psi=1$, $\varphi-\psi=\sqrt5$, $\varphi\psi=-1$.

Откуда берётся формула: характеристическое уравнение

Ищем решение рекуррентности $F_n=F_{n-1}+F_{n-2}$ в виде геометрической прогрессии $F_n=t^n$. Подстановка даёт $t^n=t^{n-1}+t^{n-2}$, после деления на $t^{n-2}$ — характеристическое уравнение $t^2=t+1$, то есть $t^2-t-1=0$, с корнями $\varphi$ и $\psi$.

Рекуррентность линейна, поэтому любая комбинация $A\varphi^n+B\psi^n$ тоже ей удовлетворяет. Коэффициенты подбираем по начальным условиям: $F_0=0$ даёт $A+B=0$, $F_1=1$ даёт $A\varphi+B\psi=1$, откуда $A(\varphi-\psi)=A\sqrt5=1$, $A=\tfrac1{\sqrt5}$, $B=-\tfrac1{\sqrt5}$. Так формула угадывается; ниже она доказывается индукцией.

Доказательство сильной индукцией. Ключевое свойство корней: $\varphi^2=\varphi+1$, $\psi^2=\psi+1$, откуда $\varphi^{n+1}=\varphi^n+\varphi^{n-1}$ и так же для $\psi$.

Базы — две: $n=1$: $\dfrac{\varphi-\psi}{\sqrt5}=\dfrac{\sqrt5}{\sqrt5}=1=F_1$; $n=2$: $\dfrac{\varphi^2-\psi^2}{\sqrt5}=\dfrac{(\varphi-\psi)(\varphi+\psi)}{\sqrt5}=\dfrac{\sqrt5\cdot1}{\sqrt5}=1=F_2$.

Переход. Пусть формула верна для $n-1$ и $n$ (где $n\ge2$). Тогда $F_{n+1}=F_n+F_{n-1}=\frac{1}{\sqrt5}\big(\varphi^{n-1}(\varphi+1)-\psi^{n-1}(\psi+1)\big)=\frac{1}{\sqrt5}\big(\varphi^{n-1}\varphi^2-\psi^{n-1}\psi^2\big)=\frac{1}{\sqrt5}\big(\varphi^{n+1}-\psi^{n+1}\big).\ \blacksquare$

Обычная индукция здесь не подходит: чтобы получить $F_{n+1}$, нужны $F_n$ и $F_{n-1}$.

Так как $|\psi|<1$, слагаемое $\psi^n/\sqrt5$ по модулю меньше $1/2$, поэтому $F_n$ — ближайшее целое к $\varphi^n/\sqrt5$. Отсюда же $F_{n+1}/F_n\to\varphi$.

3.3. Неравенство Бернулли

Теорема 6 (неравенство Бернулли). Для всех $n\in\mathbb N$ и всех $x\ge-1$ $(1+x)^n\ \ge\ 1+nx.$

Что оно говорит. Если раскрыть $(1+x)^n$ по биному (§3.5), получится $1+nx+C_n^2x^2+\dots+x^n$. Неравенство утверждает, что всё после первых двух слагаемых в сумме неотрицательно: степень не меньше своей «линейной части». При $x\ge0$ это видно сразу — все слагаемые неотрицательны. При $-1\le x<0$ знаки слагаемых чередуются, и тут нужна индукция.

Доказательство — ММИ по $n$ при фиксированном $x\ge-1$.

База $n=1$: $1+x\ge1+x$ — равенство.

Переход. Пусть $(1+x)^k\ge1+kx$ — индукционное предположение. Умножим обе части на $1+x$. Так как $x\ge-1$, множитель $1+x\ge0$, и знак неравенства сохраняется: $(1+x)^{k+1}=(1+x)^k(1+x)\ \ge\ (1+kx)(1+x).$ Раскроем скобки справа: $(1+kx)(1+x)=1+x+kx+kx^2=1+(k+1)x+kx^2\ \ge\ 1+(k+1)x,$ так как $kx^2\ge0$. Получили $(1+x)^{k+1}\ge1+(k+1)x$ — утверждение для $k+1$. $\blacksquare$

Геометрический смысл. Прямая $y=1+nx$ касается графика $y=(1+x)^n$ в точке $(0;1)$, и неравенство говорит, что при $x\ge-1$ график лежит не ниже этой прямой.

На рисунке $n=3$: сплошная линия — $y=(1+x)^3$, пунктир — $y=1+3x$.

Строгая форма. При $n\ge2$, $x>-1$, $x\ne0$ неравенство строгое: в первом же переходе отбрасывается $kx^2>0$, а дальше строгое неравенство умножается на $1+x>0$ и остаётся строгим.

А что при x < −1?

Условие $x\ge-1$ нужно доказательству, но это не точная граница. При $-2\le x<-1$ и $n\ge2$ неравенство всё ещё верно: $|1+x|\le1$, поэтому $(1+x)^n\ge-1$, а $1+nx\le1-n\le-1$. При чётном $n$ оно верно вообще для всех $x$: при $x<-1$ слева неотрицательное число, а справа $1+nx<1-n<0$. Нарушиться неравенство может только при нечётном $n\ge3$ и $x<-2$ — как в примере $x=-4$, $n=3$.

Применения — грубая оценка степени без раскрытия скобок:

• $1{,}01^{100}=(1+0{,}01)^{100}\ge1+100\cdot0{,}01=2$ (на самом деле $\approx2{,}70$);
• $0{,}99^{50}=(1-0{,}01)^{50}\ge1-50\cdot0{,}01=0{,}5$ (на самом деле $\approx0{,}605$) — здесь $x<0$, и условие $x\ge-1$ как раз работает;
• $\big(1+\tfrac1n\big)^n\ge1+n\cdot\tfrac1n=2$;
• при $q>1$: $q^n=\big(1+(q-1)\big)^n\ge1+n(q-1)$ — степени неограниченно растут;
• при $0<q<1$ запишем $q=\frac1{1+h}$, $h>0$: $q^n=\frac1{(1+h)^n}\le\frac1{1+nh}$ — отсюда в теории пределов получают $q^n\to0$.

3.4. Биномиальные коэффициенты и треугольник Паскаля

Определение 12. $n!=1\cdot2\cdots n$, $0!=1$. Биномиальный коэффициент («число сочетаний из $n$ по $k$»): $C_n^k=\binom nk=\frac{n!}{k!\,(n-k)!},\qquad 0\le k\le n.$

Смысл: $C_n^k$ — число способов выбрать $k$ элементов из $n$ без учёта порядка, то есть число $k$-элементных подмножеств $n$-элементного множества. Из пяти человек двоих дежурных можно выбрать $C_5^2=\frac{5!}{2!\,3!}=\frac{120}{2\cdot6}=10$ способами.

Считать удобнее после сокращения: $C_n^k=\dfrac{n(n-1)\cdots(n-k+1)}{k!}$ — в числителе $k$ множителей. Например, $C_7^3=\dfrac{7\cdot6\cdot5}{3!}=35$. Частные значения: $C_n^0=C_n^n=1$, $C_n^1=C_n^{n-1}=n$, $C_n^2=\dfrac{n(n-1)}2$.

Утверждение 8 (свойства биномиальных коэффициентов).

1. Симметрия: $C_n^k=C_n^{\,n-k}$.
2. Тождество Паскаля: $C_{n+1}^{\,k}=C_n^{\,k}+C_n^{\,k-1}$ при $1\le k\le n$.

Доказательство.

1. Формула не меняется при замене $k\leftrightarrow n-k$: $\dfrac{n!}{k!\,(n-k)!}=\dfrac{n!}{(n-k)!\,k!}$. Комбинаторно: выбрать $k$ элементов — то же, что выбрать $n-k$ невыбранных.
2. Приведём к общему знаменателю $k!\,(n-k+1)!$, пользуясь тем, что $k!=k\cdot(k-1)!$ и $(n-k+1)!=(n-k+1)\cdot(n-k)!$: $C_n^k+C_n^{k-1}=\frac{n!}{k!\,(n-k)!}+\frac{n!}{(k-1)!\,(n-k+1)!}=\frac{n!\,(n-k+1)+n!\,k}{k!\,(n-k+1)!}=\frac{n!\,(n+1)}{k!\,(n+1-k)!}=\frac{(n+1)!}{k!\,(n+1-k)!}=C_{n+1}^k.$ Комбинаторно: $k$-элементные подмножества множества $\{1,\dots,n+1\}$ бывают двух типов. Не содержащие элемент $n+1$: все $k$ элементов выбираются из $\{1,\dots,n\}$, таких $C_n^k$. Содержащие $n+1$: остальные $k-1$ элементов выбираются из $n$, таких $C_n^{k-1}$. $\blacksquare$

Треугольник Паскаля. Выпишем коэффициенты по строкам: в строке $n$ (нумерация с нуля) стоят $C_n^0,C_n^1,\dots,C_n^n$. По краям единицы, а каждое внутреннее число по тождеству Паскаля равно сумме двух чисел над ним.

n=0:                    1
n=1:                  1   1
n=2:                1   2   1
n=3:              1   3   3   1
n=4:            1   4   6   4   1
n=5:          1   5  10  10   5   1
n=6:        1   6  15  20  15   6   1
n=7:      1   7  21  35  35  21   7   1
n=8:    1   8  28  56  70  56  28   8   1

Например, $10$ в строке $5$ — это $4+6$ из строки $4$: $C_5^2=C_4^2+C_4^1$.

Что видно в треугольнике:

• строки симметричны — это $C_n^k=C_n^{n-k}$;
• вторая диагональ $1,2,3,4,\dots$ — это $C_n^1=n$; третья $1,3,6,10,15,\dots$ — треугольные числа $C_n^2=\frac{n(n-1)}2$;
• сумма строки $n$ равна $2^n$: $1,2,4,8,16,\dots$ (следствие бинома, §3.5);
• все числа треугольника целые. Из формулы $\frac{n!}{k!\,(n-k)!}$ это не очевидно — это дробь. А из тождества Паскаля следует индукцией по $n$: строка $0$ целая, а каждая следующая строка складывается из единиц по краям и сумм целых чисел предыдущей.

Утверждение 9 («хоккейная клюшка»). Для $0\le k\le n$ $C_k^k+C_{k+1}^k+\dots+C_n^k=C_{n+1}^{k+1}.$ В треугольнике: сумма чисел вдоль диагонали равна числу, стоящему под последним из них со сдвигом в сторону. При $k=1$ это $1+2+\dots+n=C_{n+1}^2=\frac{n(n+1)}2$; при $k=2$, $n=4$: $1+3+6=10=C_5^3$.

Доказательство — ММИ по $n$ при фиксированном $k$, начиная с $n=k$. База: $C_k^k=1=C_{k+1}^{k+1}$. Переход: если сумма до $C_n^k$ равна $C_{n+1}^{k+1}$, то после добавления $C_{n+1}^k$ получаем $C_{n+1}^{k+1}+C_{n+1}^k=C_{n+2}^{k+1}$ — тождество Паскаля с $n+1$ вместо $n$ и $k+1$ вместо $k$. $\blacksquare$

3.5. Бином Ньютона

Теорема 7 (бином Ньютона). Для всех $n\in\mathbb N$ и любых чисел $a,b$ $(a+b)^n=\sum_{k=0}^{n}C_n^k\,a^{n-k}b^k=C_n^0a^n+C_n^1a^{n-1}b+C_n^2a^{n-2}b^2+\dots+C_n^nb^n.$

Как читать формулу: слагаемых $n+1$; степень $a$ убывает от $n$ до $0$, степень $b$ растёт от $0$ до $n$, в каждом слагаемом сумма степеней равна $n$; коэффициенты — строка $n$ треугольника Паскаля.

• $(a+b)^2=a^2+2ab+b^2$ — строка $1,2,1$;
• $(a+b)^3=a^3+3a^2b+3ab^2+b^3$ — строка $1,3,3,1$;
• $(a+b)^4=a^4+4a^3b+6a^2b^2+4ab^3+b^4$ — строка $1,4,6,4,1$.

Откуда в биноме треугольник Паскаля. Посмотрим на переход от квадрата к кубу: $(a+b)^3=(a+b)(a^2+2ab+b^2)=\underbrace{a^3+2a^2b+ab^2}_{\text{умножили на }a}+\underbrace{a^2b+2ab^2+b^3}_{\text{умножили на }b}=a^3+(2+1)a^2b+(1+2)ab^2+b^3.$ Каждый коэффициент новой строки — сумма двух соседних коэффициентов старой. В общем виде это и есть доказательство.

Доказательство — ММИ по $n$; в переходе используется тождество Паскаля $C_{n+1}^k=C_n^k+C_n^{k-1}$.

База $n=1$: $\displaystyle\sum_{k=0}^{1}C_1^ka^{1-k}b^k=C_1^0a+C_1^1b=a+b$.

Переход. Пусть $(a+b)^n=\sum_{k=0}^{n}C_n^ka^{n-k}b^k$. Умножим на $a+b$ и раскроем скобки: $(a+b)^{n+1}=\sum_{k=0}^{n}C_n^ka^{n+1-k}b^k+\sum_{k=0}^{n}C_n^ka^{n-k}b^{k+1}.$ Во второй сумме заменим индекс: $j=k+1$ пробегает $1,\dots,n+1$, а $a^{n-k}=a^{n+1-j}$. Снова назовём индекс $k$: $\sum_{k=0}^{n}C_n^ka^{n-k}b^{k+1}=\sum_{k=1}^{n+1}C_n^{k-1}a^{n+1-k}b^k.$ Теперь в обеих суммах одночлены одинаковые — $a^{n+1-k}b^k$. Слагаемое с $k=0$ есть только в первой сумме: $C_n^0a^{n+1}=a^{n+1}$. С $k=n+1$ — только во второй: $C_n^nb^{n+1}=b^{n+1}$. При $1\le k\le n$ коэффициенты складываются: $(a+b)^{n+1}=a^{n+1}+\sum_{k=1}^{n}\big(C_n^k+C_n^{k-1}\big)a^{n+1-k}b^k+b^{n+1}.$ По тождеству Паскаля $C_n^k+C_n^{k-1}=C_{n+1}^k$, а крайние коэффициенты $1=C_{n+1}^0=C_{n+1}^{n+1}$. Итого $(a+b)^{n+1}=\sum_{k=0}^{n+1}C_{n+1}^ka^{n+1-k}b^k$ — утверждение для $n+1$. $\blacksquare$

Комбинаторное объяснение. $(a+b)^n$ — произведение $n$ одинаковых скобок. Раскрывая их, из каждой скобки берём $a$ или $b$. Одночлен $a^{n-k}b^k$ получается всякий раз, когда $b$ взято ровно из $k$ скобок, а из остальных $n-k$ — $a$. Выбрать эти $k$ скобок можно $C_n^k$ способами — это и есть коэффициент.

Общий член. Слагаемое с номером $k+1$: $T_{k+1}=C_n^ka^{n-k}b^k$. По нему находят один коэффициент, не раскрывая всё:

• коэффициент при $x^3$ в $(1+2x)^5$: $T_4=C_5^3\cdot1^2\cdot(2x)^3=10\cdot8\,x^3$, ответ $80$;
• свободный член в $\big(x+\frac1x\big)^6$: $T_{k+1}=C_6^kx^{6-k}x^{-k}=C_6^kx^{6-2k}$, степень $0$ при $k=3$, ответ $C_6^3=20$.

Следствия — подстановки конкретных $a$ и $b$:

• $a=b=1$: $\sum_{k=0}^nC_n^k=2^n$ — у $n$-элементного множества $2^n$ подмножеств;
• $a=1$, $b=-1$: $\sum_{k=0}^n(-1)^kC_n^k=0$ при $n\ge1$ — суммы коэффициентов на чётных и нечётных местах равны;
• $b\to-b$: $(a-b)^n=\sum_{k=0}^n(-1)^kC_n^ka^{n-k}b^k$ — знаки чередуются: $(a-b)^3=a^3-3a^2b+3ab^2-b^3$;
• $a=1$, $b=x$: $(1+x)^n=1+nx+\frac{n(n-1)}2x^2+\dots+x^n$. При $x\ge0$ все слагаемые неотрицательны, отсюда сразу неравенство Бернулли для $x\ge0$ и оценка $(1+x)^n\ge\frac{n(n-1)}2x^2$, которая понадобится в пределах.

В теории вероятностей те же коэффициенты дают биномиальное распределение: вероятность ровно $k$ успехов в $n$ испытаниях равна $C_n^kp^k(1-p)^{n-k}$.

---

4. Мощность множеств

4.1. Равномощность

Для конечного множества мощность — просто число элементов: $|\{a,b,c\}|=3$. Бесконечные множества «пересчитать до конца» нельзя, поэтому мощности сравнивают с помощью отображений: два множества «одинаково велики», если их элементы можно поставить во взаимно однозначное соответствие.

Определение 13. Множества $X$ и $Y$ называются равномощными, если существует биекция $X\to Y$. Обозначение: $X\sim Y$ или $|X|=|Y|$.

Свойства (равномощность — отношение эквивалентности):

1. рефлексивность: $X\sim X$ (биекция $\mathrm{id}_X$);
2. симметричность: $X\sim Y\Rightarrow Y\sim X$ (обратное к биекции — биекция);
3. транзитивность: $X\sim Y,\ Y\sim Z\Rightarrow X\sim Z$ (композиция биекций — биекция).

Определение 14. Мощность (кардинальное число) множества $X$ — класс всех множеств, равномощных $X$. Для конечных множеств мощность — число элементов; для бесконечных это обобщение понятия «количество элементов».

4.2. Счётные множества

Определение 15. Множество $A$ называется счётным, если $A\sim\mathbb N$ — его элементы «можно занумеровать»: $A=\{a_1,a_2,a_3,\dots\}$ без пропусков и повторов. Мощность счётного множества: $|\mathbb N|=\aleph_0$ («алеф-нуль»; другие обозначения — $\mathfrak a$, $\omega$).

Определение 16. $X$ конечно, если $X=\varnothing$ или $X\sim\{1,\dots,n\}$ для некоторого $n$; иначе бесконечно. Не более чем счётно (н.б.с.) = конечно или счётно. Бесконечное множество, не равномощное $\mathbb N$, называется несчётным.

Примеры.

1. (Парадокс Дедекинда, он же парадокс Галилея.) $\mathbb N\sim2\mathbb N=\{2,4,6,\dots\}$; биекция $\varphi\colon\mathbb N\to2\mathbb N$, $\varphi(n)=2n$. Аналогично $\mathbb N$ равномощно множеству нечётных чисел: $n\mapsto2n-1$. Бесконечное множество равномощно своему собственному подмножеству — с конечными множествами такого не бывает. Дедекинд предложил взять это свойство за определение бесконечности.
2. $(0;1)\sim(0;+\infty)$; биекция $\varphi(x)=\dfrac1x-1$. Проверка: функция строго убывает на $(0;1)$; при $x\to0^+$ получаем $\varphi\to+\infty$, при $x\to1^-$ получаем $\varphi\to0$; обратная $x=\dfrac{1}{1+y}$. Другая биекция — $x\mapsto\dfrac{x}{1-x}$ с обратной $y\mapsto\dfrac{y}{1+y}$.
3. $\mathbb Z\sim\mathbb N$: нумерация $0,\,1,\,-1,\,2,\,-2,\dots$ Явная формула биекции $\mathbb N\to\mathbb Z$: $f(1)=0$, $f(2k)=k$, $f(2k+1)=-k$ при $k\ge1$.
4. Любые два интервала $(a;b)\sim(c;d)$ (линейная функция); $(-1;1)\sim\mathbb R$ через $x\mapsto\dfrac{x}{1-x^2}$ или $\big(-\tfrac\pi2;\tfrac\pi2\big)\sim\mathbb R$ через $\tan$.

4.3. Сравнение мощностей и теорема Кантора–Бернштейна

Определение 17.

• $|A|\le|B|$ $\Leftrightarrow$ существует инъекция $A\to B$ ($A$ «вкладывается» в $B$: равномощно некоторому подмножеству $B$).
• $|A|\ge|B|$ $\Leftrightarrow$ $|B|\le|A|$, то есть существует инъекция $B\to A$. Для $B\ne\varnothing$ это равносильно существованию сюръекции $A\to B$ (одна из импликаций — «из сюръекции $A\to B$ построить инъекцию $B\to A$», выбирая по одному прообразу для каждого $b$ — использует аксиому выбора).
• $|A|<|B|$ $\Leftrightarrow$ $|A|\le|B|$ и $A\not\sim B$.

Теорема 8 (Кантора–Бернштейна). Если $|A|\le|B|$ и $|B|\le|A|$, то $|A|=|B|$. Иначе: из инъекций $f\colon A\to B$ и $g\colon B\to A$ можно построить биекцию $A\to B$. (В курсе — без доказательства.)

Смысл. Отношение $\le$ на мощностях антисимметрично, и проверка равномощности сводится к предъявлению двух инъекций — это обычно много проще, чем явно построить биекцию.

Пример. $(0;1)\sim[0;1]$.

• $\varphi\colon(0;1)\to[0;1]$, $\varphi(x)=x$ — инъекция, значит $|(0;1)|\le|[0;1]|$.
• $\psi\colon[0;1]\to(0;1)$, $\psi(x)=\dfrac{x+1}{3}$ — инъекция (образ $[\tfrac13;\tfrac23]\subset(0;1)$), значит $|[0;1]|\le|(0;1)|$.

По теореме Кантора–Бернштейна множества равномощны. $\blacksquare$

Доказательство теоремы Кантора–Бернштейна. На лекции теорема дана без доказательства, но оно элементарное: нужны только определения инъекции и биекции. Элементы $A$ и $B$, связанные отображениями $f$ и $g$, выстраиваются в цепочки, и внутри каждой цепочки биекцию видно сразу.

Пусть $f\colon A\to B$ и $g\colon B\to A$ — инъекции. Будем считать, что $A\cap B=\varnothing$, чтобы про каждый элемент было ясно, из какого он множества. Если множества пересекаются, как $(0;1)$ и $[0;1]$, их заменяют непересекающимися копиями $A\times\{0\}$ и $B\times\{1\}$ — на мощности это не влияет.

Шаг 1: стрелки и предки. Проведём стрелку $a\to f(a)$ из каждого $a\in A$ и стрелку $b\to g(b)$ из каждого $b\in B$. Из каждого элемента выходит ровно одна стрелка: $f$ и $g$ — отображения. В каждый элемент входит не больше одной стрелки: если бы $f(a_1)=f(a_2)$ при $a_1\ne a_2$, это нарушило бы инъективность $f$, и так же для $g$. Начало входящей стрелки назовём предком элемента:

• предок $a\in A$ — такой $b\in B$, что $g(b)=a$; он есть, только если $a\in g(B)$;
• предок $b\in B$ — такой $a\in A$, что $f(a)=b$; он есть, только если $b\in f(A)$.

Именно здесь работает инъективность: предок, если он есть, единственный, поэтому назад от элемента можно идти только одним путём.

Шаг 2: цепочки. Возьмём любой элемент и будем двигаться по стрелкам вперёд и назад, к предкам, пока это возможно. Все элементы, до которых так можно добраться, образуют его цепочку. Два элемента лежат в одной цепочке, если от одного до другого можно дойти по стрелкам в каком-то направлении. Это отношение эквивалентности, поэтому цепочки не пересекаются и покрывают $A\cup B$ целиком. В цепочке элементы из $A$ и $B$ чередуются, потому что стрелки ведут из $A$ в $B$ и из $B$ в $A$.

Тип цепочки определяется тем, что происходит при движении назад, к предкам. Есть четыре варианта:

(1) начало в A:   a0 → b1 → a2 → b3 → a4 → …          у a0 нет предка
(2) начало в B:   b0 → a1 → b2 → a3 → b4 → …          у b0 нет предка
(3) цикл:         a0 → b1 → a2 → … → b(2k−1) → a0     предки есть у всех
(4) без начала:   … → a(−2) → b(−1) → a0 → b1 → …     предки есть у всех, повторов нет

Если путь назад обрывается, мы пришли к элементу без предка — это начало цепочки, и важно, в каком оно множестве: тип (1) или (2). Если путь назад бесконечен, то он либо возвращается в уже пройденный элемент (цикл, тип 3, его длина чётна из-за чередования), либо никогда не повторяется (тип 4).

Шаг 3: биекция внутри каждой цепочки. Нужно разбить элементы цепочки на пары «элемент $A$ — элемент $B$».

• В цепочках типов (1), (3) и (4) каждому $a$ сопоставляем следующий элемент: $a\mapsto f(a)$. Каждый элемент $B$ в такой цепочке получает пару, потому что у него есть предок в $A$: в типе (1) цепочка начинается с элемента $A$, в типах (3) и (4) предки есть у всех.
• В цепочке типа (2) так делать нельзя: начало $b_0$ ни в чей образ при $f$ не попадает и останется без пары. Поэтому каждому $a$ сопоставляем его предка: $a_1\mapsto b_0$, $a_3\mapsto b_2$, … То есть $a\mapsto g^{-1}(a)$. Предок есть у каждого $a$ такой цепочки, ведь она начинается с элемента $B$.

Шаг 4: общая формула. Обозначим через $A_A$, $A_B$, $A_\infty$ элементы $A$, лежащие в цепочках с началом в $A$, с началом в $B$ и без начала (типы 3 и 4). Положим $h(a)=\begin{cases}f(a),& a\in A_A\cup A_\infty,\\ g^{-1}(a),& a\in A_B.\end{cases}$ Элемент $h(a)$ лежит в той же цепочке, что и $a$, и по шагу 3 на каждой цепочке $h$ — биекция между её элементами из $A$ и из $B$.

• Инъективность. Если $h(a)=h(a')$, то $a$ и $a'$ из одной цепочки, а на одной цепочке $h$ инъективно: там это либо $f$, либо $g^{-1}$, и оба инъективны.
• Сюръективность. Любой $b\in B$ лежит в какой-то цепочке и по шагу 3 получает пару.

Значит, $h\colon A\to B$ — биекция. $\blacksquare$

Чтобы узнать, по какому правилу отображать конкретный $a$, достаточно пройти назад по его предкам: $a$, $g^{-1}(a)$, $f^{-1}\big(g^{-1}(a)\big)$, … и посмотреть, где путь оборвётся. Если на элементе $B$, берём $g^{-1}$. Если на элементе $A$ или путь не обрывается, берём $f$.

4.4. Явная биекция отрезка на интервал

Выделим в $[0;1]$ счётную последовательность $\Big\{\dfrac1{2^n}\Big\}=\Big\{\dfrac12,\dfrac14,\dfrac18,\dots\Big\}$ и «сдвинем» по ней два лишних элемента $0$ и $1$: $f(0)=\frac12,\qquad f(1)=\frac14,\qquad f\Big(\frac1{2^n}\Big)=\frac1{2^{n+2}}\ \ (n\ge1),\qquad f(x)=x\ \text{ для всех остальных } x.$ То есть $0\to\frac12$, $1\to\frac14$, $\frac12\to\frac18$, $\frac14\to\frac1{16}$, $\frac18\to\frac1{32}$ и т.д.

Проверка. В образ попадают $\frac12$ и $\frac14$ (из $0$ и $1$), затем $\frac18,\frac1{16},\dots$ (из $\frac12,\frac14,\dots$) и все остальные точки $(0;1)$, которые остаются на месте — сюръекция. Разные точки переходят в разные — инъекция. Это идея «отеля Гильберта»: в счётном множестве всегда найдётся место для конечного (и даже счётного) числа новых элементов.

4.5. Свойства счётных множеств

1. Любое подмножество счётного множества либо конечно, либо счётно (не более чем счётно). Доказательство. Пусть $A=\{a_1,a_2,\dots\}$, $B\subseteq A$ бесконечно. Нумеруем $B$ в порядке возрастания индексов: $b_1$ — элемент $B$ с наименьшим индексом (существует по вполне упорядоченности $\mathbb N$, теорема 4), $b_2$ — со следующим наименьшим, и т.д. Каждый элемент $B$ получит номер, так как перед ним лишь конечное число элементов.
2. Бесконечное подмножество счётного множества счётно — частный случай свойства 1. Также: всякое бесконечное множество содержит счётное подмножество (выбираем $a_1$, затем $a_2\ne a_1$, $a_3\notin\{a_1,a_2\}$, … — процесс не остановится, потому что множество бесконечно). Значит, $\aleph_0$ — наименьшая бесконечная мощность.
3. Удаление конечного подмножества из счётного множества не меняет его мощности: если $A$ счётно, $K\subset A$ конечно, то $A\setminus K$ счётно. Симметрично: объединение счётного множества с конечным (или счётным) счётно — нумерация $k_1,\dots,k_m,a_1,a_2,\dots$ (или чередование $k_1,a_1,k_2,a_2,\dots$).
4. Декартово произведение счётных множеств счётно: $\mathbb N\times\mathbb N\sim\mathbb N$ — это диагональный метод из §4.6. Явная биекция (нумерующая функция Кантора, обход диагоналей $i+j=\mathrm{const}$ по возрастанию $j$): $\pi(i,j)=\frac{(i+j-1)(i+j-2)}{2}+j.$ По индукции любое конечное произведение $A_1\times\dots\times A_m$ счётных множеств счётно.

4.6. Теорема о счётном объединении

Теорема 9. Счётное объединение счётных множеств счётно: если $A_1,A_2,A_3,\dots$ счётны, то $\displaystyle\bigcup_{k=1}^{\infty}A_k$ счётно.

Доказательство. Пусть $A_k=\{a_{k1},a_{k2},a_{k3},\dots\}$. Запишем все элементы в бесконечную таблицу — строка $k$ содержит множество $A_k$:

a11  a12  a13  a14  ...
a21  a22  a23  a24  ...
a31  a32  a33  ...
a41  a42  ...
...

Нумеруем элементы по диагоналям $i+j=\mathrm{const}$:

• диагональ 1 ($i+j=2$): $a_{11}$;
• диагональ 2 ($i+j=3$): $a_{21},\ a_{12}$;
• диагональ 3 ($i+j=4$): $a_{31},\ a_{22},\ a_{13}$;
• диагональ $d$ ($i+j=d+1$): $a_{d1},\ a_{d-1,2},\ \dots,\ a_{1d}$ — ровно $d$ элементов;
• …

Каждая диагональ конечна, и каждый элемент $a_{ij}$ лежит на диагонали с номером $i+j-1$, поэтому получит конечный номер. Получаем последовательность, содержащую все элементы объединения. Если множества $A_k$ пересекаются, повторы пропускаем (подмножество счётного — н.б.с., свойство 1). Объединение бесконечно (содержит $A_1$), значит счётно. $\blacksquare$

Замечания и следствия.

• Теорема верна и для не более чем счётного семейства не более чем счётных множеств (результат н.б.с.; если он бесконечен — счётен).
• $\mathbb N\times\mathbb N$ счётно; $\mathbb Z$ счётно; $\mathbb Q$ счётно: $\mathbb Q=\bigcup_{q\ge1}\{p/q\mid p\in\mathbb Z\}$ — счётное объединение счётных. Иначе: $\mathbb Q$ — образ счётного множества $\mathbb Z\times\mathbb N$ при отображении $(p,q)\mapsto p/q$, а образ счётного множества не более чем счётен.
• Счётны: множество конечных последовательностей натуральных чисел, множество многочленов с целыми коэффициентами, множество алгебраических чисел.
• Формальная тонкость: чтобы одновременно выбрать нумерации всех $A_k$, используется (счётная) аксиома выбора.

4.7. Несчётность вещественных чисел

Теорема 10. Множество $\mathbb R$ несчётно.

Доказательство — диагональный аргумент Кантора. Достаточно доказать несчётность интервала $(0;1)$: он бесконечен, и если бы $\mathbb R$ было счётно, то его подмножество $(0;1)$ было бы счётным по свойству 1.

Предположим противное: все числа из $(0;1)$ можно выписать в последовательность $x_1,x_2,x_3,\dots$ Запишем их десятичные разложения (для чисел с двумя разложениями, например $0{,}5=0{,}4999\ldots$, фиксируем любое одно): $x_1=0{,}a_{11}a_{12}a_{13}\ldots,\qquad x_2=0{,}a_{21}a_{22}a_{23}\ldots,\qquad x_3=0{,}a_{31}a_{32}a_{33}\ldots,\quad\dots$ Построим число $y=0{,}b_1b_2b_3\ldots$, выбирая $n$-ю цифру отличной от диагональной $a_{nn}$: $b_n=\begin{cases}1,& a_{nn}\ne1,\\ 2,& a_{nn}=1.\end{cases}$ Тогда $y\in(0;1)$ и $y$ отличается от $x_1$ в первой цифре, от $x_2$ — во второй, от $x_n$ — в $n$-й. Значит, $y$ не совпадает ни с одним членом списка, хотя должно было в нём быть. Противоречие. $\blacksquare$

Тонкость с цифрами $0$ и $9$. Число $y$ состоит только из цифр $1$ и $2$, поэтому у него единственное десятичное разложение, и «совпасть с $x_n$ через другую запись» (как $0{,}4999\ldots=0{,}5$) оно не может. Если бы мы выбирали $b_n\in\{0,9\}$, такая ловушка была бы возможна.

Следствия. $|\mathbb R|=\mathfrak c$ — континуум; при этом $(0;1)\sim[0;1]\sim\mathbb R\sim\mathbb R^2$. «Бесконечное» не значит «несчётное»: $\mathbb N$, $\mathbb Z$, $\mathbb Q$ бесконечны и счётны, а $\mathbb R$ несчётно. Из счётности $\mathbb Q$ и несчётности $\mathbb R$ следует, что иррациональных чисел «больше», чем рациональных: множество $\mathbb R\setminus\mathbb Q$ несчётно (иначе $\mathbb R=\mathbb Q\cup(\mathbb R\setminus\mathbb Q)$ было бы счётным объединением счётных).

4.8. Теорема Кантора и лестница мощностей

Через $2^X$ обозначают булеан — множество всех подмножеств $X$. Для конечного $X$ из $n$ элементов $|2^X|=2^n$: каждое подмножество задаётся выбором «берём / не берём» для каждого элемента. Например, у $X=\{1,2\}$ четыре подмножества: $\varnothing$, $\{1\}$, $\{2\}$, $\{1,2\}$. Подробнее о булеане — в лекции 3, где теорема Кантора доказывается ещё раз.

Теорема 11 (Кантора). Для любого множества $X$ не существует сюръекции $X\to2^X$. Следовательно, $|X|<|2^X|$.

По определению 17 неравенство $|X|<|2^X|$ означает две вещи: инъекция $X\to2^X$ есть, а биекции $X\to2^X$ нет. Докажем обе.

Доказательство.

1. Инъекция есть. Положим $\iota(x)=\{x\}$ — каждому элементу сопоставляем одноэлементное подмножество. Если $\{x_1\}=\{x_2\}$, то $x_1\in\{x_2\}$, то есть $x_1=x_2$. Значит, $\iota$ инъективно и $|X|\le|2^X|$.

2. Сюръекции нет. Пусть $f\colon X\to2^X$ — произвольное отображение. Предъявим подмножество $X$, которое не является значением $f$. Каждому $x$ сопоставлено множество $f(x)\subseteq X$, и сам $x$ либо лежит в нём, либо нет. Соберём элементы, которые не лежат в «своём» множестве: $D=\{x\in X\mid x\notin f(x)\}.$ Это подмножество $X$, то есть $D\in2^X$. Докажем, что $D\ne f(d)$ ни при каком $d\in X$. Возьмём любое $d$ и сравним множества $D$ и $f(d)$ в одной точке — в самом $d$:

   • если $d\in f(d)$, то по определению $D$ имеем $d\notin D$;
   • если $d\notin f(d)$, то по определению $D$ имеем $d\in D$.

   В обоих случаях элемент $d$ лежит ровно в одном из множеств $D$ и $f(d)$, поэтому $D\ne f(d)$. Так как $d$ произвольное, $D$ не лежит в образе $f$, и $f$ не сюръективно.

3. Биекции нет. Биекция — в частности сюръекция, а сюръекций по п. 2 нет. Вместе с п. 1 получаем $|X|<|2^X|$. $\blacksquare$

Доказательство не только говорит, что сюръекции нет, но и для любой $f$ указывает конкретное пропущенное подмножество $D$. На лекции тот же аргумент изложен от противного: «пусть $g$ — сюръекция, тогда $D=g(b)$ для некоторого $b$; и $b\in D$, и $b\notin D$ дают противоречие». Это то же рассуждение для одного $d=b$.

Почему приём называется диагональным. Для $X=\mathbb N$ запишем подмножества $f(1),f(2),\dots$ строками таблицы: на пересечении строки $f(n)$ и столбца $k$ стоит $1$, если $k\in f(n)$, и $0$ иначе. Пусть, например, $f(1)$ — нечётные числа, $f(2)=\{2,3\}$, $f(3)=\varnothing$, $f(4)=\mathbb N$:

Строка $D$ — это диагональ, в которой все цифры заменены на противоположные. Поэтому $D$ отличается от строки $f(n)$ в $n$-м столбце и не совпадает ни с одной строкой. Тот же приём доказывает несчётность $\mathbb R$ в §4.7.

Примеры. Для $X=\mathbb N$ найдём $D$ для нескольких $f$ и убедимся, что $D$ действительно пропущено:

1. $f(n)=\{n\}$. Всегда $n\in f(n)$, поэтому $D=\varnothing$. И правда, $\varnothing$ не значение $f$: все значения одноэлементные.
2. $f(n)=\{n+1,n+2,\dots\}$. Всегда $n\notin f(n)$, поэтому $D=\mathbb N$. И правда, $\mathbb N\ne f(n)$: в $f(n)$ нет числа $n$.
3. $f(n)=\{n\}$ при чётном $n$ и $f(n)=\varnothing$ при нечётном. Чётные $n$ лежат в своём $f(n)$, нечётные — нет, поэтому $D$ — множество нечётных чисел. Оно бесконечно, а все значения $f$ содержат не больше одного элемента.
4. $X=\{1,2,3\}$, $f(1)=\{1,2\}$, $f(2)=\{3\}$, $f(3)=\varnothing$. Здесь $1\in f(1)$, $2\notin f(2)$, $3\notin f(3)$, поэтому $D=\{2,3\}$ — его среди значений нет. Конечно, для конечного $X$ сюръекции нет и по подсчёту, $3<2^3=8$. Теорема верна даже для $X=\varnothing$: $2^\varnothing=\{\varnothing\}$, и $0<1$.

Лестница мощностей. Применяя теорему к $2^X$, затем к $2^{2^X}$ и так далее, получаем бесконечную цепочку всё бо́льших мощностей: $|\mathbb N|<|2^{\mathbb N}|<|2^{2^{\mathbb N}}|<\dots$ Наибольшей мощности не существует: если бы у множества $M$ была наибольшая мощность, то $|2^M|>|M|$ противоречило бы этому.

Две строки таблицы требуют доказательства.

Почему $|2^{\mathbb N}|=|\mathbb R|$. Построим две инъекции и применим теорему Кантора–Бернштейна.

• $2^{\mathbb N}\to[0;1]$: подмножеству $S$ сопоставим число $0{,}s_1s_2s_3\ldots$ в троичной записи, где $s_n=1$ при $n\in S$ и $s_n=0$ иначе. Пусть $S\ne T$ и $n$ — наименьший номер, где они различаются. Тогда числа отличаются хотя бы на $3^{-n}-\sum_{k>n}3^{-k}=3^{-n}-\tfrac12\cdot3^{-n}>0$, то есть инъекция есть. В двоичной записи так нельзя: $\{1\}\mapsto0{,}1_2=\tfrac12$ и $\{2,3,4,\dots\}\mapsto0{,}0111\ldots_2=\tfrac12$ — два разных множества дали одно число.
• $(0;1)\to2^{\mathbb N}$: числу $x$ сопоставим множество номеров единиц в его двоичной записи. Если у числа две записи, например $0{,}1_2=0{,}0111\ldots_2$, берём ту, что не оканчивается одними единицами. Разные числа имеют разные записи, поэтому получают разные множества.

Вместе с $[0;1]\sim(0;1)\sim\mathbb R$ получаем $|2^{\mathbb N}|=\mathfrak c$. Это ещё один способ увидеть несчётность $\mathbb R$: $\mathfrak c=|2^{\mathbb N}|>|\mathbb N|$ по теореме Кантора.

Почему функций $\mathbb R\to\mathbb R$ столько же, сколько подмножеств прямой. Инъекция $2^{\mathbb R}\to\{\text{функции}\}$: множеству $S$ сопоставим его индикатор, $\chi_S(x)=1$ при $x\in S$ и $0$ иначе. У разных множеств индикаторы разные. Обратная инъекция: функции $f$ сопоставим её график $\{(x,f(x))\}\subseteq\mathbb R^2$. У разных функций графики разные, а подмножеств плоскости столько же, сколько подмножеств прямой: биекция $\mathbb R^2\to\mathbb R$ переводит подмножества в подмножества. По теореме Кантора–Бернштейна мощность функций равна $2^{\mathfrak c}$, и это строго больше $\mathfrak c$.

Континуум-гипотеза: нет мощности строго между $\aleph_0$ и $\mathfrak c$. В аксиоматике ZFC она недоказуема и неопровержима (Гёдель 1940, Коэн 1963).

4.9. Как доказывать утверждения о мощностях

Мини-примеры.

1. $(0;1)\sim[0;1]$ — две инъекции (§4.3) или явная биекция (§4.4).
2. $(0;1)\sim(0;+\infty)$ — явная биекция $x\mapsto\dfrac{x}{1-x}$.
3. $\mathbb N\sim\mathbb N\times\mathbb N$ — нумерация пар по диагоналям: $(1,1),\,(2,1),\,(1,2),\,(3,1),\,(2,2),\,(1,3),\dots$
4. Множество всех конечных подмножеств $\mathbb N$ счётно (объединение по $m$ счётных множеств $m$-элементных подмножеств), а множество всех подмножеств $\mathbb N$ несчётно (теорема Кантора).

---

Частые ошибки

1. Путать образ $f(X)$ и область прибытия $Y$. Сюръекция требует именно $f(X)=Y$.
2. Доказывать инъективность словами «функция возрастает», не доказав монотонность. Надёжный путь: из $f(x_1)=f(x_2)$ вывести $x_1=x_2$.
3. Проверять для биекции только одно свойство. Нужны и инъективность, и сюръективность — либо предъявить обратное отображение и проверить оба равенства $g\circ f=\mathrm{id}$, $f\circ g=\mathrm{id}$.
4. Писать $S(n)=n+1$ как определение $S$. Наоборот: $S$ дано аксиомами, а сложение определяется через него, $n+1:=S(n)$.
5. Думать, что в модели с лишними элементами можно взять любое $S(a)$. $S(a)=1$ ломает аксиому 3, $S(a)=m\ne1$ из $\mathbb N$ — аксиому 4. Только отдельные циклы и цепочки нарушают одну аксиому 5.
6. В индукции доказывать переход для конкретного $k$. $k$ обязан быть произвольным; «проверил для $n=1,2,3$» — не доказательство.
7. В доказательстве вполне упорядоченности пользоваться «очевидными» свойствами порядка. $1\le n$, $n\not<n$ и дискретность $n<m\Rightarrow n+1\le m$ сами выводятся из аксиом (утверждение 5).
8. Забывать условие $x\ge-1$ в неравенстве Бернулли. Оно нужно, чтобы умножать неравенство на $1+x\ge0$.
9. Сбиваться с показателей в биноме. В слагаемом $C_n^ka^{n-k}b^k$ сумма показателей равна $n$, слагаемых $n+1$, строки треугольника нумеруются с нуля. При $(a-b)^n$ не терять множитель $(-1)^k$, при $(1+2x)^5$ — множитель $2^k$.
10. Путать форму тождества Паскаля. $C_{n+1}^k=C_n^k+C_n^{k-1}$: сверху $n+1$, снизу соседние $k$ и $k-1$ из строки $n$. $C_{n+1}^k=C_n^k+C_{n+1}^{k-1}$ — неверно.
11. Считать, что «бесконечное» = «несчётное». $\mathbb N$, $\mathbb Z$, $\mathbb Q$ бесконечны, но счётны; $\mathbb R$ несчётно.
12. Считать, что собственное подмножество всегда «меньше». Для бесконечных множеств это не так: $\mathbb N\sim2\mathbb N$.

Мини-тренажёр

1. Является ли $f\colon\mathbb Z\to\mathbb Z$, $f(n)=2n+1$, инъекцией? Сюръекцией?
2. Пусть $f(x)=x+1$, $g(x)=x^2$. Найдите $(g\circ f)(x)$ и $(f\circ g)(x)$.
3. Найдите обратное к $f\colon\mathbb R\to\mathbb R$, $f(x)=3x-2$.
4. Модель: $\mathbb N\cup\{a;b\}$, $S(n)=n+1$, $S(a)=b$, $S(b)=b$. Какие аксиомы Пеано нарушены?
5. Докажите по индукции, что $2^n>n$ для всех $n\in\mathbb N$.
6. Для $A=\{5,8,12\}$ выпишите множество $B$ из доказательства теоремы о вполне упорядоченности. Какое $n\in B$ имеет $n+1\notin B$?
7. Оцените снизу $0{,}98^{20}$ по неравенству Бернулли.
8. Найдите $C_8^3$ двумя способами: по формуле и по треугольнику Паскаля из строки $7$.
9. Найдите коэффициент при $a^3b^2$ в $(a+b)^5$ и коэффициент при $x^2$ в $(1-3x)^4$.
10. Вычислите $F_{10}$ и проверьте, что $\varphi^{10}/\sqrt5\approx55{,}0$.
11. Счётно ли множество всех конечных строк из букв русского алфавита?
12. Постройте биекцию между $\mathbb N$ и $\mathbb N\setminus\{1,2,3\}$.
13. Пусть $A=B=\mathbb N$, $f(n)=n+1\colon A\to B$, $g(n)=n+1\colon B\to A$. Разберите цепочки из доказательства Кантора–Бернштейна и выпишите биекцию $h$, которую оно даёт.
14. Для $f\colon\mathbb N\to2^{\mathbb N}$, $f(n)=\{1,2,\dots,n-1\}$ (при $n=1$ пустое множество), найдите множество $D$ из доказательства теоремы Кантора и проверьте, что его нет среди значений $f$.

Ответы

1. Инъекция: из $2n_1+1=2n_2+1$ следует $n_1=n_2$. Не сюръекция: у чётных чисел (например, $0$) прообраза нет.
2. $(g\circ f)(x)=(x+1)^2$, $(f\circ g)(x)=x^2+1$.
3. $f^{-1}(y)=\dfrac{y+2}{3}$; проверка: $f(f^{-1}(y))=3\cdot\dfrac{y+2}{3}-2=y$.
4. Аксиома 4: $S(a)=S(b)=b$ при $a\ne b$. И аксиома 5: $\mathbb N$ содержит $1$ и замкнуто, но не равно всему множеству. Аксиомы 1–3 выполнены.
5. База: $2^1=2>1$. Переход: $2^{k+1}=2\cdot2^k>2k\ge k+1$ при $k\ge1$.
6. $B=\{1,2,3,4\}$ — числа, меньшие всех элементов $A$. $4\in B$, $5\notin B$, и $5$ — наименьший элемент $A$ (случай 2 доказательства).
7. $0{,}98^{20}=(1-0{,}02)^{20}\ge1-20\cdot0{,}02=0{,}6$ (на самом деле $\approx0{,}668$).
8. $C_8^3=\dfrac{8\cdot7\cdot6}{3!}=56$; по треугольнику $C_8^3=C_7^3+C_7^2=35+21=56$.
9. $C_5^2=10$. Во втором: $T_3=C_4^2\cdot(-3x)^2=6\cdot9x^2$, ответ $54$.
10. $F_{10}=55$: $1,1,2,3,5,8,13,21,34,55$. Так как $\varphi^{10}\approx122{,}99$, получаем $\varphi^{10}/\sqrt5\approx55{,}0$, ближайшее целое — $55$.
11. Да: строк длины $m$ конечное число ($33^m$), а объединение по всем $m\in\mathbb N$ — счётное объединение конечных множеств, бесконечное, значит счётное.
12. $n\mapsto n+3$: инъекция (из $n_1+3=n_2+3$ следует $n_1=n_2$) и сюръекция (любое $m\ge4$ есть образ $m-3$).
13. Предок $a\in A$ — число $a-1\in B$ (есть при $a\ge2$), предок $b\in B$ — $b-1\in A$. Путь назад от $a$: $a,\ a-1,\ \dots,\ 1$, множества чередуются, и через $a-1$ шагов он обрывается на единице без предка. При нечётном $a$ шагов чётное число, и единица лежит в $A$ — начало в $A$, $h(a)=f(a)=a+1$. При чётном $a$ единица лежит в $B$ — начало в $B$, $h(a)=g^{-1}(a)=a-1$. Итог: $h$ меняет местами $1\leftrightarrow2$, $3\leftrightarrow4$, $5\leftrightarrow6$, … — биекция, хотя ни $f$, ни $g$ не сюръективны.
14. $n\notin\{1,\dots,n-1\}$ при любом $n$, поэтому $D=\mathbb N$. Все значения $f$ конечны, а $\mathbb N$ бесконечно — его среди них нет.

Шпаргалка