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 a₁ , a₂ , a₃ , ..., an like that a₁ ≤ a₂ , a2 ≤ a₃ , ..., an-1 ≤ a_n and an ≤ a₁ . Applying the transitivity n-1 times on a₁ ≤ a₂ , a₂ ≤ a₃ , ..., a_n-1 ≤ a_n , we get a1 ≤ an .As relation ≤ is anti-symmetric a1 ≤ a_n and a_n ≤ a₁ together entails that a₁ = a_n . This is contrary to the fact that all a_1, a₂, a₃... a_n 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

Ask an Expert

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

Write your message here..

Related Questions

FACTORISATION, 2x+4x 2x+4x

Three person problem of points, Three-person Problem of Points: Pascal, Fer... 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

Quantitative Technique in Marketing, a company''s advertising expenditures ... 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, Explain Multiples ? When a whole number is multiplie... 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

Nombor berarah, pendaraban dan pendaraban dan

Intigrations, intigration techiniqes intigration techiniqes

first and third quartiles, From the data given below calculate the value o... 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= what is 2+2=

Measurement, into how many smaller part is each centimeter divided into how many smaller part is each centimeter divided

Implicit differentiation, Implicit Differentiation : To this instance w... 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