Введение

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

Запишите формальные описания следующих множеств.

Пусть $A$ — множество $\left\{ \mathrm{x}, \mathrm{y}, \mathrm{z}\right\}$, а $B$ — множество $\left\{ \mathrm{x}, \mathrm{y}\right\}$.

Если $A$ содержит $a$ элементов, а $B$ содержит $b$ элементов, сколько элементов в $A \times B$? Обоснуйте свой ответ.

Если $C$ — множество из $c$ элементов, сколько элементов в множестве всех подмножеств $C$? Обоснуйте свой ответ.

Пусть $X$ — множество $\left\{ 1,2,3,4,5\right\}$, а $Y$ — множество $\left\{ 6,7,8,9,10\right\}$. Унарная функция $f: X \longrightarrow Y$ и бинарная функция $g: X \times Y \longrightarrow Y$ описаны в следующих таблицах.

Для каждого пункта приведите отношение, удовлетворяющее указанному условию.

Рассмотрим неориентированный граф $G=(V, E)$, где $V$ — множество вершин, равное $\left\{ 1,2,3,4\right\}$, а $E$ — множество рёбер, равное $\left\{ \left\{ 1,2\right\} ,\left\{ 2,3\right\} ,\left\{ 1,3\right\} ,\left\{ 2,4\right\} ,\left\{ 1,4\right\} \right\}$. Нарисуйте граф $G$. Чему равны степени каждой вершины? Отметьте на своём рисунке графа $G$ путь из вершины 3 в вершину 4.

Запишите формальное описание следующего графа.

Найдите ошибку в следующем доказательстве того, что $2=1$. Рассмотрим уравнение $a=b$. Умножим обе части на $a$, получим $a^{2}=a b$. Вычтем $b^{2}$ из обеих частей и получим $a^{2}-b^{2}=a b-b^{2}$. Теперь разложим на множители обе части, $(a+b)(a-b)=b(a-b)$, и разделим каждую часть на $(a-b)$, получим $a+b=b$. Наконец, положим $a$ и $b$ равными 1, откуда следует, что $2=1$.

Пусть $S(n)=1+2+\cdots +n$ — сумма первых $n$ натуральных чисел, а $C(n)=1^{3}+2^{3}+\cdots +n^{3}$ — сумма первых $n$ кубов. Докажите следующие равенства индукцией по $n$, чтобы прийти к любопытному выводу, что $C(n)=S^{2}(n)$ для каждого $n$.

Найдите ошибку в следующем доказательстве того, что все лошади одного цвета. Утверждение: В любом множестве из $h$ лошадей все лошади одного цвета. Доказательство: Индукцией по $h$. База: При $h=1$. В любом множестве, содержащем ровно одну лошадь, все лошади, очевидно, одного цвета. Индукционный переход: Для $k \geq 1$ предположим, что утверждение верно при $h=k$, и докажем, что оно верно при $h=k+1$. Возьмём произвольное множество $H$ из $k+1$ лошадей. Покажем, что все лошади в этом множестве одного цвета. Уберём одну лошадь из этого множества, получив множество $H_{1}$ ровно из $k$ лошадей. По индукционному предположению все лошади в $H_{1}$ одного цвета. Теперь вернём убранную лошадь обратно и уберём другую, получив множество $H_{2}$. По тому же рассуждению все лошади в $H_{2}$ одного цвета. Следовательно, все лошади в $H$ должны быть одного цвета, и доказательство завершено.

Покажите, что любой граф с двумя или более вершинами содержит две вершины одинаковой степени.

• Теорема Рамсея. Пусть $G$ — граф. Кликой в $G$ называется подграф, в котором каждые две вершины соединены ребром. Антиклика, также называемая независимым множеством, — это подграф, в котором никакие две вершины не соединены ребром. Покажите, что любой граф с $n$ вершинами содержит либо клику, либо антиклику, имеющую как минимум $\frac{1}{2} \log_{2} n$ вершин.

Используя теорему 0.25, выведите формулу для вычисления размера ежемесячного платежа по ипотеке через основную сумму долга $P$, процентную ставку $I$ и число платежей $t$. Считайте, что после $t$ платежей сумма долга уменьшается до 0. С помощью этой формулы вычислите сумму в долларах каждого ежемесячного платежа для 30-летней ипотеки с 360 ежемесячными платежами при начальной сумме долга $100,000 и годовой процентной ставке 5.