0
$\begingroup$

The question is, Find the lower and upper bounds of the subsets $\{a, b, c\}$, $\{j, h\}$, and $\{a, c, d, f\}$ in the poset.

A poset is of the form $(S,R)$, where $S$ is the set, and $R$ is the relation, right? So, what would be the set? I figure that the relation is that the ordered-pairs are in alphabetical order, is that right? enter image description here

  • 0
    I'm sorry, I forgot to attach the diagram. How could I solve this without the graph?2012-11-14

1 Answers 1

3

This is a Hasse diagram: $\langle x,y\rangle\in R$ if and only if there is a path upwards from $x$ to $y$. For example, $\langle b,d\rangle,\langle b,g\rangle,\langle b,h\rangle,\langle b,e\rangle,\langle b,f\rangle$, and $\langle b,j\rangle$ are all in $R$, but no other pair with $b$ as first component belongs to $R$. For convenience let me write $x\le y$ for $\langle x,y\rangle\in R$.

The upper bounds of the set $\{a,b,c\}$ are therefore $e,f,h$, and $j$: these are the elements that are $\ge$ all three of $a,b$, and $c$. The least upper bound of $\{a,b,c\}$ is therefore $e$, since $e\le e,f,h,j$. The only lower bound for the set is $a$: nothing else is $\le$ all three of $a,b$, and $c$.

The set $\{j,h\}$ has no upper bound: there is no $x$ such that $j\le x$ and $h\le x$. The set does have six lower bounds, though, of which the greatest is ... ?

I’ll leave the last one to you for now; it offers no new complications.

Added: Here’s a list of all of the ordered pairs belonging to the partial order represented by the diagram:

$\begin{align*} &\langle a,a\rangle,\langle a,b\rangle,\langle a,c\rangle,\langle a,d\rangle,\langle a,e\rangle,\langle a,f\rangle,\langle a,g\rangle,\langle a,h\rangle,\langle a,j\rangle,\\ &\langle b,b\rangle,\langle b,d\rangle,\langle b,e\rangle,\langle b,f\rangle,\langle b,g\rangle,\langle b,h\rangle,\langle b,j\rangle,\\ &\langle c,c\rangle,\langle c,e\rangle,\langle c,f\rangle,\langle c,h\rangle,\langle c,j\rangle,\\ &\langle d,d\rangle,\langle d,f\rangle,\langle d,g\rangle,\langle d,h\rangle,\langle d,j\rangle,\\ &\langle e,e\rangle,\langle e,f\rangle,\langle e,h\rangle,\langle e,j\rangle,\\ &\langle f,f\rangle,\langle f,h\rangle,\langle f,j\rangle,\\ &\langle g,g\rangle,\langle g,h\rangle,\\ &\langle h,h\rangle,\\ &\langle j,j\rangle \end{align*}$

It may help resolve some confusions.

  • 1
    @EMACK: More tha$n$ that: neither is greater than the other. The simply aren’t related in this partial order. I’ve added a list of all the ordered pairs to my answer; it may help a bit.2012-11-14