5
$\begingroup$

Consider the following definitions of CPOs, monotonicity and continuity: The pair $(M, \leq)$ is called CPO (complete partial order), if

  • $M$ is a set,
  • $\leq$ is a partial order on $M$,
  • there exists a least element according to $\leq$ in $M$ (called bottom, $\bot$),
  • for every chain $m_0, m_1, m_2, \dots$ in $M$ its supremum $\bigsqcup \{m_0, m_1, m_2, \dots\}$ (least upper bound) exists in $M$.

(where a chain is a sequence $m_0, m_1, m_2, \dots$ of elements in $M$ such that for all $i, j \in \mathbb{N}$ $m_i \leq m_j \vee m_j \leq m_i$ holds)

A function $f \colon M \to N$ between two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ is called monotone if for all $a, b \in M$

$$a \leq b \implies f(a) \sqsubseteq f(b)$$

holds.

A function $f \colon M \to N$ between two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ is called continuous, if it is already monotone and for all chains $m_0, m_1, m_2, \dots$ we have

$$f\left(\bigsqcup \{m_0, m_1, m_2, \dots\}\right) = \bigsqcup \{f(m_0), f(m_1), f(m_2), \dots\}.$$

I read in a book using above definitions that two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ are isomorphic if there exists a function $f \colon M \to N$ such that

  • $f$ is bijective
  • $f$ and $f^{-1}$ are continuous (and therefore monotone).

I understand the demand of $f$ and $f^{-1}$ being monotone, so that they preserve the order.


Question: Why is this not sufficient? Why do we also demand $f$ to be continuous? Why its inverse function too? What are examples where a violation of one property would result in a strange view of equivalence? Another question: Is it possible to drop one property, because the other would imply it? I'm thinking about to demand only $f$'s continuity and to show that $f^{-1}$'s continuity follows – however I was not able to do so, or to come up with a counter example.

Edit: I suggest a »domain theory« tag.

$\endgroup$
2
$\begingroup$

I think I have found an answer to my question, by proofing that the monotonicity of $f$ and $f^{-1}$ imply the continuity of $f$ and $f^{-1}$. Please correct me if I made a mistake – I will give you some days to check my proof before I accept my own answer.


Lemma: If a function $f \colon M \to N$ between two cpos is monotonic, the inequality

$$\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\} \leq f\left(\bigsqcup\{ m_0, m_1, m_2, \dots\}\right)$$

holds for all chains $m_0, m_1, m_2, \dots$. This is well known and easy to show, so I will skip the proof of this.


Let $f \colon M \to N$ be now a bijective function between two cpos and let it, and its inverse $f^{-1}$, be monotonic. By the above lemma we have already one side of inequality to proof the continuity of $f$. It remains to show that

$$f\left(\bigsqcup\{ m_0, m_1, m_2, \dots\}\right) \leq \bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}$$

holds for all chains $m_0, m_1, m_2, \dots$ in $M$. Since $$\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\} = f\left(f^{-1}\left(\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}\right)\right),$$

and both $f$ and $f^{-1}$ are monotonic, the above inequality is equivalent to

$$\bigsqcup\{ m_0, m_1, m_2, \dots\} \leq f^{-1}\left(\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}\right).$$

However, again by above lemma we have

$$ f^{-1}\left(\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}\right) \geq \bigsqcup\{f^{-1}(f(m_0)), f^{-1}(f(m_1)), f^{-1}(f(m_2)), \dots\} = \bigsqcup\{ m_0, m_1, m_2, \dots\}.$$

So $f$ is continuous. You show the continuity of $f^{-1}$ in the same way.

$\endgroup$
1
  • 2
    $\begingroup$ The proof looks ok. It is a special case of the following fact from category theory: isomorphisms of categories preserve and reflect colimits. In your case the categories in question are the two posets, the isomorphism are $f$ and $f^{-1}$, and colimits in posets correspond to suprema. $\endgroup$ Sep 12 '17 at 20:46

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.