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

Linear Programming, A garden shop wishes to prepare a supply of special fer...

A garden shop wishes to prepare a supply of special fertilizer at a minimal cost by mixing two fertilizers, A and B. The mixture is to contain at least 45 units of phosphate at lea

Which of the subsequent terms does not describe the number 9, Which of the ...

Which of the subsequent terms does NOT describe the number 9? Nine is NOT prime since it has 3 factors; 1, 3, and 9. Prime numbers have only 2 factors.

Determine the area of the regular octagon, Determine the area of the regula...

Determine the area of the regular octagon with the following measurements. a. 224 square units b. 112 square units c. 84 square units d. 169 square units b. See

Area related to circle, If ABCD isaa square of side 6 cm find area of shad...

If ABCD isaa square of side 6 cm find area of shaded region

Marginal probability, Marginal Probability Probability of event A happe...

Marginal Probability Probability of event A happening, denoted by P(A), is called single probability, marginal or unconditional probability. Marginal or Uncondi

Linear equation in two variables., draw the graph of following pair of line...

draw the graph of following pair of linear equation:-2y=4x-6

Mensuration, How do mensuration relate to the real life issues

How do mensuration relate to the real life issues

Calculate expected average time , A car was machine washes every car in 5 m...

A car was machine washes every car in 5 minutes accurately. It has been calculated that customers will arrive as per to a Poisson distribution at an average of 8 per hour. Calculat

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