04-BS-16 · May 2013

Question 5 of 12: Relations — Reflexive, Symmetric, Antisymmetric, Transitive

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

Notes on this paper

National Examination, 04-BS-16 Discrete Mathematics, May 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, induction & recursion Ch.5, counting Ch.6, discrete probability Ch.7, relations Ch.9, graphs Ch.10-11); Epp, Discrete Mathematics with Applications.

Question 5: Relations — Reflexive, Symmetric, Antisymmetric, Transitive (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=\{1,2,3,4\}$, $R=\{(x,y)\in A\times A : x^2\ge y\}$.

Find. Whether $R$ is reflexive, symmetric, anti-symmetric, transitive, and an equivalence relation.

List $R$ explicitly. For $x=1$: $x^2=1$, so only $y=1$ qualifies $\Rightarrow(1,1)$. For $x=2,3,4$: $x^2\in\{4,9,16\}$, each $\ge4\ge$ every $y\in\{1,2,3,4\}$, so ALL four $y$ qualify. Hence $$R = \{(1,1)\}\cup\{2,3,4\}\times\{1,2,3,4\} = \{(1,1),(2,1),(2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4)\}.$$
(a) Reflexive? Need $(x,x)\in R\ \forall x$, i.e. $x^2\ge x$. True for every $x\in\{1,2,3,4\}$ ($1\ge1,4\ge2,9\ge3,16\ge4$). $\boxed{\text{Yes, reflexive.}}$
(b) Symmetric? Need $(x,y)\in R\Rightarrow(y,x)\in R$. Counterexample: $(4,1)\in R$ (since $16\ge1$) but $(1,4)\notin R$ (since $1^2=1\not\ge4$). $\boxed{\text{No, not symmetric.}}$
(c) Anti-symmetric? Need $(x,y)\in R$ and $(y,x)\in R\Rightarrow x=y$. Counterexample: $(2,3)\in R$ ($4\ge3$) and $(3,2)\in R$ ($9\ge2$), yet $2\ne3$. $\boxed{\text{No, not anti-symmetric.}}$
(d) Transitive? Need $(x,y),(y,z)\in R\Rightarrow(x,z)\in R$. Case $x=1$: the only pair from $x=1$ is $(1,1)$, so $y=1$, and then $(y,z)=(1,z)\in R$ forces $z=1$, giving $(x,z)=(1,1)\in R$ ✓. Case $x\ge2$: since $x^2\ge4\ge z$ automatically for every $z\in\{1,2,3,4\}$, $(x,z)\in R$ regardless of which $z$ arose. Both cases hold, so $\boxed{\text{Yes, transitive.}}$
(e) Equivalence relation? An equivalence relation requires reflexive AND symmetric AND transitive. $R$ fails symmetry (step b), so $\boxed{\text{No, } R \text{ is not an equivalence relation.}}$

Final results — Question 5
Property	Holds?	Justification
Reflexive	Yes	$x^2\ge x$ for all $x\in\{1,2,3,4\}$
Symmetric	No	$(4,1)\in R$, $(1,4)\notin R$
Anti-symmetric	No	$(2,3),(3,2)\in R$ with $2\ne3$
Transitive	Yes	every $x\ge2$ relates to all of $\{1,2,3,4\}$; $x=1$ chains only to itself
Equivalence relation	No	fails symmetry

Topic: Properties of binary relations on a finite set.

Key relations: Reflexive: $\forall x, (x,x)\in R$. Symmetric: $(x,y)\in R\Rightarrow(y,x)\in R$. Anti-symmetric: $(x,y),(y,x)\in R\Rightarrow x=y$. Transitive: $(x,y),(y,z)\in R\Rightarrow(x,z)\in R$. Equivalence relation = reflexive + symmetric + transitive.

Why this works: Writing out $R$'s full extension turns an abstract "$x^2\ge y$" condition into a concrete finite table, so every property becomes a checkable statement about 13 explicit ordered pairs rather than an inequality argument. Because $x=2,3,4$ all satisfy $x^2\ge4$ (the largest possible $y$), those three rows relate to everything — which is exactly why transitivity survives (any chain through $x\ge2$ lands back in the "relates to everything" set) even though symmetry and anti-symmetry both fail.

Common pitfall: Assuming anti-symmetric is the logical opposite of symmetric (a relation can be neither, as here, or even both simultaneously for the identity relation); checking transitivity only on a few example triples instead of covering every case of $x$.

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

← Question 4 Next: Question 6 →