§ 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 containsone 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 isreally 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 notbe disjoint.
- Example of $T_1$ is the zariski/co-finite topology on $\mathbb Z$, wherethe open sets are complements of finite sets. Given two integers $p, q$, use theopen 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 thatthey 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