1. Is the relation represented by the set S a partial ordering? S = { ( a , a ),

Question

1. Is the relation represented by the set S a partial ordering?

S = { (a, a), (b, b), (c, a), (c, c), (c, d), (d, c), (d, d) }

If S is a partial ordering, then explain why. If S is not a partial ordering, then state what properties of partial orderings it does not have. Also, if S does not have a property, then show a counterexample.

2. Suppose that the relation R is a partial ordering, so x R y means that x precedes y in the ordering. Also suppose that we know the following facts about R.

aRc eRh

cRg hRf

gRd bRh

dRf iRb

gRe iRe

Show a total ordering ? that is compatible with what we know about the partial ordering R.

These questions are about partial orderings. In both questions, lower-case letters a, b, c, etc. represent arbitrary distinct objects. 1. (10 points.) Is the relation represented by the set S a partial ordering? If S is a partial ordering, then explain why. If S is not a partial ordering, then state what properties of partial orderings it does not have. Also, if S does not have a property, then show a counterexample. 2. (10 points.) Suppose that the relation R is a partial ordering, so x Ry means that x precedes y in the ordering. Also suppose that we know the following facts about R. a Rc eRh g Rd bRh dRf iRb gRe iRe Show a total ordering that is compatible with what we know about the partial ordering R

Explanation / Answer

A partial ordered set is the set which has the following properties: Reflexive,Anti Symmetric and Transitive.

1. S = { (a, a), (b, b), (c, a), (c, c), (c, d), (d, c), (d, d) }

S is reflexive as it contains (a,a),(b,b),(c,c),(d,d). S is NOT anti symmetric as it contains both (c,d) and (d,c) which makes it not anti symmetric. S is NOT transitive as (d,c) and (c,a) exist but (d,a) does not exist.

Counter Example: Just remove (d,c) and the remaining set S is anti symmetric.

2. A total ordered set is a set with following properties: Reflexive, Anti Symmetric, Transitive and Comparability.

Now compatibility means that if you choose any two elements say a,b then either aRb or bRa.

So for the above relations in Q2,

Just add the following relations so that it becomes a total set.(Just an example)

gRi, iRd, dRe,eRb.

So the following relation is

a<c<g<i<d<e<b<h<f. which is comparable, and hence is a total set.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.