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

Word problem, A computer is programmed to scan the digits of the counting n...

A computer is programmed to scan the digits of the counting numbers.For example,if it scans 1 2 3 4 5 6 7 8 9 10 11 12 13 then it has scanned 17 digits all together. If the comput

Determine the direction cosines and direction angles, Determine or find out...

Determine or find out the direction cosines and direction angles for a = (2, 1, -4) Solution We will require the magnitude of the vector. ||a|| = √ (4+1+16) = √ (21)

Why is the steepness of a curve partially calculate, Can you explain why is...

Can you explain why is the steepness of a curve partially calculated by the units of measurement?

Hello, dans chaque cas recris l expression sous la forme d un rappot reduit...

dans chaque cas recris l expression sous la forme d un rappot reduit 5kg/600g

Introduction to learning to count, INTRODUCTION : Most of us, when plannin...

INTRODUCTION : Most of us, when planning the first mathematical experience for three-year olds, think in terms of helping them memorise numbers from 1 to 20. We also teach them to

Number theory, formula for non negative solutions integral

formula for non negative solutions integral

Solve the right triangle, 1. Solve the right triangle. B = 135     c = 3...

1. Solve the right triangle. B = 135     c = 3.72 A  ≈ ____°    (round to the nearest tenth as needed) 2.  Solve the right triangle, where  a =4 and b =10 The length of

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