Математическая логика и теория множеств - очень сложные задачи с решениями

Решение:
Оценка снизу. Ровно [tex]20 - 17 = 3[/tex] элемента множества [tex]A \cup B \cup C[/tex] не лежат в [tex]C[/tex], поэтому [tex]|A \setminus C| \le 3[/tex] и [tex]|B \setminus C| \le 3[/tex]. Следовательно,
[tex]|A \cap C| = |A| - |A \setminus C| \ge 15 - 3 = 12, \qquad |B \cap C| = |B| - |B \setminus C| \ge 10 - 3 = 7[/tex]
Множества [tex]A \cap C[/tex] и [tex]B \cap C[/tex] содержатся в [tex]C[/tex], поэтому их объединение содержит не более [tex]17[/tex] элементов, а их пересечение равно [tex]A \cap B \cap C[/tex]. Следовательно,
[tex]|A \cap B \cap C| = |A \cap C| + |B \cap C| - |(A \cap C) \cup (B \cap C)| \ge 12 + 7 - 17 = 2[/tex]
Оценка достигается, например, для множеств
[tex]A = \{1 ; \ldots ; 12\} \cup \{18 ; 19 ; 20\}, \quad B = \{11 ; \ldots ; 17\} \cup \{18 ; 19 ; 20\}, \quad C = \{1 ; \ldots ; 17\}[/tex]
Здесь [tex]|A| = 15[/tex], [tex]|B| = 10[/tex], [tex]|C| = 17[/tex], [tex]A \cup B \cup C = \{1 ; \ldots ; 20\}[/tex] и [tex]A \cap B \cap C = \{11 ; 12\}[/tex]. Значит, наименьшее возможное число равно [tex]2[/tex].

Решение:
Обозначим произведение через [tex]P[/tex]. Каждое [tex]A_n[/tex] бесконечно и счётно, поэтому его элементы можно занумеровать без повторений:
[tex]A_n = \{a_{n,1}, a_{n,2}, a_{n,3}, \ldots\}, \qquad a_{n,1} \ne a_{n,2}[/tex]
Предположим, что [tex]P[/tex] счётно. Оно непусто (содержит [tex](a_{1,1}, a_{2,1}, a_{3,1}, \ldots)[/tex]), поэтому его элементы можно выписать в последовательность (повторения допускаются)
[tex]x^{(1)}, x^{(2)}, x^{(3)}, \ldots, \qquad x^{(k)} = \left(x^{(k)}_1, x^{(k)}_2, x^{(k)}_3, \ldots\right)[/tex]
Применим диагональный метод Кантора: для каждого [tex]n[/tex] положим [tex]y_n = a_{n,2}[/tex], если [tex]x^{(n)}_n = a_{n,1}[/tex], и [tex]y_n = a_{n,1}[/tex], если [tex]x^{(n)}_n \ne a_{n,1}[/tex]. Пусть [tex]y = (y_1, y_2, y_3, \ldots)[/tex]. Тогда [tex]y_n \in A_n[/tex] при каждом [tex]n[/tex], значит, [tex]y \in P[/tex].
С другой стороны, [tex]y_n \ne x^{(n)}_n[/tex] при каждом [tex]n[/tex], т.е. [tex]y[/tex] отличается от [tex]x^{(n)}[/tex] в [tex]n[/tex]-й координате. Поэтому [tex]y \ne x^{(n)}[/tex] ни при каком [tex]n[/tex], т.е. [tex]y[/tex] отсутствует в последовательности — противоречие. Следовательно, [tex]P[/tex] несчётно.

Решение:
Построим [tex]F[/tex] как композицию трёх биекций.
Шаг 1. Линейная функция [tex]\varphi(x) = \frac{x-a}{b-a}[/tex] — биекция [tex]\left[a ; b\right][/tex] на [tex]\left[0 ; 1\right][/tex]: она строго возрастает (так как [tex]b - a \gt 0[/tex]), [tex]\varphi(a) = 0[/tex], [tex]\varphi(b) = 1[/tex], а обратная к ней функция — [tex]t \mapsto a + (b-a)t[/tex].
Шаг 2. Биекция [tex]g\colon \left[0 ; 1\right] \to \left(0 ; 1\right)[/tex] (удаление двух концов). Сдвинем последовательность [tex]0 ; 1 ; \frac{1}{2} ; \frac{1}{3} ; \frac{1}{4} ; \ldots[/tex] на две позиции вперёд, а все остальные точки оставим на месте:
[tex]g(0) = \frac{1}{2}, \qquad g(1) = \frac{1}{3}, \qquad g\left(\frac{1}{n}\right) = \frac{1}{n+2} \quad (n \ge 2)[/tex]
и [tex]g(x) = x[/tex] для всех остальных [tex]x \in \left[0 ; 1\right][/tex]. Множество [tex]S = \left\{0 ; 1 ; \frac{1}{2} ; \frac{1}{3} ; \ldots\right\}[/tex] отображается биективно на [tex]S' = \left\{\frac{1}{2} ; \frac{1}{3} ; \ldots\right\}[/tex] (член последовательности с номером [tex]k[/tex] переходит в член с номером [tex]k + 2[/tex]), а множество [tex]\left[0 ; 1\right] \setminus S[/tex] отображается тождественно на себя, и оно совпадает с [tex]\left(0 ; 1\right) \setminus S'[/tex]. Так как [tex]S'[/tex] и [tex]\left(0 ; 1\right) \setminus S'[/tex] не пересекаются и их объединение есть [tex]\left(0 ; 1\right)[/tex], функция [tex]g[/tex] — биекция.
Шаг 3. Функция [tex]h(t) = \operatorname{tg} \left(\pi\left(t - \frac{1}{2}\right)\right)[/tex] — биекция [tex]\left(0 ; 1\right)[/tex] на [tex]\mathbb{R}[/tex]. Когда [tex]t[/tex] пробегает [tex]\left(0 ; 1\right)[/tex], аргумент [tex]\pi\left(t - \frac{1}{2}\right)[/tex] пробегает [tex]\left(-\frac{\pi}{2} ; \frac{\pi}{2}\right)[/tex], где тангенс непрерывен и строго возрастает, поэтому [tex]h[/tex] инъективна. Кроме того, [tex]h(t) \to -\infty[/tex] при [tex]t \to 0^+[/tex] и [tex]h(t) \to +\infty[/tex] при [tex]t \to 1^-[/tex], поэтому по теореме о промежуточном значении [tex]h[/tex] принимает все действительные значения.
Следовательно, [tex]F = h \circ g \circ \varphi\colon \left[a ; b\right] \to \mathbb{R}[/tex] — композиция биекций, а значит, биекция.

Решение:
Воспользуемся теоремой Кантора–Шрёдера–Бернштейна: если существуют инъекции [tex]X \to Y[/tex] и [tex]Y \to X[/tex], то между [tex]X[/tex] и [tex]Y[/tex] существует биекция. Инъекция [tex]\left[a ; b\right] \to \mathbb{R}^2[/tex] очевидна: [tex]t \mapsto (t ; 0)[/tex]. Осталось построить инъекцию [tex]\mathbb{R}^2 \to \left[a ; b\right][/tex]; получим её как композицию трёх инъекций.
Шаг 1. Функция [tex]\psi(x) = \frac{1}{1 + e^{-x}}[/tex] строго возрастает и принимает значения в [tex]\left(0 ; 1\right)[/tex], так как [tex]1 + e^{-x}[/tex] строго убывает и больше [tex]1[/tex]. Поэтому [tex](x ; y) \mapsto (\psi(x) ; \psi(y))[/tex] — инъекция [tex]\mathbb{R}^2 \to \left(0 ; 1\right)^2[/tex].
Шаг 2. Каждое [tex]u \in \left(0 ; 1\right)[/tex] имеет единственную десятичную запись [tex]u = 0{,}u_1u_2u_3\ldots[/tex], не оканчивающуюся бесконечной серией девяток. Для [tex](u ; v) \in \left(0 ; 1\right)^2[/tex] с такими записями [tex]u = 0{,}u_1u_2u_3\ldots[/tex] и [tex]v = 0{,}v_1v_2v_3\ldots[/tex] чередуем цифры:
[tex]D(u, v) = 0{,}u_1v_1u_2v_2u_3v_3\ldots[/tex]
Эта последовательность цифр не оканчивается бесконечной серией девяток (иначе цифры [tex]u[/tex] были бы девятками начиная с некоторого места), поэтому она является стандартной десятичной записью числа [tex]D(u, v) \in \left[0 ; 1\right)[/tex]. Если [tex](u ; v) \ne (u' ; v')[/tex], то записи [tex]u[/tex] и [tex]u'[/tex] или записи [tex]v[/tex] и [tex]v'[/tex] различаются в некоторой цифре, поэтому различаются и полученные последовательности. Две различные последовательности цифр, не оканчивающиеся бесконечными сериями девяток, задают различные числа, следовательно, [tex]D\colon \left(0 ; 1\right)^2 \to \left[0 ; 1\right)[/tex] — инъекция.
Шаг 3. Функция [tex]t \mapsto a + (b-a)t[/tex] — инъекция [tex]\left[0 ; 1\right) \to \left[a ; b\right][/tex], так как [tex]b - a \gt 0[/tex].
Композиция инъекций из шагов 1, 2 и 3 — инъекция [tex]\mathbb{R}^2 \to \left[a ; b\right][/tex]. По теореме Кантора–Шрёдера–Бернштейна между [tex]\left[a ; b\right][/tex] и [tex]\mathbb{R}^2[/tex] существует биекция, т.е. отрезок и плоскость равномощны.

Решение:
Пусть [tex]\sim[/tex] — конгруэнция и [tex]H = \{x \in \mathbb{Z} \mid x \sim 0\}[/tex] — класс числа [tex]0[/tex].
Шаг 1: [tex]x \sim y \Leftrightarrow x - y \in H[/tex]. Действительно, если [tex]x \sim y[/tex], то, прибавив [tex]a = -y[/tex], получим [tex]x - y \sim 0[/tex]; обратно, если [tex]x - y \sim 0[/tex], то, прибавив [tex]a = y[/tex], получим [tex]x \sim y[/tex].
Шаг 2: [tex]H[/tex] — подгруппа [tex](\mathbb{Z}, +)[/tex]. По рефлексивности [tex]0 \in H[/tex]. Если [tex]x, y \in H[/tex], то [tex]x \sim 0[/tex] и, по симметричности, [tex]0 \sim y[/tex]; по транзитивности [tex]x \sim y[/tex], т.е. [tex]x - y \in H[/tex] согласно шагу 1. Следовательно, [tex]-y = 0 - y \in H[/tex] и [tex]x + y = x - (-y) \in H[/tex].
Шаг 3: [tex]H = q\mathbb{Z}[/tex] для некоторого целого [tex]q \ge 0[/tex]. Если [tex]H = \{0\}[/tex], возьмём [tex]q = 0[/tex]. Иначе [tex]H[/tex] содержит ненулевой элемент вместе с противоположным, а значит, и положительный элемент; пусть [tex]q[/tex] — наименьший положительный элемент [tex]H[/tex]. По шагу 2 все кратные [tex]kq[/tex], [tex]k \in \mathbb{Z}[/tex], лежат в [tex]H[/tex]. Для любого [tex]h \in H[/tex] деление с остатком даёт [tex]h = kq + r[/tex], где [tex]0 \le r \lt q[/tex]; тогда [tex]r = h - kq \in H[/tex], и из минимальности [tex]q[/tex] следует [tex]r = 0[/tex]. Итак, [tex]H = q\mathbb{Z}[/tex].
Шаг 4: по шагу 1 [tex]x \sim y \Leftrightarrow x - y \in q\mathbb{Z}[/tex]. Если [tex]q = 0[/tex], это означает [tex]x = y[/tex], т.е. [tex]\sim[/tex] совпадает с [tex]\Delta_{\mathbb{Z}}[/tex]. Если [tex]q \ge 1[/tex], это означает [tex]q \mid x - y[/tex], т.е. [tex]\sim[/tex] совпадает с [tex]\equiv_q[/tex].

Решение:
Шаг 1. Для позиций [tex]i, j \in \{1 ; 2 ; \ldots ; n\}[/tex] будем писать [tex]i \approx j[/tex], если [tex]s_i = s_j[/tex] для каждого [tex]s \in S[/tex]. Это отношение эквивалентности на множестве позиций; пусть [tex]C_1, \ldots, C_k[/tex] — его классы, так что [tex]1 \le k \le n[/tex]. Пусть [tex]T[/tex] — множество строк, постоянных на каждом классе. Такая строка определяется независимым выбором [tex]0[/tex] или [tex]1[/tex] на каждом классе, поэтому [tex]|T| = 2^k[/tex]. Докажем, что [tex]\bar{S} = T[/tex].
Шаг 2. [tex]\bar{S} \subseteq T[/tex]. Каждая строка [tex]s \in S[/tex] постоянна на каждом классе по определению [tex]\approx[/tex]. Если [tex]u[/tex] и [tex]v[/tex] постоянны на классе [tex]C[/tex], то такими же являются [tex]u \wedge v[/tex], [tex]u \vee v[/tex] и [tex]\neg u[/tex], поскольку операции действуют покомпонентно; например, для [tex]i, j \in C[/tex]
[tex](u \wedge v)_i = u_i \wedge v_i = u_j \wedge v_j = (u \wedge v)_j[/tex]
Индукцией по числу применённых операций получаем, что каждый элемент [tex]\bar{S}[/tex] лежит в [tex]T[/tex].
Шаг 3. [tex]T \subseteq \bar{S}[/tex]. Зафиксируем [tex]s \in S[/tex] (это возможно, так как [tex]S \ne \varnothing[/tex]); тогда строка из одних нулей [tex]\mathbf{0} = s \wedge \neg s[/tex] и строка из одних единиц [tex]\mathbf{1} = s \vee \neg s[/tex] принадлежат [tex]\bar{S}[/tex].
Зафиксируем класс [tex]C[/tex] и позицию [tex]i \in C[/tex]. Для каждой позиции [tex]j \notin C[/tex] имеем [tex]i \not\approx j[/tex], поэтому найдётся [tex]s \in S[/tex] с [tex]s_i \ne s_j[/tex]; положим [tex]t^{(j)} = s[/tex], если [tex]s_i = 1[/tex], и [tex]t^{(j)} = \neg s[/tex], если [tex]s_i = 0[/tex]. Тогда [tex]t^{(j)} \in \bar{S}[/tex], [tex]t^{(j)}_i = 1[/tex] и [tex]t^{(j)}_j = 0[/tex]. Положим
[tex]e_C = \mathbf{1} \wedge \bigwedge_{j \notin C} t^{(j)}[/tex]
(если [tex]C[/tex] содержит все позиции, то [tex]e_C = \mathbf{1}[/tex]). Тогда [tex]e_C \in \bar{S}[/tex]; эта строка имеет [tex]0[/tex] на каждой позиции вне [tex]C[/tex] и [tex]1[/tex] на позиции [tex]i[/tex]. Так как по шагу 2 [tex]e_C \in T[/tex], она равна [tex]1[/tex] на всём классе [tex]C[/tex]. Значит, [tex]e_C[/tex] — это в точности строка с единицами на [tex]C[/tex] и нулями на остальных позициях.
Наконец, каждая строка [tex]u \in T[/tex] равна [tex]1[/tex] ровно на объединении некоторых классов, поэтому [tex]u[/tex] — дизъюнкция соответствующих строк [tex]e_C[/tex] (или [tex]u = \mathbf{0}[/tex], если таких классов нет); следовательно, [tex]u \in \bar{S}[/tex]. Итак, [tex]\bar{S} = T[/tex] и [tex]|\bar{S}| = 2^k[/tex], где [tex]1 \le k \le n[/tex].