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

Surface area, Find the amount of sheet metal need to form a conical funnel ...

Find the amount of sheet metal need to form a conical funnel of base radius 30cm with a vertical height of 50cm, allowing for 0.5cm overlap. Find the total surface area?

Algebra, Evaluate: 30 - 12÷3×2 =

Evaluate: 30 - 12÷3×2 =

Write down a game each for teach maths to children, Write down a game each ...

Write down a game each to teach children i) multiplication, ii) what a circle is, iii) estimation skills. Also say what you expect the child to know before you try to t

Indicestitle.., Advantages and disadvantages of paasche indices

Advantages and disadvantages of paasche indices

Division of two like terms, Case 1: Suppose we have two terms 8ab and 4ab. ...

Case 1: Suppose we have two terms 8ab and 4ab. On dividing the first by the second we have 8ab/4ab = 2 or 4ab/8ab = (1/2) depending on whether we consider either 8ab or 4ab as the

Opt math, howwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

howwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww

Example of division of fractions, Example of division of fractions: E...

Example of division of fractions: Example: (4/5)/(2/9) = Solution: Step 1:             Invert the divisor fraction (2/9) to (9/2). Step 2:             Multip

Mathematical formulae, Mathematical Formulae (a ...

Mathematical Formulae (a + b) 2 = a 2 + b 2 + 2ab (a - b) 2 = a 2 + b 2 - 2ab (a + b) 2 +

Find the lesser of two consecutive positive even integers, Find the lesser ...

Find the lesser of two consecutive positive even integers whose product is 168. Let x = the lesser even integer and let x + 2 = the greater even integer. Because product is a k

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