GO Classes Test Series 2024 | Discrete Mathematics | Test 2 | Question: 21

Answer 1

Answer: A, C

A strict order is irreflexive and transitive. Let the relation $R$ is on $A = \begin{Bmatrix} 1, 2, 3 \end{Bmatrix}$

---

A: Every strict order is asymmetric: Let $R = \begin{Bmatrix}(1,2), (2, 3), (1,3) \end{Bmatrix}$. Now if I try to add an ordered pair $(2, 1)$ to make it symmetric then that forces me to include at least two more ordered pairs which are $(1, 1)$ and $(2,2)$ to keep it transitive but that disregards the irreflexive property. So that is true.

---

B: Every strict order is a total order relation: A total ordered relation (and even the partial order relation for that matter) must have the following three properties:

• Reflexive
• Antisymmetric
• Transitive

Since a strict order is irreflexive, it can NEVER be a TOR.

---

C: Every strict order is antisymmetric: $\forall a,b \in A \begin{pmatrix} (a, b) \in R \Lambda (b,a) \in R => a=b \end{pmatrix}$

This is Vacuously true as both $(a, b)$ and $(b, a)$ together never belongs to $R$. So the antecedent is false making this implication true.

---

D: Every relation which is both Irreflexive and Asymmetric is in strict order: Let $R = \begin{Bmatrix}(1,2), (2, 3)\end{Bmatrix}$. It is both irreflexive and asymmetric but not strict ordered because it is not transitive.

Comments

Excellent answer.

Mistake in “Since a strict order is irreflexive, it can be TOR.”

It should be “Since a strict order is irreflexive, it can NOT be TOR.”

Answer 2

A binary relation $\text{R}$ on a set $\text{A}$ is a strict order on $\text{A}$ iff $\text{R}$ is irreflexive and transitive. It’s easy to show that any transitive irreflexive relation is also asymmetric; i.e., every strict order is asymmetric, so asymmetry comes for free here.
Assume that $\text{R}$ is irreflexive and transitive but not asymmetric, so, we have $(a,b)$ and $(b,a)$ in $\text{R}$ where $a, b$ are different elements. So, by transitivity, we have $(a,a)$ in $\text{R}$, so contradiction because $\text{R}$ is irreflexive.

Similarly, every strict order is antisymmetric because every asymmetric relation is antisymmetric.

Comments

 example for make  D false

	1	2	3
1	(1,1)	(1,2)	(1,3)
2	(2,1)	(2,2)	(2,3)
3	(3,1)	(3,2)	(3,3)

 

if 1. If R is IREF diagonal are not present 

    2. If R is Asym then aRb is present then bRa not present aRb and bRc is present then also that will be asymmetric but we can’t give a guarantee that aRc must present so it may not be transitive.

example R={(1,2) (2,3)} this Iref and asym but not transitive so this will not be strict order.  

 

Answer 3

Option b is wrong

Because if you take A as {1,2,3} and relation

R= {(1,2)} . Now R is transitive and irreflexive.so R is " strict order relation" but it is not a total order relation because elements 1 is not related to 3 and 3 is not related to 1