edited by
1,924 views
14 votes
14 votes

Let $R$ be a binary relation over a set $S$. The binary relation $R$ is called an equivalence relation if it is reflexive transitive and symmetric. The relation is called partial order if it is reflexive, transitive and anti symmetric. (Notation: Let $aRb$ denote that order pair $(a, b) ∈ R.$) The relation $R$ is called a well-order if $R$ is a partial order and there does not exist an infinite descending chain (with respect to $R$) within $S$. An infinite sequence $x_{1}, x_{2}...$ of elements of $S$ is called an infinite descending chain if for all $i$ we have $x_{i+1}Rx_{i}$ and $x_{i}\neq x_{i+1}$.

Take $S=\aleph \times \aleph$ and let the binary relation $\sqsubseteq$ over $S$ be such that $\left ( i_{1}, j_{1}\right )\sqsubseteq \left ( i_{2}, j_{2} \right )$ if and only if either $\left ( i_{1}< i_{2} \right )$ or $\left ( \left ( i_{1}= i_{2}\right )\wedge \left ( j_{1}\leq j_{2} \right ) \right )$. Which statement is true of $\sqsubseteq $?

  1. $\sqsubseteq $ is an equivalence relation but not a well order.
  2. $\sqsubseteq $ is a partial order but not a well order.
  3. $\sqsubseteq $ is a partial order and a well order.
  4. $\sqsubseteq $ is an equivalence relation and a well order.
  5. $\sqsubseteq $ is neither a partial order nor an equivalence relation.
edited by

3 Answers

9 votes
9 votes

Answer: C

$S = (i_1j_1) ⊑ (i_2j_2) \text{ iff }  (i_1<i_2) \text{ or } ((i_1=i_2)∧(j_1≤j_2))$

1. $(m,n) R (m,n)$ ?

yes, here $m \not< n ,$ so we go at second criteria.

Now, $m=n$ & $n =n.$ So, this is reflexive.

2. Antisymmetric

$(1,2) R (2,3) \implies (2,3) R (1,2) ?$
No, as $2 \not< 1.$

If you see the definition, it is clear that other than diagonal element no other element is related to itself. So, antisymmetric.

3. Transitivity
$(1,2) R (2,3)$  & $(2,3) R (2,4) \implies (1,2) R (2,4) ?$
Yes. It can be seen easily from the definition of $S.$ Same for any other pairs. Not going to prove this formally.

4. It is not symmetric $(1,2) R (2,3)$ but $(2,3) \not R ( 1,2)$

5. This is well ordered. We do not have infinite descending chain. As we have least element $(0,0)$ our chain stops there.

Ref :-

https://en.wikipedia.org/wiki/Infinite_descending_chain
https://en.wikipedia.org/wiki/Well-order#Examples_and_counterexamples

edited by
1 votes
1 votes

Reflexive?

$(i_1,j_1)R(i_1,j_1)$. So yes.


Symmetric?

 Say $(i_1,j_1)R(i_2,j_2)$ $\epsilon$ $S$ such that $i_1 < i_2$

Then  $(i_2,j_2)R(i_1,j_1)$ does not belong to $S$ because $i_2 > i_1$

This can serve as the counter-example.

So, not symmetric.


Anti symmetric?

Say $(i_1,j_1)R(i_2,j_2)$ $\epsilon$ $S$ such that $i_1 < i_2$ As seen above,  $(i_2,j_2)R(i_1,j_1)$ won't be true.

 

Say $(i_1,j_1)R(i_2,j_2)$ $\epsilon$ $S$ such that $((i_1=i_2)∧(j_1<j_2)).$. So, $(i_2,j_2)R(i_1,j_1)$ won't be true because $j_2 > j_1$

 

Say $(i_1,j_1)R(i_2,j_2)$ $\epsilon$ $S$ such that $((i_1=i_2)∧(j_1=j_2)).$ This is essentially the definition of relexive instance, and hence not a threat to anti-symmetry.

 

This relation is anti-symmetric.


Since we have $S=ℵ×ℵ$, means depending on the definition and context (0,0) or (1,1) is the least element. This ensures that we can't descend down infinitely. So, well order. 

Option C

edited by
0 votes
0 votes

S = (i1j1⊑ (i2j2)  iff  (i1<i2) or ((i1=i2)∧(j1≤j2))
for reflexive 
aRb where a=b here (i1j1⊑ (i2j2
if we take any value which satisfy the reflexive property and exist in set it will also satisfy the given condition
e.g (12) 
⊑ (12)  here  ((i1=i2)∧(j1≤j2)) so its a Reflexive

for anti-symetric 
aRb -> bNRa unless a=b 
here if we take any set like i1<i2 surely it i2≨i1
                                       if i1=i2 and j1≤j2 then surely j2≨j1 
e.g.
(12) ⊑ (23)   exist in S but (23) ⊑ (12) doesn't exist since i1 ≨i2 and j1≨j2 
      
(32) ⊑ (36) exist in S  but   (36) ⊑ (32) doesn't exist  i1=i2 but   j1≨j2
so it is Anti-symmetric 


for Transitive 
aRb & bRc then aRc 
here (i1j1⊑ (i2j2(i2j2⊑ (i3j3) then (i1j1⊑ (i3j3
if i1<i2 & i2<i3 then surely i1<i3 
if i1=i2 & j1≤j2 && i2=i3 &  j2≤j3 then surely i1=i3 & j1
≤j3
so it is Transitive 

Hence it is Poset 

 For well ordered for all xi+1Rxi and xi≠xi+1
(i1j1⊑ (i2j2 given i1<i2 
(21)
 ⊑ (14) is well ordered pair but it doesnt exist in set  S. i1≨i2 && i1 ≠ i2

so i think option B


 

 

Answer:

Related questions

16 votes
16 votes
4 answers
1
40 votes
40 votes
2 answers
3
makhdoom ghaya asked Oct 26, 2015
3,082 views
How many pairs of sets $(A, B)$ are there that satisfy the condition $A, B \subseteq \left\{1, 2,...,5\right\}, A \cap B = \{\}?$$125$$127$$130$$243$$257$