The proper subset relation and strict partial order

1k Views Asked by At

The proper subset relation, $\subset$, defines a strict partial order on the subsets of $[1,6]$, that is $pow[1,6]$.

(a) What is the size of a maximal chain in this partial order? Describe one.

(b) Describe the largest antichain you can find in this partial order.

(c) What are the maximal and minimal elements? Are they maximum and minimum?

(d) Answer the previous part for the $\subset$ partial order on the set $pow\{1,2,3,4,5,6\} - \emptyset$

1

There are 1 best solutions below

2
On

HINTS:

  1. Can you do any better than to start with $\varnothing$ and add one element at a time?

  2. If $A,B\subseteq\{1,2,3,4,5,6\}$, and $|A|=|B|$, then $\{A,B\}$ is an antichain; why? This means that if $\mathscr{A}$ is a collection of subsets of $\{1,2,3,4,5,6\}$ such that $|A_0|=|A_1|$ for all $A_0,A_1\in\mathscr{A}$, then $\mathscr{A}$ is an antichain. How big an antichain can you form in this way? (How many subsets of size $k$ does $\{1,2,3,4,5,6\}$ have?)

  3. This is trivial: just apply the definitions.

  4. This is no different from (3) at the top end, but getting rid of $\varnothing$ does change the bottom end of the partial order. Here’s where you really need to understand the difference between minimal and minimum.