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

  • 2
    There isn’t enough information to make the problem meaningful as stated. Are you sure that the problem doesn’t contain more information $-$ perhaps that the partial order relation is $\subseteq$?2012-11-14
  • 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.

  • 0
    How can $e,f,h$ and $j$ be upper bounds on the set $\{a,b,c\}$? They aren't even in the set. Why can't d be an upper bound? It's above those other elements. I am having difficulty understanding the topics maximal and minimal elements, upper and lower bounds, and least upper and greatest lower bound.2012-11-14
  • 1
    @EMACK: The definition is that an element $u$ is an upper bound for a set $S$ if and only if $s\le u$ for all $s\in S$; nothing there says that $u$ has to be in $S$, and in fact it generally isn’t. $d$ isn’t an upper bound for $\{a,b,c\}$ because $c\not\le d$: there is no path from $c$ to $d$ that moves upward at each step.2012-11-14
  • 0
    Oh, so the upper bound has to be greater than all of the elements in a given set; and since, like you said, c and d are not even related to each other, there is no way to tell of one is greater than the other?2012-11-14
  • 1
    @EMACK: More than 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