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

Four is added to the quantity two minus the sum of negative, Four is added ...

Four is added to the quantity two minus the sum of negative seven and six. This answer is then multiplied through three. What is the result? This problem translates to the expr

Solve 4 cos(t )= 3 on[-8, Solve 4 cos(t )= 3 on[-8,10]. Solution : Here...

Solve 4 cos(t )= 3 on[-8,10]. Solution : Here the first step is identical to the problems in the previous section. First we need to isolate the cosine on one side by itself & t

Example of inflection point-differential equation, Example of inflection po...

Example of inflection point Determine the points of inflection on the curve of the function y = x 3 Solution The only possible inflexion points will happen where

Between that two call numbers should she place the book, A librarian is ret...

A librarian is returning library books to the shelf. She uses the call numbers to denote while the books belong. She requires placing a book about perennials along with a call numb

the demand forecast, The King Company is producing two types of products: ...

The King Company is producing two types of products: A and B. Both products are produced on the similar machining operation. The machines operate on two 8-hour shifts, 5 days per w

Equation: 4x^4+9x^4=64 , If 4x^4+9x^4=64 then the maximum value of x^2+y^2 ...

If 4x^4+9x^4=64 then the maximum value of x^2+y^2 is solution) From the eq. finding the value of x^2 and putting it in x^2 + y^2.we get 2nd eq. differentiating that and putting

Reason why we start division, Reasons why we start division : The reason w...

Reasons why we start division : The reason we start division by considering the digit in the leftmost place is efficiency and ease . For instance, suppose we divide 417 by 3, we

What did she pay per pound, Mona purchased one and a half pounds of turkey ...

Mona purchased one and a half pounds of turkey at the deli for $6.90. What did she pay per pound? Divide the cost of the turkey by the weight; $6.90 ÷ 1.5 = $4.60.

3, LAST COST METHOD

LAST COST METHOD

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