GO Classes Weekly Quiz 10 | Discrete Mathematics | Set Theory, Mathematical Logic, Lattice | Question: 14

Answer 1

Generally, the mistake that we do with statement S1 is that, we assume that since $[N,|]$ is a poset, so is the $[R,|]$. But what we fundamentally miss is, that the divisibility relation in $N$ satisfies the antisymmetric property. Whereas, $R$ doesn’t provide antisymmetric property with the divisibility relation. This is also the case with $Z,Q,Q’$ with the divisibility relation.

Ex: (2,-2) and (-2,2) both belong to the relation $[R,|]$. Hence, not a Poset.

Question: 1. If $A\subset B$ and $(A,\preceq)$ is a poset then $(B,\preceq)$ is also a Poset?

2. If $A\subset B$ and $(B,\preceq)$ is a poset then $(A,\preceq)$ is also a Poset?

---

S2: If a relation $R$(represents a relation and not the set of real numbers) on a set $A$ is irreflexive and transitive then $R$ is antisymmetric.

To check if the S2 is true we just need to check if the relation $R$ is antisymmetric. Explicitly, we need to check if both $(a,b)\in R$ and $(b,a)\in R$, with $a\neq b$. If they do then $R$ is not anti-symmetric, else $R$ is antisymmetric.

Let, $a\neq b$ . Assume that, $(a,b)\in R$ and $(b,a)\in R$. Then, by $transitivity$ of relation $R$, we have that $(a,a)\in R$. But, this is a contradiction, as $R$   is   $irreflexive$. Thus, our assumption was wrong.

Hence, $R$ is $antisymmetric$. So, S2 is True.

Comments

Excellent analysis.

Students must try to answer the two questions you have asked in your answer.

---

for your question 1 is false and 2 is correct.

Answer 2

1. $[ R,| ]$ is not antisymmetric as $2|-2, -2|2.$ It is reflexive, transitive.

2. Let relation $R$ be Irreflexive & Transitive. Then $R$ is Anti-symmetric.

Proof by Contradiction:

Assume $R$ is  Irreflexive & Transitive but Not Anti-symmetric. Since, $R$ is Irreflexive, to say that $R$ is not antisym, we have to have two pairs $(a,b), (b,a)$ such that $a \neq b,$ in $R$. But since $R$ is Transitive, so, $(a,a) \in R$ which brings Contradiction because $R$ is irreflexive.

Comments

For statement S2 :

Suppose (a1,a2) $\in$ R and (a3,a4) $\in$ R.

Now, we know R is irreflexive, it is given.

Thus, a1 $\neq$ a2 and a3 $\neq$ a4.

Now, it is also given that R is transitive.

Now we can have 2 cases - 

Case 1 : When a2 $\neq$ a3 - 

We've (a1,a2) and (a3,a4) in R and a2 $\neq$ a3 thus transitivity will not add any new elements in R.

Therefore, we don't have (x,y) and (y,x) type of elements in R, $\forall$ x,y A$\in$ A.

Case 2 : When a2 = a3 - 

We've (a1,a2) and (a3,a4) in R and a2 = a3 thus transitivity will add element (a1,a4) in R.

Now, if a1 = a4 then R will violate irreflexive property.

Thus, a1 $\neq$ a4.

Therefore, we don't have (x,y) and (y,x) type of elements in R, $\forall$ x,y $\in$ A.

Therefore, R will be Anti-symmetric.

---

@shishir__roy very small typo at line4 

Thus, a1 ≠≠ a2 and a3 ≠≠ s4.

should be Thus, a1 ≠ ≠ a2 and a3 ≠ ≠ a4.