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

Descrbe about arithmetic and geometric sequences, Descrbe about Arithmetic ...

Descrbe about Arithmetic and Geometric Sequences? When numbers are listed according to a particular pattern, we call the list a sequence. In a sequence, the numbers are separat

Law of cosines - vector, Theorem a → • b → = ||a → || ||b → || cos• ...

Theorem a → • b → = ||a → || ||b → || cos• Proof Let us give a modified version of the diagram above. The three vectors above make the triangle AOB and note tha

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

Fraction, how do you add fraction

how do you add fraction

Generic rectangles and greatest common factors, miaty and yesenia have a gr...

miaty and yesenia have a group of base ten blocks.Misty has six more than yesnia. Yesenia''s blocks repersent 17 together they have 22 blocks,and the total of blocks repersent 85.

Example of multiplication, Example 1: Multiply 432 by 8. Solution: ...

Example 1: Multiply 432 by 8. Solution:        432 ×        8 --------------       3,456 In multiplying the multiplier in the units column to the multiplica

Matrices, suppose you a business owner and selling cloth. the following rep...

suppose you a business owner and selling cloth. the following represents the number of items sold and the cost for each item. use matrix operation to determine the total revenue ov

Integration of sin ³a.cos ³a , writing sin 3 a.cos 3 a = sin 3 a.cos 2 a.co...

writing sin 3 a.cos 3 a = sin 3 a.cos 2 a.cosa = sin 3 a.(1-sin 2 a).cosa put sin a as then cos a da = dt integral(t 3 (1-t 2 ).dt = integral of t 3 - t 5 dt = t 4 /4-t 6 /6

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