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

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.

 

Posted Date: 5/3/2013 1:50:07 AM | Location : United States







Related Discussions:- Prove - digraph of a partial order has no cycle more than 1, Assignment Help, Ask Question on Prove - digraph of a partial order has no cycle more than 1, Get Answer, Expert's Help, Prove - digraph of a partial order has no cycle more than 1 Discussions

Write discussion on Prove - digraph of a partial order has no cycle more than 1
Your posts are moderated
Related Questions

Three-person Problem of Points: Pascal, Fermat and their old friend the Chevalier de Mere each put $10.00 into a pot, and agree to play a game that has rounds. Each player has the

a company''s advertising expenditures average $5,000 per month. Current sales are $29,000 and the saturation sales level is estimated at $42,000. The sales-response constant is $2,

Explain Multiples ? When a whole number is multiplied by another whole number, the results you get are multiples of the whole numbers. For example,  To find the first four mult



From the data given below calculate the value of first and third quartiles, second and ninth deciles and forty-fifth and fifty-seventh percentiles.

what is 2+2=

into how many smaller part is each centimeter divided

Implicit Differentiation : To this instance we've done quite a few derivatives, however they have all been derivatives of function of the form y = f ( x ) .  Unluckily not all