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

Compute the probability of weather, Analysis of questionnaire completed by ...

Analysis of questionnaire completed by holiday makers showed that 0.75 classified their holiday as excellent at Malindi. The probability of hot weather in the resort is 0.6.  If th

Determine the height of building, A 20-foot light post shows a shadow 25 fe...

A 20-foot light post shows a shadow 25 feet long. At the similar time, a building nearby casts a shadow 50 feet long. determine the height of building? a. 40 ft b. 62.5 ft

Fraction, give some examples of fractions that are already reduce

give some examples of fractions that are already reduce

Example of pythagorean theorem, Any 15 foot ladder is resting against the w...

Any 15 foot ladder is resting against the wall. The bottom is at first 10 feet away from the wall & is being pushed in the direction of the wall at a rate of 1 ft/sec. How rapid is

Explain how we converting fractions to percents, Explain how we Converting ...

Explain how we Converting Fractions to Percents ? To convert a fraction to a percent: 1. Convert the fraction to a decimal using long division. 2. Move the decimal point two p

Find the equation for each of the two planes , Find the equation for each o...

Find the equation for each of the two planes that just touch the sphere (x - 1) 2 + (y - 4) 2 + (z - 2)2 = 36 and are parallel to the yz-plane. And give the points on the sphere

Example of factor by grouping, Factor by grouping each of the following. ...

Factor by grouping each of the following. 3x 2 - 2x + 12x - 8 Solution           3x 2 - 2x + 12x - 8 In this case we collect the first two terms & the final two te

Marketing of herbal products , To help Himalya herbal launch a successful m...

To help Himalya herbal launch a successful marketing campaign in the UK

Determine the angle between dec, Using the example provided below, if the m...

Using the example provided below, if the measure ∠AEB = 5x + 40 and ∠BEC = x + 20, determine m∠DEC. a. 40° b. 25° c. 140° d. 65° c. The addition of the measurem

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