04-BS-16 · December 2013

Question 4 of 12: Relations — Divisibility on a Finite Set and on the Positive Integers

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, Dec 2013. Closed book, no aids, 3 hours, 12 questions of 10 marks each (100 marks); the exam instructs "answer 10 of 12" but every question is solved below as a complete study resource.

Reference texts: Rosen, Discrete Mathematics and Its Applications, 7th ed. (logic Ch.1, sets Ch.2, induction & pigeonhole Ch.5-6, relations Ch.9, counting Ch.6, discrete probability Ch.7, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 4: Relations — Divisibility on a Finite Set and on the Positive Integers (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=\{(a,b): a\mid b\}$, first restricted to $S=\{1,2,3,6,12\}$, then defined on all positive integers $\mathbb Z^+$.

Find. (a) The divisibility diagram on $S$. (b) Whether $R$ on $\mathbb Z^+$ is reflexive, symmetric, transitive, and an equivalence relation.

Divisibility relation on $\{1,2,3,6,12\}$: an arrow $a\to b$ means $a\mid b$ (self-loops at every node, since $a\mid a$, are omitted for clarity).

(a) List the arrows. $1\mid2,1\mid3,1\mid6,1\mid12$ (1 divides everything); $2\mid6,2\mid12$; $3\mid6,3\mid12$; $6\mid12$ — plus a self-loop at every node ($a\mid a$). $\boxed{\text{9 non-loop arrows (drawn above) + a self-loop at each of the 5 nodes.}}$
(b-a) Reflexive? For every positive integer $a$, $a\mid a$ (any number divides itself). $\boxed{\text{Yes, reflexive.}}$
(b-b) Symmetric? Need $a\mid b\Rightarrow b\mid a$. Counterexample: $2\mid4$ but $4\nmid2$. $\boxed{\text{No, not symmetric.}}$
(b-c) Transitive? Need $a\mid b$ and $b\mid c\Rightarrow a\mid c$. If $b=ka$ and $c=mb$ for integers $k,m$, then $c=mka$, so $a\mid c$. $\boxed{\text{Yes, transitive.}}$
(b-d) Equivalence relation? Requires reflexive AND symmetric AND transitive; $R$ fails symmetry (step b-b). $\boxed{\text{No, not an equivalence relation}}$ (it is instead a partial order — reflexive, antisymmetric, transitive).

Final results — Question 4
Part	Result
(a) Diagram	9 divisibility arrows on $\{1,2,3,6,12\}$ (see figure)
(b) Reflexive	Yes — $a\mid a$ always
(b) Symmetric	No — $2\mid4$ but $4\nmid2$
(b) Transitive	Yes — $a\mid b,b\mid c\Rightarrow a\mid c$
(b) Equivalence relation	No — fails symmetry (it's a partial order)

Topic: The divisibility relation as the standard example of a partial order (not an equivalence relation).

Key relations: $a\mid b\iff\exists k\in\mathbb Z^+, b=ka$; partial order = reflexive + antisymmetric + transitive; equivalence relation = reflexive + symmetric + transitive.

Why this works: Divisibility is transitive because dividing twice composes multiplicatively ($c=mka$ is still an integer multiple of $a$), but it is asymmetric in the "growing" direction — $b=ka$ with $k>1$ can never also give $a=k'b$ with $k'$ a positive integer, so symmetry fails whenever $a\ne b$.

Common pitfall: Concluding "transitive + reflexive $\Rightarrow$ equivalence relation" without separately checking symmetry; forgetting the self-loops when drawing the diagram.

Source: Rosen, Discrete Mathematics and Its Applications, §9.1 (relations and their properties), §9.6 (partial orderings).

← Question 3 Next: Question 5 →