Prove - digraph of a partial order has no cycle more than 1, Mathematics

Assignment Help:

Prove that the Digraph of a partial order has no cycle of length greater than 1.

Assume that there exists a cycle of length n ≥ 2 in the digraph of a partial order ≤ on a set A. This entails that there are n distinct elements a1 , a2 , a3 , ..., an like that a1 ≤ a2 , a2 ≤ a3 , ..., an-1 ≤ an and an ≤ a1 . Applying the transitivity n-1 times on a1 ≤ a2 , a2 ≤ a3 , ..., an-1 ≤ an , we get a1 ≤ an .As relation ≤ is anti-symmetric a1 ≤ an and an ≤ a1 together entails that a1 = an . This is contrary to the fact that all a1, a2, a3... an are distinct. So, our assumption that there is a cycle of length n ≥ 2 in the digraph of a partial order relation is wrong.

 


Related Discussions:- Prove - digraph of a partial order has no cycle more than 1

The prerequisites for multiplication, THE PREREQUISITES FOR MULTIPLICATION ...

THE PREREQUISITES FOR MULTIPLICATION : The word 'multiply', used in ordinary language, bears the meaning 'increase enormously For instance, bacteria multiply in favourable conditi

Minima, Minima, Maxima and points of inflexion a)      Test for rela...

Minima, Maxima and points of inflexion a)      Test for relative maximum Consider the given function of x whose graph is presented by the figure given below

Project, transportation problem project

transportation problem project

Find the area of the shaded region, ABC is a right angled triangle in which...

ABC is a right angled triangle in which ∠A = 900. Find the area of the shaded region if AB = 6 cm, BC=10cm & I is the centre of the Incircle of ?ABC. Ans: ∠A =90 0 BC

Numerical analysis and computer techniques, write a fortan programme to gen...

write a fortan programme to generate prime number between 1 to 100

#titl., class 10 Q.trigonometric formula of 1 term

class 10 Q.trigonometric formula of 1 term

PARCC Practice Book, Ask question #Minimum 100 words acceptThe top of Kevi...

Ask question #Minimum 100 words acceptThe top of Kevin''s dining room table is 4 feet long, and 3 feet wide. Kevin wants to cover the middle of the table with tiles. He plans to le

Triangles, ABCD is a parallelogram which AB and CD are divides by P and Q. ...

ABCD is a parallelogram which AB and CD are divides by P and Q. Such that AP:PB=3:2 and CQ:QD=4:1. If PQ and AC are meet at R, show that AR=3/7AC.

Compute the measure of the larger angle, Two angles are supplementary. The ...

Two angles are supplementary. The evaluate of one is 30 more than twice the measure of the other. Determine the measure of the larger angle. a. 130° b. 20° c. 50° d. 70

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd