\documentclass[a4paper,12pt]{article}

%%% Работа с русским языком
\usepackage{cmap}                   % поиск в PDF
\usepackage{mathtext}               % русские буквы в формулах
\usepackage[T2A]{fontenc}           % кодировка
\usepackage[utf8]{inputenc}         % кодировка исходного текста
\usepackage[english,russian]{babel} % локализация и переносы

%%% Дополнительная работа с математикой
\usepackage{amsmath,amsfonts,amssymb,amsthm,mathtools} % AMS
\usepackage{icomma} % "Умная" запятая: $0,2$ --- число, $0, 2$ --- перечисление

\usepackage{fullpage}

\newcommand{\mP}{\mathcal{P}}
\usepackage{euscript}    % Шрифт Евклид
\usepackage{mathrsfs} % Красивый матшрифт
\usepackage{eufrak}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{indentfirst} % КРАСНАЯ СТРОКА
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}



\usepackage{graphicx}


\input ArtNouvc.fd


\author{ Varenov Andrey, Byvaltseva Anna. }


\title{
\fontsize{8mm}{8mm}\selectfont Discrete mathematics.\\Test №3.}

\date{}


\begin{document}

    \maketitle

    % 1
    \newpage
    \subsection*{1.}
    Предположим, что $\exists A : (A = A \times A) \land (A \not = \varnothing)$, тогда $\exists x : (x \in A) \land (x \in A \times A)$,
    тогда $x = (x_1, x_2), x_1 \in A, x_2 \in A, x_1 \in X, x_2 \in X$. То есть $\forall x \in A \exists y \in A : x \ni y$. Противоречит аксиоме основания.

       \textbf{Ответ} нет, не может.



    % 2
    \newpage
    \subsection*{2.}



    $$R = \varnothing, P = \{1, 2\}, Q = \varnothing$$
    $$P \cdot R = \varnothing = Q \cdot R $$
    \textbf{Ответ:} нет, не слудует.

    % 3
    \newpage
    \subsection*{3.}
    Пусть $$ Q = \{ (k, k + 1) \in \N^2 \mid k \in \N \} \cup \{(0,0), (1,0)\} $$
    $$ P = \{ (k + 1, k) \in \N^2 \mid k \in \N \} $$

    Тогда $Q$ не инъективно ($\exists y = 0 : 0Qy \land 1Qy $), но это не влияет на композицию, т.к. в P нет ничего начинающегося с нуля, поэтому $P \circ Q = id_A $.

    \textbf{Ответ: }нет, не обязательно.

    % 4
    \newpage
    \subsection*{4.}
    Обозначим за $X$ множество беспорядков $\N \rightarrow \N$. Во-первых, $X \lesssim 2^\N$ так как множество беспорядков на $\N$ это подмножество отображений $\N \rightarrow \N$.

    Теперь рассмотрим множество последовательностей из нулей и единиц. Таких последовательностей $2^\N$, так как каждая последовательность есть по сути оторбражение $\N \rightarrow \N$.

    Докажем, что $X$ не менее мощно, чем множество таких последовательностей. Сопоставим каждой последовательности беспорядок следующим образом: нулю будет соответствовать цикл длины $2$, а единице цикл длины $3$. То есть $0101 \ldots \leftrightarrow (0, 1)(2, 3, 4)(5, 6)(7, 8, 9) \ldots $

    Следовательно $X \gtrsim 2^\N $.
    По теореме Кантора-Бернштейна-Шрёдера $X \simeq 2^\N \simeq R$

    % 5
    \newpage
    \subsection*{5.}
    $$B \sim B \setminus \{x\} \Longleftrightarrow \exists f- биекция: B \to B \setminus \{x\}  $$

     Докажем, что $B$ бесконечно.

     Пусть $B$ конечно. Тогда данная биекция $f$ из $B$ в $B \setminus \{x\}$ является инъекцией, но НЕ сюръекцией $B \to B$. На лекции формулировалось, что любая биекция между равномощными конечными множествами есть сюръекция. Противоречие.

     Итак, $B$ бесконечно. На лекции формулировалось, что  тогда $\N$ вкладывается в $B$. По определению конечности: $\exists m \in \N: A \sim \underline{m} $ . Последнее множество включено, а значит, и вкладывается в $\N$. Тогда, по транзитивности, A $\lesssim$ B.

     \textbf{Ответ:} всегда.
    % 6
    \newpage
    \subsection*{6.}
    Последовательность биективно кодируется набором, состоящим из множества B (фиксированного размера $b$), его подмножества $A$ размера $a$ и $k + 1$ множества \\ $(C_1 \setminus A, C_2 \setminus С_1, \ldots, C_k \setminus C_{k - 1}, B \setminus C_k)$.

    Понятно, что количество способов задать мн-во $B$ равно $C_n^b$, а мн-во $A$~--- $C_b^a$ соотвественно.
    Осталось посчитать кол-во упорядоченных разбиений $B \setminus A$ на $k + 1$ кусок (без ограничений мощности).

    Разбиение на $k + 1$ кусок кодируется функцией $B \setminus A \to \underline{k + 1}$. При любом выборе A и B таких функций будет $(k + 1)^{b - a}$. Итого, $C_n^b \cdot C_a^b \cdot (k + 1)^{b - a}$.

    \textbf{Ответ:} $$C_n^b \cdot C_a^b \cdot (k + 1)^{b - a}$$

    % 7
    \newpage
    \subsection*{7.}

    $G_n = \sum_{k=0}^{n} C_{n - k}^k =  \sum_{k=0}^{n} \left(C_{n - k - 1}^k + C_{n - k - 1}^{k - 1}\right) = \sum_{k=0}^{n} C_{n - k - 1}^k + \sum_{k=0}^{n} C_{n - k - 1}^{k - 1} = \left( \sum_{k=0}^{n - 1} C_{n - k - 1}^k + C_{-1}^n \right) + \left( C_{n - 1}^{ - 1} + \sum_{k=1}^{n-2} C_{n - k - 1}^{k - 1} + C_{-1}^{n - 1}\right) = \left( \sum_{k=0}^{n - 1} C_{n - k - 1}^k + 0 \right) + \left( 0 + \sum_{k=1}^{n-2} C_{n - k - 1}^{k - 1} + 0\right) = \sum_{k=0}^{n - 1} C_{n - k - 1}^k + \sum_{k=0}^{n-2} C_{n - k - 1}^{k} = G_{n-1} + G_{n-2}$
    Получается, что последовательность $G_i$ задается таким же рекурентным соотношением, как и последовательность чисел $F_i$, кроме того начальные значения $G_0 = F_1 = 1 $ и $ G_1 = F_2 = 1$ а значит последовательности совпадают по индукции. Q.E.D.

    % 8
    \newpage
    \subsection*{8.}
    $A \cup B \simeq \R \simeq \R \times \R \simeq [0, 1] \times [0, 1]$ то есть существует биекция между $A \cup B$ и квадратиком на плоскости.
    Раскрасим все точки квадратика, которые соответствуют $A \setminus B$
    Возможны 2 варианта: или есть вертикальный отрезочек квадрата такой, что он полностью раскрашен или на каждом вертикальном отрезке есть незакрашеная точка. В первом случае $A \gtrsim A \setminus B \gtrsim \R$, во втором $B \gtrsim A$
    Так как $A, B \subseteq \R$, то $A \lesssim \R$ и $B \lesssim \R$
    По теореме Кантора-Бернштейна-Шрёдера $A \simeq R$ или $B \simeq R$ Q.E.D.

\end{document}