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

Theory of numbers, show that all primes except 2, are of the form 4n-1 or 4...

show that all primes except 2, are of the form 4n-1 or 4n+1

Elps in maths, 25 cookies have to be divided equally among 4 children.hw ca...

25 cookies have to be divided equally among 4 children.hw can we use elps to answer this question?

Diffrence between integers and rational numbers, Q. Give basic Diffrence be...

Q. Give basic Diffrence between Integers and Rational Numbers? Ans. Integers The integers are positive and negative whole numbers. The integers are closed under ad

Geometry, In the diagram points V,W,X,Y and Z are collinear, VZ=52, XZ= 20 ...

In the diagram points V,W,X,Y and Z are collinear, VZ=52, XZ= 20 AND WX=XY=YZ. Find the indicated length of WX, VW, WY, VX, WZ, and VY

Geometria, un prisma retto ha per base un rombo avente una diagonale lunga ...

un prisma retto ha per base un rombo avente una diagonale lunga 24cm. sapendo che la superficie laterale e quella totale misurano rispettivamente 2800cm e3568cm ,calcola la misura

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

What price tag will he put on the item, The manager of a specialty store ma...

The manager of a specialty store marks up imported products 110%. If a vase imported from Italy costs him $35, what price tag will he put on the item? To ?nd out the price he s

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