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

Adding & subtracting i guess, Jack and his mother paid $11.50 for tickets t...

Jack and his mother paid $11.50 for tickets to the movies, and adults tickets cost $4.50 more than a child ticket what was the cost of each ticket?

Inequalities, seven more than a number is less than or equal to -18

seven more than a number is less than or equal to -18

Find the number of vertices in graph, A graph G has 21 Edges, 3 vertices of...

A graph G has 21 Edges, 3 vertices of degree 4 and other vertices are of degree 3. Find the number of vertices in G.   Ans: It is specified that graph G has 21 edges, so total

Understand the terms quotient and remainder, What other activities can you ...

What other activities can you suggest to help a child understand the terms 'quotient' and 'remainder'? Once children understand the concept and process of division, with enough

Find the common difference of an ap, Find the common difference of an AP wh...

Find the common difference of an AP whose first term is 100 and sum of whose first 6 terms is 5 times the sum of next 6 terms. Ans:    a = 100 APQ a 1 + a 2 + ....... a 6

Geometry, two sides of an equilateral triangle have lengths 3x-1 and 3x-1. ...

two sides of an equilateral triangle have lengths 3x-1 and 3x-1. Which of 27-x or 2x-4 could be the length of the third side?

Total linear attenuation, Consider the task of identifying a 1 cm thick bre...

Consider the task of identifying a 1 cm thick breast cancer that is embedded inside a 4.2 cm thick fibroglandular breast as depicted in Fig. The cancerous tumor has a cross

DECIMALS, the mass of a container is 5.81kg when full with sugar .the mass ...

the mass of a container is 5.81kg when full with sugar .the mass of container is 3.8kg when 3/8 of the sugar is removed.what is the mass of empty container

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