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

Solve the limit problem, Solve the Limit problem as stated  Limit x tends... Solve the Limit problem as stated  Limit x tends to 0 [tanx/x]^1/x^2 is ? lim m tends to infinity [cos (x/m)] ^m is? I need the procedure of solving these sums..

Estimate round to the nearest tenth of an inch, One inch equals 2.54 centim... One inch equals 2.54 centimeters. The dimensions of a table made in Europe are 85 cm huge by 120 cm long. What is the width of the table in inches? Round to the nearest tenth of an

How many more miles did he run today, Kevin ran 6.8 miles yesterday and 10.... Kevin ran 6.8 miles yesterday and 10.4 miles presently. How many more miles did he run today? To ?nd out how many more miles he ran today, subtract yesterday's miles from today

Fractions, which fractions is equivalent to 5/ 6 a.20/24 b.9/10 c.8/18 d.... which fractions is equivalent to 5/ 6 a.20/24 b.9/10 c.8/18 d.10/15

Find x if one ball is drawn at random from the box, A box contains 12 balls... A box contains 12 balls out of which x are black .if one ball is drawn at random from the box  what is the probability that it will be a black ball ? If 6 more black balls are   pu

Equations of lines - three dimensional spaces, Equations of Lines In t... Equations of Lines In this part we need to take a view at the equation of a line in R 3 .  As we saw in the earlier section the equation y = mx+b does not explain a line in R

Find the value of a+b, If A, B are acute angles and sinA= cosB, then find t... If A, B are acute angles and sinA= cosB, then find the value of A+B. Ans:    A + B = 90 o

1234 Mathematics, use only the digits 1,2,3 and 4 in any order to write an ... use only the digits 1,2,3 and 4 in any order to write an expression for the numbers 1 to 100. you may only use each digit once. You may use exponents of 1,2,3 and 4 in some of th

Randy, write in factor form 9x3+9x5 write in factor form 9x3+9x5

Proof of: limq?0 (cosq -1)/q = 0 trig limit, Proof of: lim q →0 (co... Proof of: lim q →0 (cos q -1) / q = 0 We will begin by doing the following, lim q →0 (cosq -1)/q = lim q →0 ((cosq - 1)(cosq + 1))/(q (cosq + 1)) = lim q