Given is a binary relation. Determine the Hasse diagram for it and two upper bounds

396 Views Asked by At

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 : /

1

There are 1 best solutions below

6
On BEST ANSWER

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.