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

Percents, write as a percent 6/10

write as a percent 6/10

Partial differential equations, I need expert who can solve 10 set of PDE w...

I need expert who can solve 10 set of PDE with constant of integration.

Complex eigenvalues, It is the last case that we need to take a look at. Th...

It is the last case that we need to take a look at. Throughout this section we will look at solutions to the system, x?' = A x? Here the eigenvalues of the matrix A are compl

What is slope of a line, What is Slope of a Line ? A line can have a "...

What is Slope of a Line ? A line can have a "steep" slope or a "gradual" slope. slope = rise/run The "rise" is the distance going up or down. The "run" is the distance goin

How to converting fractions to decimals explain with example, How to Conver...

How to Converting Fractions to Decimals explain with example? To convert fractions to decimals, divide the numerator by the denominator. The quotient is the decimal. Ex

Math reasoning, The probability that a certain region in mexico will be hit...

The probability that a certain region in mexico will be hit by a hurricane in any given year is .06. What is the probability that the region will be hit by at least one hurricane i

People fit, How many people ca fi in a small cars without seats?

How many people ca fi in a small cars without seats?

Substitute 6 for r in the formula a = r^2 and solve for a, Find the area of...

Find the area of a circle along with a radius of 6 inches. The formula for the area of a circle is A = πr 2 . Use 3.14 for π. Substitute  6 for r in the formula A = πr 2 and solve

Aging, The average age of a woman and her daughter is 16 years. The ratio o...

The average age of a woman and her daughter is 16 years. The ratio of their ages is 7: 1. Then the woman''s age is

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