Separation axiom implied by semidecidability of comparison

80 Views Asked by At

I am studying computable analysis. What I'm fascinated by is the analogy between computable analysis and general topology: a Wikipedia article

Semidecidable sets are analogous to open sets.

So I treat them essentially the same.

Discrete sets in topology are analogous to sets in computability where equality between elements is semi-decidable.

This would actually make every set decidable, for every set is clopen in discrete topology.

But I'm puzzled with:

Hausdorff sets in topology are analogous to sets in computability where inequality between elements is semi-decidable.

If the "inequality" refers to $≠$, this would mean every cofinite set is open, and thus every finite set is closed. Doesn't that mean the space is $T_1$, but not necessarily $T_2$?

1

There are 1 best solutions below

2
On BEST ANSWER

Saying that $\neq$ is semi-decidable for a space $\mathbf{X}$ is the effective counterpart of saying that the complement of the diagonal $\{(a,b) \mid a \neq b\} \subseteq \mathbf{X} \times \mathbf{X}$ is open. This is a standard example of a condition equivalent to being Hausdorff.

You do need to be careful though with discreteness: In classical topology discrete indeed implies Hausdorff, and you thus don't need to distinguish between equality being semidecidable and equality being decidable. In the effective world, there is a difference though. A counter-example is the quotient of $\mathbb{N}$ by the equivalence relation $\sim$ where $a \sim b$ iff $a = b$ or $a,b \in H$ where $H$ is the Halting set. This space has semidecidable equality, but not decidable equality (so it is computably discrete, but not computably Hausdorff).

As you mention $T_1$, it turns out that that does not have a clear effective counterpart. In fact, some statements that look like computable counterparts are already the computable counterpart to being Hausdorff.

If you want to read more on the computability/topology analogy, I'll be so forward and advertise my article here: Journal arXiv