Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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$? –  Brian M. Scott Nov 14 '12 at 1:34
    
I'm sorry, I forgot to attach the diagram. How could I solve this without the graph? –  Mack Nov 14 '12 at 1:38
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  Mack Nov 14 '12 at 20:27
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. –  Brian M. Scott Nov 14 '12 at 20:49
    
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? –  Mack Nov 14 '12 at 20:58
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. –  Brian M. Scott Nov 14 '12 at 21:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.