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

Total linear attenuation, Consider the task of identifying a 1 cm thick bre...

Consider the task of identifying a 1 cm thick breast cancer that is embedded inside a 4.2 cm thick fibroglandular breast as depicted in Fig. The cancerous tumor has a cross

Fraction, sarah has 12 gel pen. she gave 3/4. how many she have

sarah has 12 gel pen. she gave 3/4. how many she have

Mensuration, find the diameter of circle whose circumference is 26.51

find the diameter of circle whose circumference is 26.51

Probability., an insurance salesman sells policies to 5 men, all of identic...

an insurance salesman sells policies to 5 men, all of identical age in good health. the probability that a man of this particular age will be alive 30 years hence is 2/3.Find the p

Solving problem with linear function, An electric utility company determine...

An electric utility company determines the monthly bill for a residential customer by adding an energy charge of 5.72 cents per kilowatt-hour to its base charge of $16.35 per month

Logarithms, how do they solve log9 = ... 27

how do they solve log9 = ... 27

How many days are there in a year, There are m months in a year, w weeks wi...

There are m months in a year, w weeks within a month and d days in a week. How many days are there in a year? In this problem, multiply d and w to obtain the total days in one

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