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

Basics of vectors - calculus, Vectors - The Basics Let us start this s...

Vectors - The Basics Let us start this section off with a quick discussion on what is the use of vector.  Vectors are utilized to present quantities that have both a magnitude

Shares and dividend, a man in rested rupee 800 is buying rupee 5 shares and...

a man in rested rupee 800 is buying rupee 5 shares and then are selling at premium of rupee 1.15. He sells all the shares.find profit

Dividing mixed numbers, Dividing Mixed Numbers Dividing mixed numbers i...

Dividing Mixed Numbers Dividing mixed numbers is a 3-step process: 1. Convert the mixed numbers to improper fractions. 2. Divide the fractions 3. Convert the result ba

Fundamentals of math, When there are 4 dots how many chords are they

When there are 4 dots how many chords are they

Calculus, what is a domain of a function?

what is a domain of a function?

BOUNDARY VALUE PROBLEM, Ut=Uxx+A exp(-bx) u(x,0)=A/b^2(1-exp(-bx)) u(0,t)=0...

Ut=Uxx+A exp(-bx) u(x,0)=A/b^2(1-exp(-bx)) u(0,t)=0 u(1,t)=-A/b^2 exp(-b)

Naming fractions greater than 1, the 10 miles assigned to the chess club st...

the 10 miles assigned to the chess club start at the 10 mile point and go to the 20 mile point when the chess club members have cleaned 5/8 of their 10 mile section between which m

Ordinary differential equation, find the normalised differential of the fol...

find the normalised differential of the following {1,x,x^3}

The hurwiz method, The Hurwiz method Hurwiz method was the concept of c...

The Hurwiz method Hurwiz method was the concept of coefficient of optimism or pessimism introduced by L. Hurwicz. The decision maker takes into account both the minimum and max

Ploting of mathematical graphs, how can we represent this mathematical equa...

how can we represent this mathematical equation on a graph y=2x-1

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