Corrected exercises: set theory and relations (201-N11)

$A = \{2,4,6,8,10\}$ and $B = \{1,2,3,4,5\}$. Set-builder notation gives the rule, roster form gives the list: switching from one to the other is the first reflex of the chapter, because a property is much faster to check on a list.

$3 \notin A$, since 3 is odd. $\{3\} \subseteq B$, since the only element of $\{3\}$ is in $B$. $3 \in B$. $\{2,4\} \subseteq A$. The point not to miss: $3$ and $\{3\}$ are not the same thing. The first is a number, the second is a set containing that number. You write $3 \in B$ but $\{3\} \subseteq B$, and never the other way around.

$\mathcal{P}(\{a,b,c\}) = \{\varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}$, that is, 8 subsets. List them by increasing size: it is the only way not to forget any, and the count by size must give $1, 3, 3, 1$.

Each element of $X$ is either taken or left out, independently of the others: that makes $2$ choices repeated $n$ times, so $\lvert \mathcal{P}(X) \rvert = 2^{n}$. For $E$, which has 10 elements, $2^{10} = 1024$ subsets. The link with the chapter on number systems is direct: a subset of $X$ is exactly a binary word of $n$ bits, where the bit in position $k$ says whether element $k$ is taken.

$\varnothing \notin A$: the elements of $A$ are numbers, not sets. But $\varnothing \subseteq A$: inclusion requires every element of $\varnothing$ to be in $A$, which is vacuously true since there is no element to check. And $\varnothing \in \mathcal{P}(A)$, since $\mathcal{P}(A)$ is the set of subsets of $A$ and $\varnothing$ is one of them. The three answers differ, and that is what makes the example useful.

$A \cup B = \{1,2,3,4,5,6,7,8\}$: all the elements that are in one OR the other, counted only once. $A \cap B = \{4,5,6\}$: those that are in both. $A \setminus B = \{1,2,3\}$: in $A$ but not in $B$. $B \setminus A = \{7,8\}$. Note that $A \setminus B$ and $B \setminus A$ have nothing to do with each other: the difference is not symmetric.

$\overline{A} = \{7,8,9,10\}$ and $\overline{B} = \{1,2,3,9,10\}$. The complement only makes sense relative to a universal set: without $E$, the notation $\overline{A}$ means nothing. Check: $\lvert A \rvert + \lvert \overline{A} \rvert = 6+4 = 10 = \lvert E \rvert$.

$A \times B$ is the set of ORDERED pairs $(a,b)$ with $a \in A$ and $b \in B$: it has $6 \times 5 = 30$ of them. For example $(1,4)$, $(3,8)$ and $(6,5)$. The Cartesian product produces pairs, not elements: $(1,4)$ is neither a number nor a two-element set.

$A \setminus B = \{1,2,3\}$ and $A \cap B = \{4,5,6\}$; their union is $\{1,2,3,4,5,6\} = A$. The identity is general: every element of $A$ is either in $B$ or not, and these two cases give exactly the two pieces. It is a partition of $A$ into two disjoint parts, which explains why the cardinalities add up here with no correction.

$\lvert A \rvert = 6$, $\lvert B \rvert = 5$, $\lvert A \cap B \rvert = 3$, so the formula gives $6+5-3 = 8$. And $\lvert A \cup B \rvert = \lvert \{1,\dots,8\} \rvert = 8$. The formula works. The reason is that adding $\lvert A \rvert$ and $\lvert B \rvert$ counts the common elements twice: one copy must therefore be subtracted.

No. $A \times B$ contains $(1,4)$, but not $(4,1)$, since $1 \notin B$. Yet $(4,1) \in B \times A$. The two products have the same cardinality, 30, but they are not the same pairs. An ordered pair is ordered, and that is the whole difference with an unordered pair: $(a,b) = (c,d)$ requires $a=c$ AND $b=d$.

First inclusion. Let $x \in \overline{A \cup B}$. Then $x \notin A \cup B$, so $x$ is neither in $A$ nor in $B$; hence $x \in \overline{A}$ and $x \in \overline{B}$, that is, $x \in \overline{A} \cap \overline{B}$. Reverse inclusion. Let $x \in \overline{A} \cap \overline{B}$. Then $x \notin A$ and $x \notin B$, so $x$ is in neither of the two, so $x \notin A \cup B$, that is, $x \in \overline{A \cup B}$. The two inclusions give the equality. This is exactly De Morgan's law from logic, carried over to sets: the negation of an OR is an AND of negations.

Four rows, depending on whether $x$ belongs to $A$ and to $B$ or not. Columns $(x \in A, x \in B)$, then $A \cap B$, then $\overline{A \cap B}$, then $\overline{A}$, $\overline{B}$ and their union. Row $(1,1)$: $A \cap B$ is 1, its complement 0; $\overline{A} \cup \overline{B}$ is $0 \cup 0 = 0$. Row $(1,0)$: $0$, so $1$; and $0 \cup 1 = 1$. Row $(0,1)$: $0$, so $1$; and $1 \cup 0 = 1$. Row $(0,0)$: $0$, so $1$; and $1 \cup 1 = 1$. The two final columns are identical on all four rows: the equality is established. The table is faster than double inclusion, but it only generalizes cleanly to identities involving a small number of sets.

$x \in A \setminus B$ means $x \in A$ and $x \notin B$, which can be written $x \in A$ and $x \in \overline{B}$, that is, $x \in A \cap \overline{B}$. The two expressions translate the same sentence, so the equivalence is immediate in both directions. This identity is the one that lets you eliminate the difference symbol everywhere and work only with union, intersection and complement.

$A \setminus B$ and $B \setminus A$ are disjoint, so the cardinalities add up: $\lvert A \Delta B \rvert = \lvert A \setminus B \rvert + \lvert B \setminus A \rvert$. Now $\lvert A \setminus B \rvert = \lvert A \rvert - \lvert A \cap B \rvert$, and likewise for the other. Hence $\lvert A \Delta B \rvert = \lvert A \rvert + \lvert B \rvert - 2\lvert A \cap B \rvert$. The factor 2 is the point to understand: the intersection is removed twice, once on each side, because it is precisely what the symmetric difference excludes. On the example of the previous exercise: $6+5-2(3) = 5$, and indeed $A \Delta B = \{1,2,3,7,8\}$.

No. Counterexample: $A = \{1\}$, $B = \{2\}$, $C = \{1\}$. On the left, $B \setminus C = \{2\}$ and $A \setminus \{2\} = \{1\}$. On the right, $A \setminus B = \{1\}$, then $\{1\} \setminus C = \varnothing$. We get $\{1\}$ on one side and $\varnothing$ on the other: the difference is not associative. A single counterexample is enough to disprove an identity claimed for all sets, and it is best looked for with one-element sets, where everything can be checked in your head.

ALWAYS start from the center, otherwise you subtract quantities that have already been removed. Center: $\lvert A \cap B \cap C \rvert = 3$. Region $A \cap B$ only: $8 - 3 = 5$. Region $A \cap C$ only: $10 - 3 = 7$. Region $B \cap C$ only: $7 - 3 = 4$. Region $A$ only: $27 - 5 - 7 - 3 = 12$. Region $B$ only: $20 - 5 - 4 - 3 = 8$. Region $C$ only: $29 - 7 - 4 - 3 = 15$. Outside: $60 - (12+8+15+5+7+4+3) = 60 - 54 = 6$. Check: the eight regions add up to 60, the cardinality of $E$.

$\lvert A \cup B \cup C \rvert = 27+20+29-8-10-7+3 = 54$. On the diagram, the union is the sum of the seven inner regions: $12+8+15+5+7+4+3 = 54$. The two methods agree, and it is this double calculation that secures the result.

$60 - 54 = 6$ elements are outside the union. This is the outer region of the diagram, the one that is systematically forgotten when the rectangle of the universal set is not drawn.

Exactly two: these are the three lens-shaped regions, $5 + 7 + 4 = 16$ elements. Watch the wording: $\lvert A \cap B \rvert = 8$ also counts the 3 elements in the center, which are in THREE sets. “In exactly two” is not “in $A \cap B$”, and this nuance is the classic trap of survey problems.

Because the elements in the center are counted three times by $\lvert A \rvert + \lvert B \rvert + \lvert C \rvert$, then removed three times by the three pairwise intersections: their balance is zero, whereas they must count once. So they are added back once. The same compensation argument, applied to an element lying in exactly two sets, gives $2 - 1 = 1$: it is counted once, as it should be, and nothing needs correcting for it.

$R = \{(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)\}$, that is, 8 ordered pairs. You find them by sweeping through the 16 possible pairs and keeping those where the division comes out exactly: 1 divides everything, 2 divides 2 and 4, 3 divides 3, and 4 divides 4.

A relation on $E$ is a subset of $E \times E$, which has $4 \times 4 = 16$ ordered pairs. There are therefore $2^{16} = 65{,}536$ possible relations, one per subset of pairs. The link with exercise 1 is direct: each pair is chosen or not, which is a 16-bit word.

Ordering the indices from 1 to 4: $M = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$. The first row is full, because 1 divides everything; the matrix is upper triangular, because a divisor of a nonzero number is less than or equal to it. Check: the matrix has 8 entries equal to 1, as many as $R$ has ordered pairs.

The image of 2 is $\{y : 2\,R\,y\} = \{2,4\}$, that is, the 1s of the second ROW. The preimages of 4 are $\{x : x\,R\,4\} = \{1,2,4\}$, that is, the 1s of the fourth COLUMN. Reading a row or a column does not give the same thing, and this is the first source of error with relation matrices.

No. A function assigns to each starting element AT MOST one image, but 1 is related to 1, 2, 3 and 4: four images. A relation is a function exactly when each row of its matrix contains at most one 1; here the first row contains four. This is the essential difference between the two notions: a function is a very special case of a relation.

Reflexive: every integer divides itself, the four pairs $(x,x)$ are there. Symmetric: no, $(1,2) \in R_{1}$ but $(2,1) \notin R_{1}$, one counterexample is enough. Antisymmetric: if $x$ divides $y$ and $y$ divides $x$ with $x,y$ positive, then $x=y$; you can also check it pair by pair, no symmetric pair appears off the diagonal. Transitive: if $x$ divides $y$ and $y$ divides $z$, then $x$ divides $z$. Reflexive, antisymmetric and transitive: $R_{1}$ is an ORDER relation, and this order is partial since 2 and 3 are not comparable.

Reflexive: no, $(1,1) \notin R_{2}$. Symmetric: yes, $(1,2)$ and $(2,1)$ are both present, and $(3,3)$ is its own mirror image. Antisymmetric: no, $(1,2)$ and $(2,1)$ are there although $1 \neq 2$. Transitive: no, $(1,2)$ and $(2,1)$ should force $(1,1)$, which is missing. So $R_{2}$ is neither an order nor an equivalence: it is just an arbitrary relation, and that is the most frequent case.

Reflexive: $x+x = 2x$ is even, so yes. Symmetric: $x+y = y+x$, so yes. Antisymmetric: no, $(1,3)$ and $(3,1)$ are there with $1 \neq 3$. Transitive: if $x+y$ and $y+z$ are even, then $x$ and $y$ have the same parity, and so do $y$ and $z$, hence $x$ and $z$ as well, so $x+z$ is even. Reflexive, symmetric and transitive: $R_{3}$ is an EQUIVALENCE relation, the one that sorts integers by parity.

Yes, but it is very restrictive: if $(x,y) \in R$ with $x \neq y$, symmetry forces $(y,x) \in R$ and antisymmetry then forces $x=y$, a contradiction. A relation that is both symmetric and antisymmetric therefore contains only pairs on the diagonal. Example: equality, $R = \{(x,x) : x \in E\}$. Symmetric and antisymmetric are not opposites: they are two independent conditions that can be true together, false together, or one without the other.

Reflexive: the diagonal contains only 1s. Symmetric: the matrix equals its transpose. Antisymmetric: off the diagonal, never $M_{ij}$ and $M_{ji}$ both equal to 1. Transitive: the Boolean square $M^{2}$ has no 1 where $M$ has a 0, which is written $M^{2} \le M$. This last reading builds the bridge to the chapter on matrices: a 1 in position $(i,j)$ of $M^{2}$ signals a path of length 2, and transitivity requires such a path always to have its direct shortcut.

Reflexive: $x$ obviously leaves the same remainder as itself. Symmetric: if $x$ and $y$ leave the same remainder, then so do $y$ and $x$, the condition is symmetric as written. Transitive: if $x$ and $y$ leave the same remainder $r$, and $y$ and $z$ the same remainder, that remainder is still $r$, so $x$ and $z$ leave the same remainder. The three properties hold: $\sim$ is an equivalence. None of these checks requires any calculation, because the relation is defined by the equality of a quantity, and equality is always an equivalence.

Class of 0: $\{0,5,10\}$. Class of 1: $\{1,6,11\}$. Class of 2: $\{2,7,12\}$. Class of 3: $\{3,8,13\}$. Class of 4: $\{4,9,14\}$. We write $[r]$ for the class of the remainder $r$; for example $[2] = \{2,7,12\}$, and $[7]$ denotes the SAME set. A class has as many names as it has elements, which is puzzling at first but causes no trouble once accepted.

Three conditions. No class is empty: each has three elements. They are pairwise disjoint: two different remainders cannot coexist for the same number, since the remainder of Euclidean division is unique. Their union is $E$: every integer in $E$ has a remainder, so it belongs to a class. It is indeed a partition.

Five classes, as many as the possible remainders $0, 1, 2, 3, 4$, with 3 elements each. Check: $5 \times 3 = 15 = \lvert E \rvert$. This regularity comes from the fact that $E$ contains exactly three blocks of 5 consecutive integers; on $\{0,\dots,13\}$ the classes would no longer all have the same size.

Each class is the content of one bucket: the elements that collide are exactly those that are equivalent modulo 5. The number of buckets is the number of classes, and evenly sized classes are precisely what is asked of a good hash function. If the data all left the same remainder, everything would land in the same bucket and searching would become linear again.

No. If $z$ belongs to the class of $x$ and to that of $y$, then $x \sim z$ and $z \sim y$, so $x \sim y$ by transitivity, and the two classes contain exactly the same elements. Two classes are therefore either equal or disjoint, never partly overlapping. This dichotomy is what guarantees a partition, and it rests entirely on transitivity.

FALSE. It is inclusion that is universal, not membership: $\varnothing \subseteq A$ for every $A$, but $\varnothing \in A$ only if $A$ contains the empty set as an element. Counterexample: $A = \{1,2\}$ contains only the numbers 1 and 2. Correct statement: $\varnothing \subseteq A$ always, and $\varnothing \in \mathcal{P}(A)$ always, but $\varnothing \in A$ almost never.

FALSE. The number of subsets doubles with each element added, it does not increase by a fixed amount: it is $2^{n}$, not $2n$. Counterexample: for $n=3$, we counted 8 subsets, whereas $2n = 6$. Correct statement: $\lvert \mathcal{P}(X) \rvert = 2^{\lvert X \rvert}$, because each element is taken or left out independently of the others.

FALSE. The two properties are independent, and a relation may satisfy neither. Counterexample: $R = \{(1,2),(2,1),(1,3)\}$ on $\{1,2,3\}$ is not symmetric, since $(3,1)$ is missing, and not antisymmetric, since $(1,2)$ and $(2,1)$ coexist with $1 \neq 2$. Correct statement: symmetric and antisymmetric are two distinct conditions; the negation of one cannot be deduced from the other.

FALSE. The common elements would be counted twice. Counterexample: $A = \{1,2\}$ and $B = \{2,3\}$ give $\lvert A \cup B \rvert = 3$ whereas $\lvert A \rvert + \lvert B \rvert = 4$. Correct statement: $\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert$, and the plain equality holds only if $A$ and $B$ are disjoint.