Digraph continuity vs topological continuity

84 Views Asked by At

Continuing the topic of Topological "closure" of a binary relation:

Let $\mu$, $\nu$ be binary relations on a set $U$.

Topology $T \mu = \{ E \in \mathscr{P} U \mid \mu [E] \subseteq E \}$ (here $\mu[E]$ is the image of a set $E$ by binary relation $\mu$).

By definition, a function $f$ (on $U$) is a continuous function from $\mu$ to $\nu$ iff $f\circ\mu\subseteq\nu\circ f$. (It is the definition of discrete continuity if we consider $\mu$ and $\nu$ as directed graphs.)

Conjecture If $f$ is a continuous function from $\mu$ to $\nu$ then $f$ is a continuous function from the topology $T\mu$ to the the topology $T\nu$.

1

There are 1 best solutions below

5
On BEST ANSWER

I will identify functions with their "transpose graphs", and not their usual graphs: $$f=\left\{(f(x),x):x\in U\right\}$$ and composition as $$(z,y)(y,x)=(z,x)$$ so that composition of relations and functions becomes $$\nu\circ f=\left\{(z,x):(z,f(x))\in \nu\right\}$$ $$f\circ\mu=\left\{(f(y),x):(y,x)\in\mu\right\}$$ (this is actually more suitable for usual functional notation, where "functions act on the left of elements", but I digress).


First assume $f\circ\mu\subseteq\nu\circ f$, and suppose $E\in T_\nu$, that is, $\nu[E]\subseteq E$. We will prove that $f^{-1}(E)\in T_\mu$, that is, $\mu[f^{-1}(E)]\subseteq f^{-1}(E)$.

Let $y\in\mu[f^{-1}(E)]$. Then there is $x\in U$ with $x\in f^{-1}(E)$ and $(y,x)\in\mu$, thus $$(f(y),y)\in f\quad\text{and}\quad (y,x)\in\mu\quad \text{which implies}\quad (f(y),x)\in f\circ\mu\subseteq\nu\circ f$$ and this means that $(f(y),f(x))\in\nu$. But since $x\in f^{-1}(E)$ (i.e. $f(x)\in E$) then $f(y)\in\nu[E]\subseteq E$, so $y\in f^{-1}(E)$.

This proves that $f$ is $(T_\mu,T_\nu)$-continuous.


The reverse is not true if $\nu$ is not transitive. Let $U=\left\{1,2,3\right\}$, $\mu=\left\{(3,1)\right\}$, $\nu=\left\{(3,2),(2,1)\right\}$. The $\nu$-invariant subsets are $U$, $\left\{2,3\right\}$, $\left\{3\right\}$ and $\varnothing$, and these are also $\mu$-invariant, so the identity map $f=\operatorname{id}_U$ is $(T_\mu,T_\nu)$-continuous, but $$\operatorname{id}_U\circ\mu=\mu\not\subseteq\nu=\nu\circ\operatorname{id}_U.$$


If $\nu$ is transitive then the reverse is true but I'll leave the details to you: An element of $f\circ\mu$ is of the form $(f(y),x)$ where $(y,x)\in\mu$. Let $E_0=\left\{f(x)\right\}$, $E_{n+1}=\nu[E_n]$ and $E=\bigcup_{n\geq 0}E_n$. Then $E$ is $\nu$-invariant so $f^{-1}(E)$ is $\mu$-invariant (by continuity) and contains $x$. Use transitivity of $\nu$ and the definition of $E$ to conclude $(f(y),f(x))\in \nu$ and therefore $(f(y),x)\in\nu\circ f$.