Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $S=\{1,2,3,4,5,6,7,8,9,10\}$, $P=\{y \in \mathbb N : y \text { is a prime number}\}$, consider the map $f$ defined as follows: $$\begin{aligned} f:x\in S \rightarrow f(x) \in \wp (P) \end{aligned}$$ and $$\begin{aligned} f(x)=\{y \in P: y \mid x\} \end{aligned}$$

Let $X=\{1,4,5,8,10\}$ and $f(X)=\{\{\emptyset\}, \{2\}, \{5\}, \{2\}, \{2,5\}\}$. Let $\Sigma$ be a partial order defined as follows:

$$\begin{aligned} x\text{ }\Sigma \text{ } y \Leftrightarrow f(x) \subset f (y) \text{ or } x=y\end{aligned}$$

draw the Hasse diagram relative to $(X, \Sigma)$.

The $f$ function clearly isn't injective, because $f(4) = f(8)=\{2\}$. I am unsure how the Hasse diagram should be drawn: in this case I have a repetition, so do I have to omit one of the elements with the same image element? So is my Hasse diagram correct?

enter image description here

share|cite|improve this question
You're specifying the domain and range of $f$, but not which elements map to what. – Henning Makholm Jul 29 '12 at 14:56
I suspect that $\subset$ is the notation for strict inclusion. Maybe you could check it in the text from which you took the problem. (BTW I think it is always good to mention the source of the problem in the post - give the name of the book, or a link, if they are available.) – Martin Sleziak Sep 28 '12 at 8:46

$\Sigma$ isn't a partial order since it lacks the antisymmetry property: $$x \Sigma y \text{ and } y \Sigma x \Rightarrow x=y.$$ Here, $4 \Sigma 8$ and $8 \Sigma 4$ but $4 \neq 8$.

Edit: I just noticed that by $\subset$ you mean proper inclusion. In this case, $\Sigma$ is indeed a partial order. $4$ and $8$ are incomparable so you have to add a node labeled $8$ next to the node labeled 4 with connecting lines $1$-$8$ and $8$-$10$.

share|cite|improve this answer
How do you get $4\mathrel{\Sigma}8$? Neither $\{2\}\subset\{2\}$ nor $4=8$ are true. – Henning Makholm Jul 29 '12 at 15:00

$X$ has 5 particular elements, and nothing that goes on in the definition of $\Sigma$ can change which set $X$ is or what its elements are. The identity of $X$ is independent of what you do with it after defining it. So yes, you need to represent all of those elements in your Hasse diagram.

Also, no matter which strange functions you're using internally in the definition of $\Sigma$, what comes out of the process is just a particular subset of $X\times X$. This exact same relation could have been defined in various other ways -- at its most primitive you could just list all those pairs $(a,b)$ such that $a\mathrel\Sigma b$. Since what you're diagramming is the relation itself, rather than the irrelevant internal details of how the relation arose, you should not attempt to make the diagram encode information about $f$, except to the extent that this information influences the yer-or-no answers to "is this element related to that element"? The diagram cannot represent such information at all.

share|cite|improve this answer

Your Answer


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.