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

Two even digits , Find the number of six-digit positive integers that can b...

Find the number of six-digit positive integers that can be formed using the digits 1,2, 3, 4, and 5 (every of which may be repeated) if the number must start with two even digits o

Proof of: limq?0 (cosq -1)/q = 0 trig limit, Proof of: lim q →0 (co...

Proof of: lim q →0 (cos q -1) / q = 0 We will begin by doing the following, lim q →0 (cosq -1)/q = lim q →0 ((cosq - 1)(cosq + 1))/(q (cosq + 1)) = lim q

Whats this, how do you determine if a graph has direct variation

how do you determine if a graph has direct variation

Algebra, please tell me what is algebra and how i can understand it

please tell me what is algebra and how i can understand it

Earth geometry, calculate the shortest distance between A and B 40degrees w...

calculate the shortest distance between A and B 40degrees west and 50 degrees east respectively laying along 57 degrees north

Estimate whose time was the fastest, Nancy, Jennifer, Alex, and Joy ran a r...

Nancy, Jennifer, Alex, and Joy ran a race. Nancy's time was 50.24 seconds, Jennifer's was 50.32, Alex's was 50.9, and Joy's was 50.2. Whose time was the fastest? The fastest ti

Multiplying mixed numbers, Q. Multiplying Mixed Numbers? Ans. Mult...

Q. Multiplying Mixed Numbers? Ans. Multiplying mixed numbers is a 3-step process: 1. Convert the mixed numbers to improper fractions 2. Multiply the fractions 3.

Homotopy, prove same homotopy type is an equivalent relation

prove same homotopy type is an equivalent relation

How many permutations of the letters a b c d e f g h, How many permutations...

How many permutations of the letters A B C D E F G H consist of string DEF?    Ans: It is the dilemma of finding number of words that can be formed along with the given 8 lette

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