Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1

We prove both set inclusions. If $x\in A\setminus (A\setminus B)$, then $x\in A$ and $x\notin A\setminus B$. Since $x\in A$, the latter condition forces $x\in B$, giving $x\in A\cap B$. Conversely, if $x\in A\cap B$, then $x\in A$ and $x\notin A\setminus B$, so $x\in A\setminus (A\setminus B)$. By set extensionality, the two sets are equal. This is a double inclusion proof; the implication involving the set difference uses membership in $A$ explicitly.

False. Take the sets $A=\{1\}$, $B=\varnothing$ and $C=\varnothing$. Both intersections with $C$ are empty, although $A\ne B$. Intersecting with $C$ loses information about membership outside $C$.

False. Take the sets $A=\{1\}$, $B=\varnothing$ and $C=\{1\}$. Both unions with $C$ equal $\{1\}$, although $A\ne B$. Taking a union with $C$ conceals which of its elements belonged to the original set.

True. The two operations retain complementary membership information. For $x\in C$, equality of the intersections makes $x\in A$ equivalent to $x\in B$. For $x\notin C$, equality of the unions makes $x\in A$ equivalent to $x\in B$. These cases exhaust every possible element. Set extensionality therefore gives $A=B$. Equivalently, reconstruct either set fromSubstituting the two given equalities into this expression gives $B$.

False. With the sets $A=\{1\}$, $B=\varnothing$ and $C=\{1\}$, both set differences are empty but $A\ne B$. Removing $C$ loses the distinction between their memberships inside $C$.

True. Fix $a\in A$. Reflexivity supplies $a{R}_{1}a$ and $a{R}_{2}a$. In the definition of composition of relations, choose the intermediate element to be $a$ itself. Then $a(R_2\circ R_1)a$. This holds for every $a\in A$, so the composite binary relation is reflexive.

False, even for two equivalence relations. On $A=\{1,2,3\}$, let $R_1$ have equivalence classes $\{1,2\}$ and $\{3\}$, and let $R_2$ have equivalence classes $\{1\}$ and $\{2,3\}$. Both binary relations are transitive. For $S=R_2\circ R_1$, we have $3S2$, using the intermediate element $3$, and $2S1$, using the intermediate element $1$. However, $3S1$ fails: the only $R_1$-successor of $3$ is $3$, and $3R_{2}1$ is false. Thus the composite fails transitivity. The order of composition here means first $R_1$, then $R_2$.

False. Use the same two equivalence relations as in part (ii). They are both symmetric relations. The composite contains $1S3$, since $1R_{1}2$ and $2R_{2}3$. It does not contain $3S1$, as shown there. Hence composition of relations need not preserve symmetry of a relation, even when both factors are also reflexive and transitive.

Let $x_i$ be the number in box $i$ and put $y_i=x_i-1$. We count integer compositions satisfying $y_1+\cdots +y_4=6$ and $0\le y_i\le 4$. Without the upper bounds, stars and bars gives $\left(\genfrac{}{}{0ex}{}{9}{3}\right)=84$. If a specified $y_i\ge 5$, subtract five from it; the remaining nonnegative integer variables sum to one, giving $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ possibilities. Two violations cannot occur because they would require a sum at least ten. The inclusion-exclusion principle therefore givesThe boxes are distinguished by their positions in the composition; individual objects are not distinguished.