GATE CSE
First time here? Checkout the FAQ!
x
+4 votes
201 views

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.
asked in Set Theory & Algebra by Veteran (39.7k points) 256 1308 1941 | 201 views
It is well ordered. option (c) is correct.
you are correct !

2 Answers

+2 votes

Answer -> C

S = (i1j1) ⊑ (i2j2)  iff  (i1<i2) or ((i1=i2)∧(j1≤j2))

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

yes, here m !< n , so we go at second criteria.

Now m=n & n =n. So This is reflexive.

2. Antisymmetric

(1,2) R (2,3)

Is (2,3) R (1,2) ? No as 2 < 1.

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

3. Transitive ->
(1,2) R (2,3)  & (2,3) R (2,4) (It is easy to prove)

(1,2) R (2,4) ? Yes. It can be seen easily from following property

S = (i1j1) ⊑ (i2j2)  iff  (i1<i2) or ((i1=i2)∧(j1≤j2)).

Not going to prove this formally.

4. It is Not reflexive (1,2) R (2,3) but (2,3 ) ~R ( 3,2)

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

Ref :-

https://en.wikipedia.org/wiki/Infinite_descending_chain

https://books.google.co.in/books?id=OR5KAAAAQBAJ&pg=PA17&lpg=PA17&dq=does+natural+no+have+infinite+descending+chain&source=bl&ots=dDJdZ26vWP&sig=WMJUx-35YMNbgkR5twmKDMwL2bo&hl=en&sa=X&ved=0ahUKEwje9of1-rfJAhUSC44KHRqGDI4Q6AEIKjAC#v=onepage&q=does%20natural%20no%20have%20infinite%20descending%20chain&f=false

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

 

answered by Veteran (45.7k points) 171 533 843
How does it not have infinite descending chain?

@Akash  how can you say (0,0) is the least element . (-1,-2)R(-1,-1) is also satisfying the relation . so a/c to me its not well ordered . so  option b should be the answer a/c to me.

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


 

 

answered by Veteran (15.3k points) 17 51 129

it is well order also , as there is least element (0,0)     [ if N = 0,1,2,... ]

the given sequence is infinite ascending chain. not descending chain. 

a well-order if R is a partial order and there does not exist an infinite descending chain (with respect to R) within S

by default well order is partial order , which is reflexive.

 

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23398 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8264 Points

  4. srestha

    6296 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4348 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Notable Question KISHALAY DAS
Notable Question sh!va
Notable Question abhijeetbzu
Great Question jothee
Popular Question rahul sharma 5
Nice Question mohit kumar 5
Notable Question rishu_darkshadow
Nice Comment Pranay Datta 1
Copy Editor Shivansh Gupta
Nice Comment KULDEEP SINGH 2
27,324 questions
35,176 answers
84,108 comments
33,279 users