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

Solid mensuration, what is the importance of solid mensuration?

what is the importance of solid mensuration?

Show that of all right triangles inscribed in a circle, Show that of all ri...

Show that of all right triangles inscribed in a circle, the triangle with maximum perimeter is isosceles.

By the last gymnastics competition estimate keri total score, In her last g...

In her last gymnastics competition Keri scored a 5.6 on the floor exercise, 5.85 on the vault, and 5.90 on the balance beam. What was Keri's total score? Keri's three scores re

Find out a series solution for differential equation, Find out a series sol...

Find out a series solution for the following differential equation about x 0 = 0 y′′ + y = 0.   Solution Note that in this case p(x)=1 and therefore every point is an or

Example of multiplication, Example 1: Multiply 432 by 8. Solution: ...

Example 1: Multiply 432 by 8. Solution:        432 ×        8 --------------       3,456 In multiplying the multiplier in the units column to the multiplica

Lori, rewrite the problem so that the divisor is a whole number...8.5/2.3

rewrite the problem so that the divisor is a whole number...8.5/2.3

Precalculus, how does sin of x equal negative 1/3

how does sin of x equal negative 1/3

Example of exponential smoothing, Example of Exponential Smoothing ...

Example of Exponential Smoothing By using the previous example and smoothing constant 0.3 generate monthly forecasts Months Sales Forecast

Mensuration, if area of a rectangle is 27 sqmtr and it perimeter is 24 m fi...

if area of a rectangle is 27 sqmtr and it perimeter is 24 m find the length and breath#

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