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

Calculate the probability, Calculate the Probability A bag contains 80...

Calculate the Probability A bag contains 80 balls of such 20 are red, 25 are blue and 35 are white.  A ball is picked at random what is the probability that the ball picked is

Convex rectilinear figure, the sum of the interior angles of a convex recti...

the sum of the interior angles of a convex rectilinear figure is equal to sum of the exterior angles. then the number of sides is

Composite functions, f(x)=4x-3 and g(x)=(x+3)/4 a)Find the function fg(x) ...

f(x)=4x-3 and g(x)=(x+3)/4 a)Find the function fg(x) b)Hence describe the relationship between the functions f and g c)Write down the exact value of fg(sqrt(3))

Find the slope of a line given two points on it, Finding the Slope of a Lin...

Finding the Slope of a Line, Given Two Points on it ? Find the slope of the line passing through the pairs of points (-5, -2) and (2, 4). One way to find the slope is

Linear equation, The sum of the digit number is 7. If the digits are revers...

The sum of the digit number is 7. If the digits are reversed , the number formed is less than the original number. find the number

Evaluate the volume of the shaded region, If the hight of pipe is 18 inches...

If the hight of pipe is 18 inches, what is the volume of the shaded region in terms of π? a. 31.5π in 3 b. 126π in 3 c. 157.5 in 3 d. 58.5 in 3

Rounding, what is the nearest ten thousand of 92,892?

what is the nearest ten thousand of 92,892?

Jason 10 two-point or 2 three-point how many points score, Jason made 10 tw...

Jason made 10 two-point baskets and 2 three-point baskets within Friday's basketball game. He did not score any other points. How many points did he score? Find out the number

Explain adding rational expressions different denominators, Explain Adding ...

Explain Adding Rational Expressions with Different Denominators When you add or subtract fractions or rational expressions that have different denominators, you must first find

Decimals, which one of the following examples represents a repeating decima...

which one of the following examples represents a repeating decimal? 0.123123,1.111114,0.777777,4.252525?

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