04-BS-16, May 2016, Q7 | Nivaar Exam Prep

Question 7 (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. $R=\{(x,y)\in\mathbb{Z}\times\mathbb{Z}: x=y\pm 3\}$, i.e. $|x-y|=3$; $A=\{1,2,3,4\}$, $|A|=4$.

Find. (a) Which of the four standard properties $R$ has. (b) Whether $R^2=R\circ R$ is reflexive. (c) The number of distinct relations on $A$.

Approach. Test each property directly from the defining condition $x=y\pm3$ (equivalently $|x-y|=3$); compute $R^2$ by chaining the relation with itself; count relations as subsets of $A\times A$.

(a) Properties of $R$. Note $x=y\pm3\iff|x-y|=3$. Reflexive? Would need $|x-x|=0=3$, false for every $x$ (e.g. $(0,0)\notin R$): NOT reflexive. Symmetric? If $(x,y)\in R$ then $|x-y|=3$, hence $|y-x|=3$ and $(y,x)\in R$: SYMMETRIC. Antisymmetric? $(0,3)\in R$ and $(3,0)\in R$, but $0\ne3$: NOT antisymmetric. Transitive? $(0,3)\in R$ and $(3,6)\in R$, but $|0-6|=6\ne3$, so $(0,6)\notin R$: NOT transitive. $$\boxed{R\text{ is symmetric only (not reflexive, not antisymmetric, not transitive)}}$$
(b) Is $R^2$ reflexive? $R^2=R\circ R=\{(x,z):\exists y,\ |x-y|=3,\ |y-z|=3\}$. Two steps of $\pm3$ give $z-x\in\{-6,0,6\}$, so $R^2=\{(x,z): z-x\in\{-6,0,6\}\}$. In particular, for every integer $x$ take $y=x+3$: $(x,x+3)\in R$ and $(x+3,x)\in R$, so $(x,x)\in R^2$. $$\boxed{R^2\text{ IS reflexive (every } x \text{ returns to itself via } x\to x+3\to x)}$$
(c) Number of relations on a 4-element set. A relation on $A$ is any subset of $A\times A$, and $|A\times A|=4\times 4=16$. The number of subsets of a 16-element set is $2^{16}$: $$\boxed{2^{16}=65{,}536}$$

Question 7 – results
Part	Result
a	Symmetric only
b	$R^2$ IS reflexive ($x\to x+3\to x$)
c	65,536 relations

Topic: Properties of relations and relation composition.

Key relations: Reflexive: $\forall x\,(x,x)\in R$; symmetric: $(x,y)\in R\Rightarrow(y,x)\in R$; antisymmetric: $(x,y),(y,x)\in R\Rightarrow x=y$ (vacuously true if the hypothesis never holds); transitive: $(x,y),(y,z)\in R\Rightarrow(x,z)\in R$; number of relations on an $n$-set is $2^{n^2}$.

Why this works: The $\pm$ makes the defining condition $|x-y|=3$ symmetric in $x$ and $y$, which gives symmetry at once and rules out antisymmetry (both $(0,3)$ and $(3,0)$ are in $R$). Composition $R\circ R$ is computed by chaining through the shared middle variable, and a step out followed by a step back returns to the start, so $R^2$ contains every loop $(x,x)$ even though $R$ contains none.

Common pitfall: Reading $x=y\pm3$ as $x=y+3$, which would make $R$ antisymmetric and $R^2$ non-reflexive (both verdicts reversed); assuming $R^2$ inherits non-reflexivity from $R$; miscounting $A\times A$ as $4+4$ instead of $4\times 4=16$ when counting relations.

Source: Rosen, Discrete Mathematics and Its Applications, 7th ed., Ch. 9 (Relations and Their Properties).

Question 7 of 12

Question 7 (10 marks)