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

Determine the total area of the land, John is planning to buy an irregularl...

John is planning to buy an irregularly shaped plot of land. Referring to the diagram, determine the total area of the land. a. 6,400 m 2 b. 5,200 m 2 c. 4,500 m 2 d.

Quadratic equation assignment, what is number of quadratic equation that ar...

what is number of quadratic equation that are unchanged by squaring their roots is There are four such cases x 2   =0 root 0 (x-1) 2 =0  root 1 x(x+1)=0  roots  0 and 1

Distribution of sample means not normal, The distribution of sample means i...

The distribution of sample means is not always a normal distribution. Under what circumstances is the distribution of sample means not normal?

The prerequisites for multiplication, THE PREREQUISITES FOR MULTIPLICATION ...

THE PREREQUISITES FOR MULTIPLICATION : The word 'multiply', used in ordinary language, bears the meaning 'increase enormously For instance, bacteria multiply in favourable conditi

Statistics, The winning team''s score in 21 high school basketball games wa...

The winning team''s score in 21 high school basketball games was recorded. If the sample mean is 54.3 points and the sample standard deviation is 11.0 points, find the 90% confiden

What is pythagorean triples, What is Pythagorean Triples? A set of thre...

What is Pythagorean Triples? A set of three numbers a, b, and c that can satisfy the equation A 2 +b 2 = c 2 , is called a Pythagorean triple. The following is a list of

Evaluate the perimeter of the plot of land, Evaluate the perimeter of the p...

Evaluate the perimeter of the plot of land. a. 260 m b. 340 m c. 360 m d. 320 m To evaluate the perimeter, we must know the length of all sides. According to the dia

Undetermined coefficients, UNDETERMINED COEFFICIENTS The way of Undeter...

UNDETERMINED COEFFICIENTS The way of Undetermined Coefficients for systems is pretty much the same to the second order differential equation case. The simple difference is as t

Find the time it takes to slide down, The time in seconds that it takes for...

The time in seconds that it takes for a sled to slide down a hillside inclined at and angle θ is where d is the length of the slope in metres. Find the time it takes to sli

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