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

How much time does larry spend on his dog each day, Larry spends 3/4 hour t...

Larry spends 3/4 hour twice a day walking and playing with his dog. He also spends 1/6 hour twice a day feeding his dog. How much time does Larry spend on his dog each day? Add

Find out the value of the subsequent summation, Using the formulas and prop...

Using the formulas and properties from above find out the value of the subsequent summation. c The first thing that we require to do here is square out the stuff being summe

Undetermined coefficients, In this section we will see the first method whi...

In this section we will see the first method which can be used to find an exact solution to a nonhomogeneous differential equation. y′′ + p (t ) y′ + q (t ) y = g (t) One of

Graph of a function, Graph of a function Help me in understanding the ...

Graph of a function Help me in understanding the concept of graph of a function in linear algebra and matrices.

How much does it car cost her per year, Ashley's car insurance costs her $1...

Ashley's car insurance costs her $115 per month. How much does it cost her per year? Multiply $115 by 12 because there are 12 months in a year; $115 × $12 = $1,380 per year.

Inventory record, a) Complete the inventory record below for an FOQ of 100 ...

a) Complete the inventory record below for an FOQ of 100 units. b) Talk about weaknesses of MRP. List at least 3 and describe each in a sentence or two. Item: A

Example of division of fractions, Example of division of fractions: E...

Example of division of fractions: Example: (4/5)/(2/9) = Solution: Step 1:             Invert the divisor fraction (2/9) to (9/2). Step 2:             Multip

Maximum and minimum values, Find all the local maximum and minimum values a...

Find all the local maximum and minimum values and saddle points of the function f(x, y) = x 2 - xy + y 2 + 9x - 6y + 10

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