patternMinor
Domain theory: Definition of isomorphisms
Viewed 0 times
theorydefinitiondomainisomorphisms
Problem
Consider the following definitions of CPOs, monotonicity and continuity:
The pair $(M, \leq)$ is called CPO (complete partial order), if
(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
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#81103, answer score: 2
Revisions (0)
No revisions yet.