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

Numertic methods, solve by factorization method; 10x-6y-3z=100, -6x+10y-5z=...

solve by factorization method; 10x-6y-3z=100, -6x+10y-5z=100, -3x-5y+10z=100

Word problems, A baseball card was worth $5.00 in 1940. It doubled in value...

A baseball card was worth $5.00 in 1940. It doubled in value every decade. How much was it worth in 2000?

Fractions, how do you do fractions mixed numbers and how do you add and sub...

how do you do fractions mixed numbers and how do you add and subtract fractions.

Complementary addition model, E1) How is the 'comparison model' different...

E1) How is the 'comparison model' different from the 'complementary addition model'? E2) Create one word problem related to the children's world for each of the 4 models liste

Interpretations of definite integral, Interpretations of Definite Integral ...

Interpretations of Definite Integral There are some quick interpretations of the definite integral which we can give here. Firstly, one possible interpretation of the defini

Physical fitness association, Physical fitness association 1 mile run. It i...

Physical fitness association 1 mile run. It is known to have a normal distribution, mean 450 sec. SD 50 sec. How many in the top 10% fastest runners? Need to know what time they ha

2 step equations, What is a two step equation that equals 8 ?

What is a two step equation that equals 8 ?

Frequency polygon, how to compute the frequncy polygon of the scores?

how to compute the frequncy polygon of the scores?

Circle, Circle Well, let's recall just what a circle is. A circle is al...

Circle Well, let's recall just what a circle is. A circle is all the points which are the similar distance, r - called the radius, from a point, ( h, k ) - called the center. I

Algebra, prove That J[i] is an euclidean ring

prove That J[i] is an euclidean ring

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