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

Geometric progression (g.p.), Learning geometric progression ...

Learning geometric progression vis-á-vis arithmetic progression should make it easier. In geometric progression also we denote the first t

Matrix, find the matrix of the linear transformations T:R2->R2 defined by T...

find the matrix of the linear transformations T:R2->R2 defined by T(x,y,z)=(x+2y,x-3z).

Addition rule - probability rule, The Addition Rule: Mutually Exclusive Eve...

The Addition Rule: Mutually Exclusive Events P(A or B or C) = P(A) + P(B) + P(C) This can be represented by the Venn diagram as follows:

1trig, how do you find the tan, sin, and cos.

how do you find the tan, sin, and cos.

Prove any prime number is irrational, 1. Show that there do not exist integ...

1. Show that there do not exist integers x and y for which 110x + 315y = 12. 2. If a and b are odd integers, prove that a 2 +b 2 is divisible by 2 but is NOT divisible by 4. H

Geometry, how to make an obtuse scalene triangle FAT with m

how to make an obtuse scalene triangle FAT with m

Basic algebraic properties of real numbers, These can be expressed in...

These can be expressed in terms of two fundamental operations of addition and multiplication. If a, b and c are any three real numbers, then;     1.

Title expressions equivalent, 2x40 420x4 7x240 84x20 Explain h...

2x40 420x4 7x240 84x20 Explain how three expressions are equivalent.

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