Mathematical Logic and Set Theory: Difficult Problems with Solutions

Solution:
Let [tex]T[/tex], [tex]H[/tex], [tex]F[/tex] be the sets of students who run, play handball and play football. Every student practices at least one sport, so [tex]|T\cup H\cup F|=40[/tex]. By the inclusion-exclusion principle
[tex]|T\cup H\cup F|=|T|+|H|+|F|-|T\cap H|-|H\cap F|-|T\cap F|+|T\cap H\cap F|[/tex]
[tex]40=18+20+27-7-12-|T\cap F|+4=50-|T\cap F|\ \Rightarrow\ |T\cap F|=10[/tex]
The required students form the set [tex](T\cap F)\setminus H[/tex]:
[tex]|(T\cap F)\setminus H|=|T\cap F|-|T\cap H\cap F|=10-4=6[/tex]
Check: the seven regions of the Venn diagram contain [tex]5[/tex] (only running), [tex]5[/tex] (only handball), [tex]9[/tex] (only football), [tex]3[/tex] (running and handball only), [tex]8[/tex] (handball and football only), [tex]6[/tex] (running and football only) and [tex]4[/tex] (all three) students; all numbers are non-negative and their sum is [tex]40[/tex].

Solution:
All elements of [tex]D_y[/tex] are odd. If [tex]x[/tex] is odd and [tex]x\ge 3[/tex], the sum [tex]x+y[/tex] is even and [tex]x+y\ge 4[/tex], so it is not prime. In particular, [tex]P(3,y)[/tex] is false for every [tex]y\in D_y[/tex].
Therefore [tex]\forall x\,\exists y\,P(x,y)[/tex] is false (it fails for [tex]x=3[/tex]), and [tex]\exists y\,\forall x\,P(x,y)[/tex] is false (every [tex]y[/tex] fails at [tex]x=3[/tex]).
For [tex]x=6[/tex] all the sums are prime:
[tex]6+1=7 , \quad 6+5=11 , \quad 6+7=13[/tex]
[tex]6+11=17 , \quad 6+13=19 , \quad 6+17=23[/tex]
so [tex]\exists x\,\forall y\,P(x,y)[/tex] is true. Then [tex]\forall y\,\exists x\,P(x,y)[/tex] is also true (take [tex]x=6[/tex] for every [tex]y[/tex]), hence its negation [tex]\exists y\,\forall x\,\neg P(x,y)[/tex] is false.
The only true statement among the options is [tex]\exists x\,\forall y\,P(x,y)[/tex].

Solution:
Each pair [tex](a,b)\in R_1[/tex] is combined with every pair [tex](b,c)\in R_2[/tex] that starts with the same [tex]b[/tex], and gives [tex](a,c)\in R_1\mathbin{\char59}R_2[/tex]. No pair of [tex]R_2[/tex] starts with [tex]2[/tex], so [tex](1,2)[/tex] and [tex](2,2)[/tex] give nothing. The remaining pairs of [tex]R_1[/tex] give:
[tex](1,3)\in R_1\land(3,1)\in R_2\ \Rightarrow\ (1,1)[/tex]
[tex](2,4)\in R_1\land(4,3),(4,4)\in R_2\ \Rightarrow\ (2,3),(2,4)[/tex]
[tex](3,4)\in R_1\land(4,3),(4,4)\in R_2\ \Rightarrow\ (3,3),(3,4)[/tex]
[tex](4,3)\in R_1\land(3,1)\in R_2\ \Rightarrow\ (4,1)[/tex]
Therefore
[tex]R_1\mathbin{\char59}R_2=\{(1,1),(2,3),(2,4),(3,3),(3,4),(4,1)\}[/tex]
The order matters: [tex]R_2\mathbin{\char59}R_1=\{(1,2),(1,3),(1,4),(3,2),(3,3),(4,3),(4,4)\}[/tex] is a different relation.

Solution:
Reflexivity holds: for every [tex]X[/tex] we have [tex]X\subseteq X[/tex] and [tex]|X\setminus X|=|\varnothing|=0\le 1[/tex], so [tex]X\,R\,X[/tex].
Symmetry fails: [tex]\varnothing\,R\,\{1\}[/tex], because [tex]\varnothing\subseteq\{1\}[/tex] and [tex]|\{1\}\setminus\varnothing|=1[/tex], but [tex]\{1\}\,R\,\varnothing[/tex] is false, because [tex]\{1\}\not\subseteq\varnothing[/tex].
Antisymmetry holds: if [tex]X\,R\,Y[/tex] and [tex]Y\,R\,X[/tex], then [tex]X\subseteq Y[/tex] and [tex]Y\subseteq X[/tex], hence [tex]X=Y[/tex].
Transitivity fails: [tex]\varnothing\,R\,\{1\}[/tex] and [tex]\{1\}\,R\,\{1,2\}[/tex], but [tex]|\{1,2\}\setminus\varnothing|=2\gt 1[/tex], so [tex]\varnothing\,R\,\{1,2\}[/tex] is false.
Hence [tex]R[/tex] is reflexive and antisymmetric, but neither symmetric nor transitive (in particular, it is neither a partial order nor an equivalence relation).

Solution:
The Zhegalkin polynomial of [tex]f[/tex] is unique and has the form (all operations are modulo [tex]2[/tex])
[tex]f=a_0\oplus a_1x_1\oplus a_2x_2\oplus a_3x_3\oplus a_{12}x_1x_2\oplus a_{13}x_1x_3\oplus a_{23}x_2x_3\oplus a_{123}x_1x_2x_3[/tex]
The vector of values gives
[tex]f(0,0,0)=1 , \ f(0,0,1)=1 , \ f(0,1,0)=0 , \ f(0,1,1)=1[/tex]
[tex]f(1,0,0)=0 , \ f(1,0,1)=0 , \ f(1,1,0)=1 , \ f(1,1,1)=1[/tex]
We substitute the points in order of increasing number of ones:
[tex]f(0,0,0)=a_0=1[/tex]
[tex]f(1,0,0)=a_0\oplus a_1=0\Rightarrow a_1=1[/tex]
[tex]f(0,1,0)=a_0\oplus a_2=0\Rightarrow a_2=1[/tex]
[tex]f(0,0,1)=a_0\oplus a_3=1\Rightarrow a_3=0[/tex]
[tex]f(1,1,0)=a_0\oplus a_1\oplus a_2\oplus a_{12}=1\oplus a_{12}=1\Rightarrow a_{12}=0[/tex]
[tex]f(1,0,1)=a_0\oplus a_1\oplus a_3\oplus a_{13}=a_{13}=0[/tex]
[tex]f(0,1,1)=a_0\oplus a_2\oplus a_3\oplus a_{23}=a_{23}=1[/tex]
[tex]f(1,1,1)=1\oplus 1\oplus 1\oplus 0\oplus 0\oplus 0\oplus 1\oplus a_{123}=a_{123}=1[/tex]
Hence
[tex]f=1\oplus x_1\oplus x_2\oplus x_2x_3\oplus x_1x_2x_3[/tex]

Solution:
Let [tex]F[/tex] be the number of false statements in [tex]A[/tex], [tex]0\le F\le 12[/tex]. By its content, [tex]p_i[/tex] is true exactly when [tex]F\ge i[/tex].
So the true statements are exactly [tex]p_1,\ldots,p_F[/tex] and the false ones are [tex]p_{F+1},\ldots,p_{12}[/tex]. Counting the false statements in two ways:
[tex]12-F=F\Rightarrow F=6[/tex]
Check: if [tex]p_1,\ldots,p_6[/tex] are true and [tex]p_7,\ldots,p_{12}[/tex] are false, then exactly [tex]6[/tex] statements are false, so “at least [tex]i[/tex] are false” holds exactly for [tex]i\le 6[/tex], which agrees with the assignment. Since [tex]F=6[/tex] is forced, this is the only consistent assignment, and exactly [tex]6[/tex] statements are true.

Solution:
First simplify the right-hand side:
[tex](x,y)\in(A×C)\cap(B×D)\Leftrightarrow x\in A\cap B\ \land\ y\in C\cap D[/tex]
[tex](A×C)\cap(B×D)=(A\cap B)×(C\cap D)[/tex]
Since [tex]C\cap D\subseteq C\cup D[/tex], the right-hand side is always contained in the left-hand side. If [tex]A\cap B=\varnothing[/tex], both sides are empty and the equality holds.
Let [tex]A\cap B\ne\varnothing[/tex], fix [tex]x_0\in A\cap B[/tex] and suppose the equality holds. For every [tex]y\in C\cup D[/tex] the pair [tex](x_0,y)[/tex] lies in the left-hand side, hence in [tex](A\cap B)×(C\cap D)[/tex], so [tex]y\in C\cap D[/tex]. Thus [tex]C\cup D\subseteq C\cap D[/tex], and therefore
[tex]C\subseteq C\cup D\subseteq C\cap D\subseteq D[/tex]
and similarly [tex]D\subseteq C[/tex], so [tex]C=D[/tex]. Conversely, if [tex]C=D[/tex], then [tex]C\cup D=C\cap D[/tex] and both sides coincide. Therefore the equality holds if and only if [tex]A\cap B=\varnothing[/tex] or [tex]C=D[/tex].

Solution:
Work inside a universal set [tex]U[/tex] containing [tex]A[/tex], [tex]B[/tex] and [tex]C[/tex]. For [tex]X\subseteq U[/tex] let [tex]\chi_X[/tex] be its indicator function:
[tex]\chi_X(x)=\begin{cases}1, & x\in X\\ 0, & x\notin X\end{cases}[/tex]
Two subsets of [tex]U[/tex] are equal exactly when their indicator functions are equal. By definition, [tex]x\in X\triangle Y[/tex] exactly when [tex]x[/tex] belongs to exactly one of the sets [tex]X[/tex] and [tex]Y[/tex], i.e. exactly one of [tex]\chi_X(x)[/tex] and [tex]\chi_Y(x)[/tex] equals [tex]1[/tex]. Hence
[tex]\chi_{X\triangle Y}=\chi_X\oplus\chi_Y[/tex]
where [tex]\oplus[/tex] is addition modulo [tex]2[/tex]: [tex]0\oplus 0=1\oplus 1=0[/tex], [tex]0\oplus 1=1\oplus 0=1[/tex]. Applying this twice, we get
[tex]\chi_{A\triangle(B\triangle C)}=\chi_A\oplus(\chi_B\oplus\chi_C)[/tex]
[tex]\chi_{(A\triangle B)\triangle C}=(\chi_A\oplus\chi_B)\oplus\chi_C[/tex]
Addition modulo [tex]2[/tex] is associative (it is ordinary integer addition followed by taking the remainder modulo [tex]2[/tex]), so the two indicator functions coincide at every [tex]x\in U[/tex]. Hence [tex]A\triangle(B\triangle C)=(A\triangle B)\triangle C[/tex]. In words: both sides consist exactly of the elements that belong to an odd number (one or three) of the sets [tex]A[/tex], [tex]B[/tex], [tex]C[/tex].

Solution:
By the associativity of composition, [tex]f^a \circ f^b = f^{a+b}[/tex] for all natural [tex]a, b[/tex], and every power [tex]f^m[/tex] is a bijection of [tex]S[/tex] onto itself, since a composition of bijections is a bijection.
If [tex]S[/tex] has [tex]k[/tex] elements, there are only [tex]k![/tex] bijections [tex]S \to S[/tex], so the infinite sequence [tex]f^1, f^2, f^3, \ldots[/tex] contains a repetition: [tex]f^i = f^j[/tex] for some [tex]1 \le i \lt j[/tex]. Put [tex]m = j - i \ge 1[/tex]. Then
[tex]f^m \circ f^i = f^{m+i} = f^j = f^i[/tex]
Composing both sides on the right with the inverse of the bijection [tex]f^i[/tex], we get [tex]f^m = \mathrm{id}_S[/tex]. Now let [tex]n = 2m - 1 \ge 1[/tex]. Then
[tex]f^n \circ f = f \circ f^n = f^{2m} = f^m \circ f^m = \mathrm{id}_S[/tex]
so [tex]f^n[/tex] is a two-sided inverse of [tex]f[/tex]. The inverse of a bijection is unique, hence [tex]f^{-1} = f^n[/tex].
(We take [tex]n = 2m - 1[/tex] rather than [tex]m - 1[/tex] so that [tex]n \ge 1[/tex] also when [tex]m = 1[/tex], i.e. when [tex]f = \mathrm{id}_S[/tex].)