Mathematical Logic and Set Theory: Very Difficult Problems with Solutions

Solution:
Lower bound. Exactly [tex]20 - 17 = 3[/tex] elements of [tex]A \cup B \cup C[/tex] lie outside [tex]C[/tex], so [tex]|A \setminus C| \le 3[/tex] and [tex]|B \setminus C| \le 3[/tex]. Hence
[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]
The sets [tex]A \cap C[/tex] and [tex]B \cap C[/tex] are subsets of [tex]C[/tex], so their union has at most [tex]17[/tex] elements, and their intersection is [tex]A \cap B \cap C[/tex]. Therefore
[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]
The bound is attained, for example, for the sets
[tex]A = \{1 , \ldots , 12\} \cup \{18 , 19 , 20\}, \quad B = \{11 , \ldots , 17\} \cup \{18 , 19 , 20\}, \quad C = \{1 , \ldots , 17\}[/tex]
Here [tex]|A| = 15[/tex], [tex]|B| = 10[/tex], [tex]|C| = 17[/tex], [tex]A \cup B \cup C = \{1 , \ldots , 20\}[/tex] and [tex]A \cap B \cap C = \{11 , 12\}[/tex]. Hence the smallest possible number is [tex]2[/tex].

Solution:
Denote the product by [tex]P[/tex]. Each [tex]A_n[/tex] is countably infinite, so we can enumerate its elements without repetitions:
[tex]A_n = \{a_{n,1}, a_{n,2}, a_{n,3}, \ldots\}, \qquad a_{n,1} \ne a_{n,2}[/tex]
Assume that [tex]P[/tex] is countable. It is non-empty (it contains [tex](a_{1,1}, a_{2,1}, a_{3,1}, \ldots)[/tex]), so its elements can be listed in a sequence (repetitions allowed)
[tex]x^{(1)}, x^{(2)}, x^{(3)}, \ldots, \qquad x^{(k)} = \left(x^{(k)}_1, x^{(k)}_2, x^{(k)}_3, \ldots\right)[/tex]
We use Cantor's diagonal argument: for every [tex]n[/tex] put [tex]y_n = a_{n,2}[/tex] if [tex]x^{(n)}_n = a_{n,1}[/tex], and [tex]y_n = a_{n,1}[/tex] if [tex]x^{(n)}_n \ne a_{n,1}[/tex]. Let [tex]y = (y_1, y_2, y_3, \ldots)[/tex]. Then [tex]y_n \in A_n[/tex] for every [tex]n[/tex], so [tex]y \in P[/tex].
On the other hand, [tex]y_n \ne x^{(n)}_n[/tex] for every [tex]n[/tex], i.e. [tex]y[/tex] differs from [tex]x^{(n)}[/tex] in the [tex]n[/tex]-th coordinate. Hence [tex]y \ne x^{(n)}[/tex] for all [tex]n[/tex], so [tex]y[/tex] is missing from the list, a contradiction. Therefore [tex]P[/tex] is uncountable.

Solution:
We build [tex]F[/tex] as a composition of three bijections.
Step 1. The linear function [tex]\varphi(x) = \frac{x-a}{b-a}[/tex] is a bijection of [tex]\left[a , b\right][/tex] onto [tex]\left[0 , 1\right][/tex]: it is strictly increasing (since [tex]b - a \gt 0[/tex]), [tex]\varphi(a) = 0[/tex], [tex]\varphi(b) = 1[/tex], and its inverse is [tex]t \mapsto a + (b-a)t[/tex].
Step 2. A bijection [tex]g\colon \left[0 , 1\right] \to \left(0 , 1\right)[/tex] (removing the two endpoints). We shift the sequence [tex]0 , 1 , \frac{1}{2} , \frac{1}{3} , \frac{1}{4} , \ldots[/tex] two places forward and leave all other points fixed:
[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]
and [tex]g(x) = x[/tex] for every other [tex]x \in \left[0 , 1\right][/tex]. The set [tex]S = \left\{0 , 1 , \frac{1}{2} , \frac{1}{3} , \ldots\right\}[/tex] is mapped bijectively onto [tex]S' = \left\{\frac{1}{2} , \frac{1}{3} , \ldots\right\}[/tex] (the term number [tex]k[/tex] of the sequence goes to the term number [tex]k + 2[/tex]), and the set [tex]\left[0 , 1\right] \setminus S[/tex] is mapped identically onto itself; this set equals [tex]\left(0 , 1\right) \setminus S'[/tex]. Since [tex]S'[/tex] and [tex]\left(0 , 1\right) \setminus S'[/tex] are disjoint and their union is [tex]\left(0 , 1\right)[/tex], the function [tex]g[/tex] is a bijection.
Step 3. The function [tex]h(t) = \tan \left(\pi\left(t - \frac{1}{2}\right)\right)[/tex] is a bijection of [tex]\left(0 , 1\right)[/tex] onto [tex]\mathbb{R}[/tex]. When [tex]t[/tex] runs over [tex]\left(0 , 1\right)[/tex], the argument [tex]\pi\left(t - \frac{1}{2}\right)[/tex] runs over [tex]\left(-\frac{\pi}{2} , \frac{\pi}{2}\right)[/tex], where the tangent is continuous and strictly increasing, so [tex]h[/tex] is injective. Moreover, [tex]h(t) \to -\infty[/tex] as [tex]t \to 0^+[/tex] and [tex]h(t) \to +\infty[/tex] as [tex]t \to 1^-[/tex], so by the intermediate value theorem [tex]h[/tex] takes every real value.
Hence [tex]F = h \circ g \circ \varphi\colon \left[a , b\right] \to \mathbb{R}[/tex] is a composition of bijections, and therefore a bijection.

Solution:
We use the Cantor–Schröder–Bernstein theorem: if there are an injection [tex]X \to Y[/tex] and an injection [tex]Y \to X[/tex], then there is a bijection between [tex]X[/tex] and [tex]Y[/tex]. An injection [tex]\left[a , b\right] \to \mathbb{R}^2[/tex] is obvious: [tex]t \mapsto (t , 0)[/tex]. It remains to construct an injection [tex]\mathbb{R}^2 \to \left[a , b\right][/tex]; we obtain it as a composition of three injections.
Step 1. The function [tex]\psi(x) = \frac{1}{1 + e^{-x}}[/tex] is strictly increasing and takes values in [tex]\left(0 , 1\right)[/tex], because [tex]1 + e^{-x}[/tex] is strictly decreasing and greater than [tex]1[/tex]. Hence [tex](x , y) \mapsto (\psi(x) , \psi(y))[/tex] is an injection [tex]\mathbb{R}^2 \to \left(0 , 1\right)^2[/tex].
Step 2. Every [tex]u \in \left(0 , 1\right)[/tex] has a unique decimal expansion [tex]u = 0.u_1u_2u_3\ldots[/tex] that does not end with an infinite run of nines. For [tex](u , v) \in \left(0 , 1\right)^2[/tex] with such expansions [tex]u = 0.u_1u_2u_3\ldots[/tex] and [tex]v = 0.v_1v_2v_3\ldots[/tex] we interleave the digits:
[tex]D(u, v) = 0.u_1v_1u_2v_2u_3v_3\ldots[/tex]
This digit sequence does not end with an infinite run of nines (otherwise the digits of [tex]u[/tex] would be nines from some place on), so it is the standard expansion of the number [tex]D(u, v) \in \left[0 , 1\right)[/tex]. If [tex](u , v) \ne (u' , v')[/tex], then the expansions of [tex]u[/tex] and [tex]u'[/tex], or those of [tex]v[/tex] and [tex]v'[/tex], differ in some digit, so the interleaved sequences differ too. Two different digit sequences that do not end with infinite runs of nines represent different numbers, hence [tex]D\colon \left(0 , 1\right)^2 \to \left[0 , 1\right)[/tex] is injective.
Step 3. The function [tex]t \mapsto a + (b-a)t[/tex] is an injection [tex]\left[0 , 1\right) \to \left[a , b\right][/tex], since [tex]b - a \gt 0[/tex].
The composition of the injections from Steps 1, 2 and 3 is an injection [tex]\mathbb{R}^2 \to \left[a , b\right][/tex]. By the Cantor–Schröder–Bernstein theorem there is a bijection between [tex]\left[a , b\right][/tex] and [tex]\mathbb{R}^2[/tex], i.e. the segment and the plane have the same cardinality.

Solution:
Let [tex]\sim[/tex] be a congruence and let [tex]H = \{x \in \mathbb{Z} \mid x \sim 0\}[/tex] be the class of [tex]0[/tex].
Step 1: [tex]x \sim y \Leftrightarrow x - y \in H[/tex]. Indeed, if [tex]x \sim y[/tex], adding [tex]a = -y[/tex] gives [tex]x - y \sim 0[/tex]; conversely, if [tex]x - y \sim 0[/tex], adding [tex]a = y[/tex] gives [tex]x \sim y[/tex].
Step 2: [tex]H[/tex] is a subgroup of [tex](\mathbb{Z}, +)[/tex]. By reflexivity, [tex]0 \in H[/tex]. If [tex]x, y \in H[/tex], then [tex]x \sim 0[/tex] and, by symmetry, [tex]0 \sim y[/tex]; by transitivity [tex]x \sim y[/tex], i.e. [tex]x - y \in H[/tex] by Step 1. Consequently [tex]-y = 0 - y \in H[/tex] and [tex]x + y = x - (-y) \in H[/tex].
Step 3: [tex]H = q\mathbb{Z}[/tex] for some integer [tex]q \ge 0[/tex]. If [tex]H = \{0\}[/tex], take [tex]q = 0[/tex]. Otherwise [tex]H[/tex] contains a non-zero element together with its opposite, hence a positive element; let [tex]q[/tex] be the smallest positive element of [tex]H[/tex]. By Step 2 all multiples [tex]kq[/tex], [tex]k \in \mathbb{Z}[/tex], belong to [tex]H[/tex]. For any [tex]h \in H[/tex], division with remainder gives [tex]h = kq + r[/tex] with [tex]0 \le r \lt q[/tex]; then [tex]r = h - kq \in H[/tex], and the minimality of [tex]q[/tex] forces [tex]r = 0[/tex]. So [tex]H = q\mathbb{Z}[/tex].
Step 4: by Step 1, [tex]x \sim y \Leftrightarrow x - y \in q\mathbb{Z}[/tex]. If [tex]q = 0[/tex], this means [tex]x = y[/tex], so [tex]\sim[/tex] coincides with [tex]\Delta_{\mathbb{Z}}[/tex]. If [tex]q \ge 1[/tex], it means [tex]q \mid x - y[/tex], so [tex]\sim[/tex] coincides with [tex]\equiv_q[/tex].

Solution:
Step 1. For positions [tex]i, j \in \{1 , 2 , \ldots , n\}[/tex] write [tex]i \approx j[/tex] if [tex]s_i = s_j[/tex] for every [tex]s \in S[/tex]. This is an equivalence relation on the set of positions; let [tex]C_1, \ldots, C_k[/tex] be its classes, so [tex]1 \le k \le n[/tex]. Let [tex]T[/tex] be the set of strings that are constant on each class. Such a string is determined by an independent choice of [tex]0[/tex] or [tex]1[/tex] on each class, so [tex]|T| = 2^k[/tex]. We prove that [tex]\bar{S} = T[/tex].
Step 2. [tex]\bar{S} \subseteq T[/tex]. Every [tex]s \in S[/tex] is constant on each class by the definition of [tex]\approx[/tex]. If [tex]u[/tex] and [tex]v[/tex] are constant on a class [tex]C[/tex], then so are [tex]u \wedge v[/tex], [tex]u \vee v[/tex] and [tex]\neg u[/tex], because the operations act coordinatewise; for example, for [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]
By induction on the number of operations used, every element of [tex]\bar{S}[/tex] belongs to [tex]T[/tex].
Step 3. [tex]T \subseteq \bar{S}[/tex]. Fix [tex]s \in S[/tex] (possible, since [tex]S \ne \varnothing[/tex]); then the all-zero string [tex]\mathbf{0} = s \wedge \neg s[/tex] and the all-one string [tex]\mathbf{1} = s \vee \neg s[/tex] belong to [tex]\bar{S}[/tex].
Fix a class [tex]C[/tex] and a position [tex]i \in C[/tex]. For every position [tex]j \notin C[/tex] we have [tex]i \not\approx j[/tex], so there is [tex]s \in S[/tex] with [tex]s_i \ne s_j[/tex]; put [tex]t^{(j)} = s[/tex] if [tex]s_i = 1[/tex] and [tex]t^{(j)} = \neg s[/tex] if [tex]s_i = 0[/tex]. Then [tex]t^{(j)} \in \bar{S}[/tex], [tex]t^{(j)}_i = 1[/tex] and [tex]t^{(j)}_j = 0[/tex]. Let
[tex]e_C = \mathbf{1} \wedge \bigwedge_{j \notin C} t^{(j)}[/tex]
(if [tex]C[/tex] contains all positions, then [tex]e_C = \mathbf{1}[/tex]). Then [tex]e_C \in \bar{S}[/tex]; it has [tex]0[/tex] at every position outside [tex]C[/tex] and [tex]1[/tex] at position [tex]i[/tex]. Since [tex]e_C \in T[/tex] by Step 2, it equals [tex]1[/tex] on the whole class [tex]C[/tex]. So [tex]e_C[/tex] is exactly the string with ones on [tex]C[/tex] and zeros elsewhere.
Finally, every [tex]u \in T[/tex] equals [tex]1[/tex] exactly on the union of some classes, so [tex]u[/tex] is the disjunction of the corresponding strings [tex]e_C[/tex] (or [tex]u = \mathbf{0}[/tex] if there are no such classes); hence [tex]u \in \bar{S}[/tex]. Therefore [tex]\bar{S} = T[/tex] and [tex]|\bar{S}| = 2^k[/tex], where [tex]1 \le k \le n[/tex].