How to prove that $fg$ and $gf$ are order embeddings?

Question

From Wikipedia, we know that

Given two posets $(S,\preceq_S)$ and $(T,\preceq_T)$, a function $f:S\to T$ is an order embedding if $f$ satisfies: $$ \forall x,y\in S, \quad x \preceq_S y \Leftrightarrow f(x) \preceq_T f(y) $$

Similarly, we can define a reverse embedding:

Given two posets $(S,\preceq_S)$ and $(T,\preceq_T)$, a function $f:S\to T$ is an reverse embedding if $f$ satisfies: $$ \forall x,y\in S, \quad x \preceq_S y \Leftrightarrow f(y) \preceq_T f(x) $$

Now, we return to the question, given two posets $(S,\preceq_S)$ and $(T,\preceq_T)$, $f:S\to T$, $g:T\to S$ are both reverse embeddings, how to prove that $fg$ and $gf$ are non-decreasing order embeddings if and only if $x\preceq_S g(y)\Leftrightarrow y\preceq_T f(x)$?

Note: $fg$ and $gf$ are non-decreasing order embeddings means: $$ x \preceq_S gf(x)\quad \mathrm{and}\quad y \preceq_T fg(y) $$

---

I thought for a long time, but only figured out how to prove the necessity:

From the question we know $fg$ and $gf$ are non-decreasing order embeddings, and because $f$ and $g$ are both reverse embeddings, we could obtain that $$ x\preceq_S g(y) \Rightarrow fg(y) \preceq_T f(x) \Rightarrow y \preceq_T fg(y) \preceq_T f(x) \Rightarrow y \preceq_T f(x) $$ Similarly, $$ y \preceq_T f(x) \Rightarrow gf(x) \preceq_S g(y) \Rightarrow x \preceq_S gf(x) \preceq_S g(y) \Rightarrow x \preceq_S g(y) $$

I still haven't come up with proof of sufficiency, could you help me solve it?

Thank you!

Answer 1

Assume $x\leq_S g(y)\Leftrightarrow y\leq_T f(x)$ for all $x\in S$ and $y\in T$.

For all $x\in S$, since $f(x)\leq_T f(x)$, we get $x\leq g(f(x))$ [applying $y\leq_T f(x)\Rightarrow x\leq_S g(y)$ with $y = f(x)$].

For all $y\in T$, ssince $g(y)\leq_S g(y)$, we get $y\leq f(g(x))$ [applying $x\leq_S g(y)\Rightarrow y\leq_T f(x)$ with $x = g(y)$].

---

There's something very strange happening with the terminology in your question. You define "$f\colon S\to T$ is an order embedding" to mean "$x\leq_S y\Rightarrow f(x)\leq_T f(y)$". But then you seem to redefine "$f\colon S\to S$ is an order embedding" to mean "$x\leq_S f(x)$". Not every order embedding satisfies the latter property. I would call an order embedding satisfying the property "non-decreasing".

So the correct statement would be: If $f\colon S\to T$ and $g\colon T\to S$ are reverse embeddings, then $gf\colon S\to S$ and $fg\colon T\to T$ are non-decreasing order embeddings if and only if for all $x\in S$ and $y\in T$, $x\leq_S g(y)\Leftrightarrow y\leq_T f(x)$.