Consider the endorelation isPrereqFor defined on the set of

Consider the endorelation isPrereqFor, defined on the set of UMW courses. We say x isPrereqFor y if passing course x is required before you are allowed to take course y. Otherwise, we say x isPrereqFor y. For example, ARTH 114 isPrereqFor CLAS 305, and CPSC 110 isPrereqFor CPSC 405 (since you can’t take 405 without 305, and you can’t take 305 without 220, and you can’t take 220 without 110), but CPSC 305 isPrereqFor CPSC 240 and MUTH 471 isPrereqFor MUTH 471. Is isPrereqFor a partial order? Explain why or why not.

Solution

R being a relation defined is partial order if R is reflexive, antisymmetric and transitive

Now the relation PrereqF is defined as(x,y) where x is a pre-requisite for the course y

(x,x) belongs to relation R since each and every course will be pre-requisite of itself and you need to clear the course before opting for other advanced courses.

Ex - MUTH 471 isPrereqFor MUTH 471

Hence the given relation is reflexive

Antisymmetric means that the only way for both aRb and bRa to hold is if a = b.

Let us assume x is a pre-requisite for course y

=> (x,y) belongs to R

but (y,x) will not belong to R since we first need to do the course x before doing the course y and the equality holds only in the case when both the courses are equal

The relation is transitive if aRb, bRc and aRc

(a,b) => a course is required for doing the b course

(b,c) => b course is required for doing the c course

(a,c) => a course is required for doing the c course

Given statement is not correct by quoting the above example

a = CPSC 110, b = CPSC 220, c = CPSC 305

aRb, bRc, but aRc is not true since CPSC 110 is not pre-requisite for 305 and we can\'t do CPSC 305 after doing CPSC 110 before doing CPSC 220

Hence the relation is not a partial order relation