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

Решение:
Долна граница. Точно [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].