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

Precalculuc, evaluate the expression and write the result in the form a + b...

evaluate the expression and write the result in the form a + bi. I^37

Estimate percent of the original price will the customer pay, Bikes are on ...

Bikes are on sale for 30% off the original price. What percent of the original price will the customer pay if he gets the bike at the sale price? The original price of the bike

#title.heat loss in a cylindrical pipe., briefly explain how the famous equ...

briefly explain how the famous equation for the loss of heat in a cylindrical pipe is derived

MATH HONORS, HOW DO YOU DO BAR DIAGRAMS ANDESTIMATE IT WITH PERCENTS

HOW DO YOU DO BAR DIAGRAMS ANDESTIMATE IT WITH PERCENTS

Rita, Calculate 50%

Calculate 50%

Algegra, what''s the main purpose of algebra in our daily life

what''s the main purpose of algebra in our daily life

Learning, my math skills are keeping me from getting my ged need help in al...

my math skills are keeping me from getting my ged need help in all areas

6, 200000+500

200000+500

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