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

#tiword problem proportions, The scale of a map is 0.5 in 25mi the actua...

The scale of a map is 0.5 in 25mi the actual distance between two cities is 725mi write a proportion that represents the relationship how far apart will the cities be on the map

Calculate the monthly payment amount of the loan, Consider a student loan o...

Consider a student loan of $12,500 at a fixed APR of 12% for 25 years, 1. What is the monthly payment amount? 2. What is the total payment over the term of the loan? 3. OF

Analysis of algorithm running time - undirected graph, Problem. You are giv...

Problem. You are given an undirected graph G = (V,E) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight of either {1, 2, . .

Determine the approximate raw act score, Using the same mean and standard d...

Using the same mean and standard deviation as mean m = 20.1 and a standard deviation s = 5.8. Joe was informed that he scored at the 68 th percentile on the ACT, what was Joe's ap

Math, the size of my sitting room is 7metres by 6metres . i bought a rug fo...

the size of my sitting room is 7metres by 6metres . i bought a rug for covering the centre of its floor. one metre of the floor around the edge of the room is not to be covered by

Find x if one ball is drawn at random from the box, A box contains 12 balls...

A box contains 12 balls out of which x are black .if one ball is drawn at random from the box  what is the probability that it will be a black ball ? If 6 more black balls are   pu

Mathematical formulae, Mathematical Formulae (a ...

Mathematical Formulae (a + b) 2 = a 2 + b 2 + 2ab (a - b) 2 = a 2 + b 2 - 2ab (a + b) 2 +

#permutation, #The digits 1,2,3,4and 5 are arranged in random order,to form...

#The digits 1,2,3,4and 5 are arranged in random order,to form a five-digit number. Find the probability that the number is a. an odd number. b.less than 23,000

Simultaneous equations, two rolls of carpet cost £574, the first cost £8 pe...

two rolls of carpet cost £574, the first cost £8 per meter, the second which is 7m longer costs £7 p/m. how many meters are there in each roll

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