§ Finite topologies and DFS numbering
In this great math overflow question on
How to think about non hausdorff topologies in the finite case , there's an answer that encourages us
to think of them as preorders, which are basically graphs. I wanted to understand
this perspective, as well as connect it to DFS numbers, since they provide a
nice way to embed these topologies into $\mathbb R$.
§ Closure axioms of topology
We can axiomatize a topology using the kurotawski closure axioms. We need an
idempotent monotonic function $c: 2^X \rightarrow 2^X$ which satisfies some
technical conditions. Formally:
- $c(\emptyset) = \emptyset)$ [ $c$ is a strict function: it takes bottoms to bottoms ]
- $A \subseteq c(A)$. [monotonicity ]
- $c$ is idempotent: $c(c(A)) = c(A)$. [idempotence ]
- for all $A, B$ in $X$, $c(A \cup B) = c(A) \cup c(B)$.
Under this, a set is closed if it is a fixed point of $c$: That is, a set $A$
is closed iff $c(A) = A$.
§ Slight weakening into Single axiom version
Interestingly, this also gives a single axiom version of topological axioms,
something that maybe useful for machine learning. The single axiom is that
for all $A, B \subseteq X$, $A \cup c(A) \cup c(C(B)) \subseteq c(A \cup B)$.
This does not provide that $c(\emptyset) = \emptyset$, but it does provide
the other axioms [2-4 ].
§ Continuous functions
A function is continuous iff $f(c(A)) \subseteq c'(f(A))$ for every $A \in X$.
TODO: give examples of why this works, and why we need $(\subseteq)$ and not just $(eq)$.
§ Finite topologies as preorders
We draw an arrow $x \rightarrow y$ iff $x \in Closure(y)$. Alternatively stated,
draw an arrow iff $Closure(x) \subseteq Closure(y)$. That is, we have an injection
from the closure of $x$ into the closure of $y$, and the arrow represents
the injection. Alternatively, we can think of
this as ordering the elements $x$ by "information". A point $x$ has less information
than point $y$ if its closure has fewer points.
§ T0 in terms of closure:
- $X$ is $T_0$ iff for points $p, q \in X$, we have an open set $O$ which contains one of the points but not the other. Formally, either $p \in O \land q \not \in O$, or $p \not \in O \land q \in O$.
- Example of a $T_0$ space is the sierpinski space . Here, we have the open set $\{ \bot \}$ by considering the computation
f(thunk) = force(thunk)
. For more on this perspective, see [Topology is really about computation ](#topology-is-really-about-computation--part-1). This open set contains only $\bot$ and not $\top$. - Closure definition: $X$ is $T_0$ iff $x \neq y \implies c(\{x\}) \neq c(\{y\})$
§ T1 in terms of closure:
- $X$ is $T_1$ iff for all $p, q$ in $X$, we have open sets $U_p, U_q$ such that $U_p, U_q$ are open neighbourhoods of $p, q$ which do not contain the "other point". Formally, we need $p \in U_p$ and $q \not \in U_p$, and similarly $q \in U_q$ and $p \not \in U_q$. That is, $U_p$ and $U_q$ can split $p, q$ apart, but $U_p$ and $U_q$ need not be disjoint.
- Example of $T_1$ is the zariski/co-finite topology on $\mathbb Z$, where the open sets are complements of finite sets. Given two integers $p, q$, use the open sets as the complements of the closed finite sets $U_p = \{q\}^C = \mathbb Z - q$, and $U_q = \{p\}^C = \mathbb Z - p$. These separate $p$ and $q$, but have huge intersection: $U_p \cap U_q = Z - \{ p, q\}$.
- Closure definition: $X$ is $T_1$ iff $c(\{x\}) = \{x\}$.
- T1 has all singleton sets as closed
§ Haussdorf (T2) in terms of closure
- $X$ ix $T_1$ iff for all $p, q$ in $X$, we have open set $U_p, U_q$ such that they are disjoint ( $U_p \cap U_q = \emptyset$) and are neighbourhoods of $p$, $q$: $p \in U_p$ and $q \in U_q$.
- Example of a $T_2$ space is that of the real line, where any two points $p, q$can be separated with epsilon balls with centers $p, q$ and radii $(p - q) / 3$.
- Closure definition : $X$ is $T_2$ iff $x \neq y$ implies there is a set $A \in 2^X$ such that $x \not \in c(A) \land y \not \in c(X - A)$ where $X - A$ is the set complement.
§ Relationship between DFS and closure when the topology is $T0$
If the topology is $T0$, then we know that the relation will be a poset,
and hence the graph will be a DAG. Thus, whenever we have $x \rightarrow y$, we
will get
§ DFS: the T0 case
§ DFS: the back edges