237 views

Consider the following sentences :

1. $[R, | ]$ is poset. Where $R$ is the set of all real numbers and $|$ is the divisibility relation i.e. for any $a,b$ in $R, a|b$ iff there is some $c$ in $R$ such that $b=a\ast c.$
2. If a relation $R$ on a set $A$ is irreflexive and transitive then $R$ is antisymmetric.

Which of the above statements is correct?

1. Only $1$
2. Only $2$
3. Both
4. None

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?

1. 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.

by

1 comment

Excellent analysis.

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.

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.

edited

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.

1
246 views