4 ms·
The analogy goes much further if you take it as "open set" =~ "semidecidable property", i.e., you can determine in finite time that something is in the subset,
by maxiepoo 5y ago
The analogy goes much further if you take it as "open set" =~ "semidecidable property", i.e., you can determine in finite time that something is in the subset, but may not halt on an input that is not in the subset. A closed set is one whose complement is semidecidable, i.e., "co-semidecidable". This gives some intuition to the finite intersection vs arbitrary union property (though in computability you would restrict to a kind of "effective" union, but still one that could be infinite). Then sets that are closed and open are the decidable properties.
Then the inverse-image definition of a continuous function is clearly satisfied by computable functions. A function f : A -> B is continuous if for any semidecidable property O on B, the property { x \in A. f(x) \in O } is semidecidable (since f is a computable function).
There's some very cool ideas here like Hausdorff == Diagonal is closed =~ the equality predicate is co-semidecidable, i.e., you can implement a partial inequality function that always returns true if the inputs are not equal.
See Martín Escardó's work for more details: https://www.cs.bham.ac.uk/~mhe/papers/barbados.pdf https://www.cs.bham.ac.uk/~mhe/papers/barbados.pdf
- bade 5y agoYou're absolutely correct. Thanks.