1
$\begingroup$

Given is the set $A = \left\{1,2,3,4,5,6,7\right\}$ with relation $R = \left\{(1,2),(3,2),(2,4),(5,4),(4,6),(4,7)\right\}$

Determine the Hasse diagram for the reflexive-transitive closure of $R$ and determine two upper bounds of $\left\{2,5\right\}$ in this reflexive-transitive close of $R$.

So I've read about Hasse diagrams and the good thing is that you can ignore edges that are transitive and reflexive. So basically, if my understanding is correct, it's sufficient if I just draw the Hasse diagram for the given relation $R$:

 6     7
  \   /
   \ /
    4
   /|
  / |
 5  2
   / \
  /   \
 1     3

Is the Hasse diagram correct like that?

But I'm not sure how I solve the problem with those upper bounds now. It's mentioned to find two lower bounds of $\left\{2,5\right\}$. But now I don't know where to look at in the Hasse diagram? I understand it like that that $\left\{2,5\right\}$ means that we need to look at the "nodes" $2$ and $5$ in the Hasse diagram and check their children. $5$ has no child and thus no lower bound, so we look at $2$. It has as children nodes $1$ and $3$ thus the two lower bounds are $1$ and $3$?

I hope you can tell me because if they ask such a question in an exam I feel pretty helpless : /

$\endgroup$
3
$\begingroup$

No, your diagram is incorrect. You may be confusing reflexive and symmetric, but I can't be sure. For example, your diagram shows 2R3, but in actuality we have 3R2. Similarly, the diagram shows 4R5 instead of 5R4. It doesn't make sense to address the rest of your question until you fix the diagram.

You are confused about upper and lower bounds, I think. A lower bound of a set $S$ is just an element $b$ such that $b\le s$ for every $s\in S.$ Similarly, an upper bound of a set $S$ is just an element $b$ such that $b\ge s$ for every $s\in S.$ Here I'm writing $a\le b$ instead of $aRb$ because it's more intuitive.

So an upper bound of $\{2,5\}$ is an element $\ge 2$ and $\ge 5.$ In the diagram, there are $3$ to choose from: $4,6,7.$ As an aside, in the case, $4$ is the least upper bound. Not only is it a lower bound, but it's smaller than all the other lower bounds.

$\endgroup$
  • $\begingroup$ Thank you, I have edited the Hasse diagram and I believe it's correct now because it seems to "create" every element which belongs to reflexive-transitive closure of $R$ but I still don't understand the second part of the question with the lower bounds, do you? I understand it like that that $\left\{2,5\right\}$ means that we need to look at the "nodes" $2$ and $5$ in the Hasse diagram and check their children. $5$ has no child and thus no lower bound, so we look at $2$. It has as children nodes $1$ and $3$ thus the two lower bounds are $1$ and $3$? $\endgroup$ – roblind Mar 12 '18 at 21:13
  • 1
    $\begingroup$ I'm going to enlarge my answer. I'm a slow typist, so it may be a few minutes. $\endgroup$ – saulspatz Mar 12 '18 at 21:28
  • $\begingroup$ Thank you for the edit and help! :) Just one last question to your last paragraph the first sentence. The element really needs to be $\geq 2$ AND $\geq 5$? $\endgroup$ – roblind Mar 12 '18 at 21:57
  • 1
    $\begingroup$ Yes, that's right. That's typical usage in math, not just in Hasse diagrams. If there are 1000 elements in a set, an upper bound for the set is $\ge$ every one of them. $\endgroup$ – saulspatz Mar 12 '18 at 22:07
  • $\begingroup$ Alright thank you very much I understood this now!! :D $\endgroup$ – roblind Mar 12 '18 at 22:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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