Consider the 8 element set S-{{0.1,2}, {0,1,2,3}, {0,2,3), {1,2,3}, {1,2}, {0,1)

Question

Consider the 8 element set S-{{0.1,2}, {0,1,2,3}, {0,2,3), {1,2,3}, {1,2}, {0,1)·(02), {2,3,4,5 }} which we now consider with respect to the partial ordering relation of set-inclusion i.e, X precedes Y in the ordering if and only it x C Y (ie, iff every element of X is an element of Y, but not vice-versa). (Note that neither S itself nor the null set is an element of S) List all the minimal elements of S: List all the maximal elements of S List three multiple-element maximal chains of S (Remember that any two distinct sets can have some of their elements in common, and that neither any letter, nor the null set is an element of S): List three maximal anti-chains composed of elements of S

Explanation / Answer

(A)

  A minimal element of a subset S of partially ordered set is an element of S that is not greater than any other element in S.

So, the minimal elements of S: {1,2},{0,1},{0,2},{2,3,4,5}

(B)

A maximal element of a subset S of partially ordered set is an element of S that is not smaller than any other element in S.  

So, the maximal elements of S: {0,1,2,3}, {2,3,4,5}

(C)

We know that, a pair of elements X, Y are comparable if X Y or Y X. Otherwise they are incomparable.

A chain is a subset in which every pair is comparable.

So, three multiple-element maximal chains of S : {{0,1,2},{0,1,2,3}}, {{0,2,3},{0,1,2,3}}, {{1,2,3},{0,1,2,3}}

(D)

We know that, an anti-chain is a subset in which every pair is comparable, i.e.,

  X Y

or

YX

So, three maximal anti-chains composed of elements of S: {{0,1,2},{2,3,4,5}}, {{0,1,2,3},{2,3,4,5}}, {{0,2,3}, {2,3,4,5}}, {{1,2,3},{2,3,4,5}}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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