Let $(X, \preceq)$ and $(Y, \ll)$ be partially ordered sets. Suppose there are functions $f : X \to Y$ and $g : Y \to X$ such that $$x \preceq g(y) \iff y \ll f(x)$$ for all $x \in X$, $y \in Y$.

Define the closed elements of $X$ to be all elements of the form $g(f(x))$ and the closed elements of $Y$ to be all elements of the form $f(g(y))$. I have to prove that there is an order-reversing bijection between the closed elements of $X$ and the closed elements of $Y$.

I'm really not sure how to do this. I'm thinking the map would have to be something simple but I can't see what it would be. If you just map $g(f(x)) \mapsto f(x)$ then that isn't necessarily injective and also maps onto $f(X)$ which might be larger than the set of closed elements of $Y$.

I feel like I have to use the property of $f$ and $g$ listed above to derive some other relationship between $f$ and $g$ ... maybe something like $f(g(f(x))) = f(x)$, but I'm not sure.

  • $\begingroup$ are the functions order-reversing? $\endgroup$ – Stefan Hamcke Sep 4 '13 at 16:20
  • $\begingroup$ The functions just satisfy the condition listed on the third line. I don't think that implies they're order-reversing but I'm not totally sure. $\endgroup$ – saurs Sep 4 '13 at 16:26
  • $\begingroup$ If they are antitone (order-reversing), then this is called a Galois connection. $\endgroup$ – Stefan Hamcke Sep 4 '13 at 16:28
  • $\begingroup$ This reminds me the notion of Galois connection en.wikipedia.org/wiki/Galois_connection . $\endgroup$ – user87690 Sep 4 '13 at 16:29

You can prove that $fgf = f$ and $gfg = g$. $f(x) ≤ f(x)$ implies $x ≤ gf(x)$, the same for $fg$. Also $x ≤ x' ≤ gf(x')$ implies $f(x) ≥ f(x')$ so in fact the assumption gives that both $f$ and $g$ are order-reversing and they form a Galois connection or adjoint pair on poset categories. $x ≤ gfgf(x)$ gives $f(x) ≥ fgf(x)$ and $gf(x) ≤ gf(x)$ gives $fgf(x) ≥ f(x)$ so $fgf = f$ and $gfg = g$. Now it follows that $f$ and $g$ restricted to closed elements are desired mutually inverse order-reversing bijections ($fgf = f$ implies $gfgf = gf$ so closed elements are exactly fix-points of $gf$ and the same for $fg$. Again by $fgf = f$ we have that closed elements are exactly images of $f$, $g$.)

Also note that the only asymetric result of the construction is $x ≤ gf(x)$ and $y ≤ fg(y)$. If the assumption was $y ≥ f(x) \iff x ≥ g(y)$ then you would have the same result but $x ≥ gf(x)$ and $y ≥ fg(y)$ would hold. This has to do with what is called “contravariant adjoint situation”. Since both $f$, $g$ are order-reversing, neither of them is right nor left adjoint but both are “adjoints on the right”. For the reversed assumption they would be “adjoints on the left”.

  • $\begingroup$ It should be "... implies $f(x')\le f(x)$" in the third sentence. $\endgroup$ – Stefan Hamcke Sep 4 '13 at 16:46
  • 1
    $\begingroup$ You say "$x \leq gfgf(x)$ gives $ f(x) \leq fgf(x)$". Shouldn't that be "$x \leq gfgf(x)$ gives $ fgf(x) \leq f(x)$" or am I missing something? (Thanks for your help by the way) $\endgroup$ – saurs Sep 4 '13 at 16:52
  • $\begingroup$ That's interesting. So far I didn't know that you can drop the monotonicity from the definition of Galois connection and only need that property. $\endgroup$ – Stefan Hamcke Sep 4 '13 at 16:56
  • $\begingroup$ @StefanH., saurs: Yes you are right, I forgot to change the direction of $≤$ when removing $g$ on the right and adding $f$ on the left. $\endgroup$ – user87690 Sep 4 '13 at 16:56
  • $\begingroup$ Similarly $gf(x) \leq gf(x)$ seems to imply that $f(x) \leq fgf(x)$. But the conclusion is the saem either way. $\endgroup$ – saurs Sep 4 '13 at 16:57

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.