I'm trying to understand posets better but for the life of me I can't seem to grasp what is required of a chain. So I am given a poset (P([4]), ⊆), and I am trying to find the minimum number of chains that cover the poset and then list out the chains as a set of elements. Do I draw the more complicated Hasse diagram such as this one:
Or the more simplistic one, simplistic being just the elements 1, 2, 3, 4 where 1 connects to 2 and 2 connects to 4 and 1 connects to 3
In the simplistic case, I can see that a chain would be {1, 2, 4} and that there are two chains to cover the poset, but I'm not exactly sure if this is right or not. And looking at the complicated Hasse diagram, well to be frankly honest, I'm lost in terms of trying to find chains in that one.
For reference, a chain in a poset is a subset C ⊆ X such that any pair of elements in C are comparable (For all x,y in C, xRy or yRx)
All help is greatly appreciated, and please do dumb down your answers to a level that I can understand them very easily as combinatoric math is not my greatest strength
Thanks for your time
Best Answer
Look at the two-element sets in the middle of the Hasse diagram:
$$\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}$$
There are six of them, and no two are comparable. That is, if $A$ and $B$ are any two of these sets, then $A\nsubseteq B$, and $B\nsubseteq A$. Thus, no chain in this poset can contain more than one of these six sets. (Remember, if two members of this poset are in the same chain, by definition one of them must be a subset of the other, since that’s the partial order relation here.) This means that you’ll need at least six different chains to cover the entire poset, one for each of these six sets.
In fact six chains will do it. Can you find six chains, one containing each of these six sets, such that every member of the poset (i.e., every subset of $[4]$) is a member of at least one of your six chains? I’ll get you started:
$$\big\{\varnothing,\{1\},\{1,2\},\{1,2,3\},\{1,2,3,4\}\big\}$$
is a chain containing $\{1,2\}$.