Question 3 of 12

Question 3 (10 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) $A=\{1,2,3\}$, $B=\{1,3\}$. (b) Three arbitrary sets $A,B,C$. (c) Two set identities relating $A,B,C$.

Find. (a) The elements of $A\times B - B\times A$. (b) A proof of the set identity by the algebra of sets. (c) Whether $A=B$ follows, with proof or counterexample.

Approach. (a) list both Cartesian products and subtract; (b) rewrite every difference as an intersection with a complement ($X-Y=X\cap Y^c$, so $X-C^c=X\cap C$) and simplify both sides with the set laws; (c) case-split an arbitrary $x\in A$ on whether $x\in C$.

1. (a) Compute $A\times B - B\times A$. $$A\times B=\{(1,1),(1,3),(2,1),(2,3),(3,1),(3,3)\}$$ $$B\times A=\{(1,1),(1,2),(1,3),(3,1),(3,2),(3,3)\}$$ Subtracting, the pairs of $A\times B$ that are NOT also in $B\times A$ are exactly those whose first coordinate is $2$ (since $2\notin B$, no pair starting with $2$ can appear in $B\times A$): $$\boxed{A\times B - B\times A = \{(2,1),(2,3)\}}$$
2. (b) Show $(A-B)-C^c=(A-C^c)-(B-C^c)$. Use $X-Y=X\cap Y^c$ and $(C^c)^c=C$, so subtracting $C^c$ is the same as intersecting with $C$: $X-C^c=X\cap C$. Left side: $$(A-B)-C^c=(A\cap B^c)\cap C=A\cap B^c\cap C$$ Right side, using De Morgan's law $(B\cap C)^c=B^c\cup C^c$, then the distributive, complement ($C\cap C^c=\varnothing$) and identity laws: $$(A-C^c)-(B-C^c)=(A\cap C)\cap(B\cap C)^c=(A\cap C)\cap(B^c\cup C^c)=(A\cap B^c\cap C)\cup(A\cap C\cap C^c)=A\cap B^c\cap C$$ Both sides reduce to the same set, so: $$\boxed{(A-B)-C^c=(A-C^c)-(B-C^c)=A\cap B^c\cap C}$$
3. (c) Does $A-C=B-C$ and $C-A=C-B$ force $A=B$? Take an arbitrary $x\in A$; show $x\in B$ (the reverse inclusion is symmetric, giving $A=B$).
   Case 1: $x\notin C$. Then $x\in A-C$, so by the first hypothesis $x\in B-C\subseteq B$.
   Case 2: $x\in C$. Since $x\in A$ and $x\in C$, $x\notin C-A$ (as $C-A$ requires $x\notin A$). By the second hypothesis $C-A=C-B$, so $x\notin C-B$ either; but $x\in C$, so $x\notin C-B$ forces $x\in B$ (otherwise $x$ would satisfy $x\in C,x\notin B$, i.e. $x\in C-B$).
   Both cases give $x\in B$, so $A\subseteq B$; the identical argument with $A,B$ swapped gives $B\subseteq A$. Hence: $$\boxed{\text{Yes: } A=B}$$ (An exhaustive computer search over all subset triples of a 4-element universe found no counterexample, confirming the proof.)