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 amplitude of trigonometry function, Consider the trigonometri...

Consider the trigonometric function f(t) = -3 + 4 cos(Π/ 3 (t - 3/2 )). (a) What is the amplitude of f (t)? (b) What is the period of f(t)? (c) What are the maximum and mi

Polynomials, On dividing p(X)=5x^(4)-4x^(3)+3x^(2)-2x+1 by g(x)=x^(2)+2 if ...

On dividing p(X)=5x^(4)-4x^(3)+3x^(2)-2x+1 by g(x)=x^(2)+2 if q(x)=ax^(2)+bx+c, find a,b and c.

Graphical method for interpolation, Graphical Method Whil...

Graphical Method While drawing the graph on a natural scale, the independent variables are marked along the horizontal line and corresponding dependen

Conclude the values of the six trigonometric functions, Conclude the values...

Conclude the values of the six trigonometric functions: Conclude the values of the six trigonometric functions of an angle formed through the x-axis and a line connecting the

Square root., i dont get these questions they are hard for me

i dont get these questions they are hard for me

Linear programming, what is the advantage of dual linear problem programmin...

what is the advantage of dual linear problem programming when we maximize profit then what is need to minimize cost of the same problem

Interpolation and extrapolation, Interpolation is a method of s...

Interpolation is a method of statistical estimation and the word literally means 'making insertions'. Let us consider a well-known situation whi

Define an ordered rooted tree, Define an ordered rooted tree. Cite any two ...

Define an ordered rooted tree. Cite any two applications of the tree structure, also illustrate using an example each the purpose of the usage.   Ans: A  tree is a graph like t

Geometry, find the value of 0 that makes cos 21 degrees = sin 0 statement t...

find the value of 0 that makes cos 21 degrees = sin 0 statement true.

Unit normal vector - three dimensional space, Unit Normal Vector - Three Di...

Unit Normal Vector - Three Dimensional Space The unit normal vector is illustrated to be, N (t) = → T' (t) / (|| T → ' (t)||) The unit normal is orthogonal or normal or

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