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
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..

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

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

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

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 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

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

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

write in factor form 9x3+9x5

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