1
$\begingroup$

I am struggling with a proof related to the mapping of posets. Let $P_1$and $P_2$ are posets, and $f$ an order preserving map from $P_1$ to $P_2$. $$g(Z):= f^{-1}[Z]$$ $g$ goes from the set of all down-sets of $P_2$ to the down-sets of $P_1$. I need to prove that for every $Z$ in the down-sets of $P_2$:

  1. $g$ is a map from the down-sets $P_2$ to down-sets $P_1$.

  2. $f$ is order embedding if and only if g is onto down-sets $P_1$.

  3. $f$ is onto $P_2$ if and only if $g$ is one to one.

So, for the first one I don't know what I have to do to prove that it is a map, it seems clear that it is, as if $f$ is defined for every set in $P_1$ to every set in $P_2$, the inverse would be a map as well, moreover, we can take "some" (the down-set) of those elements in $P_2$, the inverse function will be defined for it. I would appreciate the input on wheather my reasoning is correct, and if it is id like some input on how to translate that into formal proof. If it is not, I would like to know how to do it.

For the second part, call $O$ the set of down-sets. First, assume $f$ is order embedding, so for all $x,y \in P_1 : \ x \le y \iff f(x) \le f(y)$.
Let $Z \in O(P_1)$, because it is a member Assume $g$ is onto, then the range is $O(P_1)$. The inverse of an order preserving map is order preserving.

For the third, Assume $f$ is onto $P_2$, then $ran(f)=P_2$. In search of a contradiction, assume $g$ is not one to one. My idea is: if $g$ is not one to one, then 2 elements of $O(P_2)$ can go to the same element in $O(P_1)$ so when i take the inverse, $f$... i have a problem. I was thinking about setting $a < c \in O(P_2)$ and $g(a) = g(c)$, but i don't know how else to procede.

I don't really know how else to procede in these, I also would very very much appreciate the help with formalising the ideas, I'm working writing properly, but sometimes can't translate the concepts to a formal writing.

$\endgroup$
1
$\begingroup$

So, for the first one I don't know what I have to do to prove that it is a map, it seems clear that it is, as if $f$ is defined for every set in $P_1$ to every set in $P_2$, the inverse would be a map as well, moreover, we can take "some" (the down-set) of those elements in $P_2$, the inverse function will be defined for it. I would appreciate the input on wheather my reasoning is correct, and if it is id like some input on how to translate that into formal proof. If it is not, I would like to know how to do it.

I don't understand what you're saying so I can't comment on the correctness of your reasoning. I will however comment on the part where you say it is clear that $g$ is a map.

Regardless of how clear that is, you're being asked to prove more than $g$ being a map, you're being asked to prove that $g$ is a map from $\mathcal O(P_2)$ to $\mathcal O(P_1)$, so you need to prove that for every $Z\in \mathcal O(P_2)$, it holds that $f^{-1}[Z]$ is a down-set of $P_1$.

To prove this take $x,y\in P_1$ such that $y\leq x$ and $x\in f^{-1}[Z]$. The goal is to prove that $y\in f^{-1}[Z]$. By definition $y\in f^{-1}[Z]\iff f(y)\in f[Z]$. So it suffices to prove that $f(y)\in Z$. To prove this you'll need the fact that $Z$ is a down-set and $f$ is order preserving.

Now you've earned the right to write $g\colon \mathcal O(P_2)\to \mathcal O(P_1)$.

For the second part, call $O$ the set of down-sets. First, assume $f$ is order embedding, so for all $x,y \in P_1 : \ x \le y \iff f(x) \le f(y)$.
Let $Z \in O(P_1)$, because it is a member Assume $g$ is onto, then the range is $O(P_1)$. The inverse of an order preserving map is order preserving.

It's an equivalence, you seem to be starting by $\implies$, so you need to prove that $g\colon \mathcal O(P_2)\to \mathcal O(P_1)$ is onto. In this respect you just typed "Let $Z \in O(P_1)$, because it is a member" and then you started proving the direction $\Longleftarrow$, as is suggest by the sentence "Assume $g$ is onto". Here too you don't seem to have proved what's required, namely that $f$ is an embedding. And you talk about the inverse without knowing if $f$ is injective, not every order-preserving map is injective.

To prove $\implies$, assume $f$ is an embedding. You wish to prove that $g$ is surjective, that is that $\forall Y\in \mathcal O(P_1)\exists Z\in \mathcal O(P_2)\left(g(Z)=Y\right)$. Let $Y\in \mathcal O(P_1)$. It's natural to try $Z':=f[Y]$. Is $Z'$ a down-set? Not necessarily. Try $Z:=\mathord{\downarrow} Z'$ instead. Does it hold that $g(Z)=Y$? In other symbols, does it hold that $f^{-1}\left[\mathord{\downarrow} f\left[Y \right]\right]=Y?$ Try to prove it. You'll need to use the fact that $f$ is an embedding.

To prove $\Longleftarrow$, start by supposing that $g$ is onto. It's already given that $f$ is order-preserving so all that is left is to prove that $\forall x,y\in P_1(f(x)\leq f(y)\implies x\leq y)$. Let $x,y\in P_1$ be such that $f(x)\leq f(y)$. Consider the down-sets $\mathord{\downarrow} x$ and $\mathord{\downarrow} y$. Since $g$ is onto, there exist down-sets $Z_x, Z_y\in \mathcal O(P_2)$ such that $g\left(Z_x\right)=\mathord{\downarrow} x$ and $g(Z_y)=\mathord{\downarrow} y$. Note that $f(x)\in Z_x$, prove that $f(x)\in Z_y$, infer that $x\in \mathord{\downarrow} y$ and conclude that $x\leq y$.

For the third, Assume $f$ is onto $P_2$, then $ran(f)=P_2$. In search of a contradiction, assume $g$ is not one to one. My idea is: if $g$ is not one to one, then 2 elements of $O(P_2)$ can go to the same element in $O(P_1)$ so when i take the inverse, $f$... i have a problem. I was thinking about setting $a < c \in O(P_2)$ and $g(a) = g(c)$, but i don't know how else to procede.

Your try here seems legitimate. In fact, because $f$ is surjective, it is also injective so you're allowed to talk about the inverse of $f$. In any case I don't see how to make your proof work without doing and I do below (which avoids contradiction).

For $\Longrightarrow$, assume $f$ is onto. The goal is to prove that $g$ is injective, i.e., that for all $Z_1, Z_2\in \mathcal O(P_2)$ it holds that $f^{-1}\left[Z_1\right]=f^{-1}\left[Z_2\right]\implies Z_1=Z_2$. Since $f$ is surjective and $f^{-1}\left[Z_1\right]=f^{-1} \left[Z_2\right]\implies f\left[f^{-1}\left[Z_1\right]\right]=f\left[f^{-1}\left[Z_2\right]\right]$, this is actually an elementary set theory result which has nothing to do with order and it has been done thousands of times before, see it for instance here.

For $\Longleftarrow$, one possibility is to prove it by contraposition, that is, suppose that $f$ isn't surjective and prove that $g$ isn't one-to-one. Well, assuming $f$ isn't surjective, there exists $z\in P_2$ which isn't in the image of $f$. Now consider $\mathord{\downarrow} z$ and $\left(\mathord{\downarrow} z\right)\setminus \{z\}$ and show that $g\left(\mathord{\downarrow} z\right)=g\left(\left(\mathord{\downarrow} z\right)\setminus \{z\}\right)$ (you'll need the fact that $z$ isn't in the image of $f$). This finalizes the proof.

$\endgroup$
  • $\begingroup$ I've given a few hints for 1. and 2. I don't have time to write about 3. now. Try to work with what I've typed. $\endgroup$ – Git Gud Jan 21 '15 at 19:51
  • $\begingroup$ Hi, thank you very much for your answer, things are getting clearer. I'm still struggling with the third one, I have tried using a similar construction with $Z:= \downarrow Z'$, but I'm still having issues on how to procede. $\endgroup$ – Sara Jan 22 '15 at 11:26
  • $\begingroup$ @Sara I added a proof for 3. Make sure you handle the details and let me know if you need further help. $\endgroup$ – Git Gud Jan 22 '15 at 11:58
  • $\begingroup$ Thank you, I think I got it, very good way to explain it. $\endgroup$ – Sara Jan 22 '15 at 15:25
  • $\begingroup$ @Sara You're welcome. $\endgroup$ – Git Gud Jan 22 '15 at 15:29

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.