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

Fourier series - partial differential equations, Fourier series - Partial D...

Fourier series - Partial Differential Equations One more application of series arises in the study of Partial Differential Equations.  One of the more generally employed method

Find ways in which prizes are distributed between student, Find out the num...

Find out the number of ways in which 5 prizes can be distributed among 5 students such that  (a)   Each student may get a prize. (b)  There is no restriction to the number o

The arithmetic mean, Arithmetic mean Arithmetic means is commonly know...

Arithmetic mean Arithmetic means is commonly known as average or mean it is acquired by first of all summing up the values provided and by dividing the total value by the tota

Union operations using union by weight, Show the result of the following se...

Show the result of the following sequence of UNION operations using union-by-weight with the following assumptions Unions are performed on the representatives on the sets th

Quantitative analysis, Suppose the economy is now ‘open’ and thus has an ex...

Suppose the economy is now ‘open’ and thus has an external demand (e.g. from the government, exports, etc.) of the dollar amounts for each respective industry. In the latest budget

Velocity of derivation, Velocity : Recall that it can be thought of as sp...

Velocity : Recall that it can be thought of as special case of the rate of change interpretation. If the situation of an object is specified by f(t ) after t units of time the vel

Curve tracing, How we calculate region for curve tracing

How we calculate region for curve tracing

Fractions, what is the lowest term of 11/121

what is the lowest term of 11/121

Commercial maths, if 500kg of food lasts 40 days for 30 men.how many men wi...

if 500kg of food lasts 40 days for 30 men.how many men will consume 675kg of food in 45 days.

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