14.  Topology and Epistemology

Kevin T. Kelly
Department of Philosophy
Carnegie Mellon University


 
 

A Little Point-Set Topology

A topological space is a pair (X, X), where X is a set and X is a collection of subsets of X satisfying:
  1. X(X)
  2. X(Æ)
  3. X is closed under finite intersection.
  4. X is closed under arbitrary union.
A set is open (in the space) just in case it is in X.
A set is closed just in case is complement is open.
A clopen set is both closed and open.
A basis for a topological space is a collection of sets that generates the open sets of the space when closed under arbitrary union.
A space is separableÛ it has a countable basis.

Cute example:  X has two elements a, b.
X = {{a, b}, {a}, Æ}.
Thus, {a} is open but not closed and {b} is closed but not open.

Standard example:  Let R be the real numbers.
A half-open interval is a set of form [x, y) = {z: x £z<y}.
An open set is a union of half-open intervals.

The "open" and "closed" talk is justified by the fact that in real line, each open interval (x, y) is open (but not closed) and each closed interval [x, y] is closed but not open.  In the real line, the only clopen sets are the trivial sets R, Æ.

Exercise 3:  Topology arose in the foundations of analysis, as an epistemological grounding for the calculus.  Unfortunately, the usual presentation in terms of disks with dotted borders obscures the deeply epistemological character of the subject.  Here is a way of seeing the epistemological dimension of topology directly. Argue informally that the collection of all "empirically verifiable hypotheses" constitutes the open sets of a topological space.  What do you think the points in the space correspond to?  What sorts of cognitive limitations would screw up your argument?

We will be interested primarily in the following spaces, which make the epistemological metaphor explicit.

The Baire space:  Let Fun be the set of all total unary functions on N.
Let [q] denote the set of all total functions extending finite function q.
Cylinder = {[q]: q is a finite function}.
Let O consist of sets formed by taking arbitrary unions of elements of Cylinder.
Let Baire = (F, O).

Positive information space: Just like Baire space except that we start out with the set Part of all partial functions on N and topologize by taking cylinders of these.  Call the resulting space Pos.

Elements of Baire space may be thought of as "data streams" involving outcomes through time drawn from a countably infinite set. Think of the data as coming it sequentially.
Elements of Pos may be thought of as possible data that may be presented at any time, possibly with repetitions.  Unlike Baire and Cantor space, it may be impossible to "empirically decide" whether the function is defined in a given place.

Exercise 2:  Show that Pos and Baire are topological spaces.

Exercise 3:  Show that each singleton {f} is closed but not open in Baire.  Hint: think about the complement.
Show that each fan [q] is clopen in Baire but is properly open in Pos.  Hint: think about functions "smaller" than q.
Think about the preceding exercise and show that Pos has no non-trivial clopen sets. Hint: recall the case argument in Rice's theorem and look at the "epistemology" discussion in the next section.
Give an intuitive interpretation of the result in terms of empirical verifiability.  Which situation is closer to computability theory?

If we think of open sets as "neighborhoods", then a limit point of a set is a point that is so close that every neighborhood around it catches some of the set.  Let S be an arbitrary subset of X.  Define:

z is a limit point of S in (X, X) Û "A, X(A) ÙA(z) ÞAÇ S¹ Æ.
z is an interior point of S in (X, X) Û $A, X(A) ÙA(z) ÙA Ç ØS = Æ.
z is a boundary point of S in (X, X) Û z is a limit point of S and of ØS.
Proposition 0 (Duality):  z is a limit point of S Û z is not an interior point of ØS.

Proof:  By the form of the definition.
-|

Proposition 1:  Either z is an interior point of S or an interior point of ØS or a boundary point of S.

Proof:  By duality, a limit point of both S and ØS is an interior point of neither.
-|

Epistemology

In Baire, a limit point of set S is a function f such such that any finite information q Í f presented byf is consistent with S.  So no information about f could possibly refute S!  Thus, the zero constant function (the sun will always rise) is a limit point of its complement (the sun will stop rising some time).  That doesn't pose any difficulty if S is true in (i.e.,   is an element of S).  But what if f is not an element of S?  Then any information received from world (in which S is false) is consistent with the truth of S.  That is the classical problem of induction!
The problem of induction is the problem of missing limit points!
An interior point is a "data stream" that eventually affords evidence verifying S.  A boundary point of S is not an interior point but it is a limit point, so it poses the problem of induction  either for S or for ØS.  Here is a striking statement:
The problem of induction for S arises precisely only in the boundary of S.
In Pos, the everywhere undefined function Æ is a limit point of every set (null information can be extended in every possible way).  That is why the everywhere undefined function was such a potent source of undecidability arguments in chapter 8. Putting it "outside" of a hypothesis ensures that the hypothesis is missing a limit point so the problem of induction arises.

These concepts provide a more constructive characterization of open and closed sets.

Proposition 2: A is closed Û A contains each of its limit points.

Proof:  Suppose A is closed.
Suppose ØA(z).
 ØA is open (definition of closed).
 ØA contains z but misses all of A.
So z is not a limit point of A.

Conversely, suppose A contains all of its limit points.
Then for each point z in ØA, there is an open set S[z] that contains z but misses all of A.
The union Èz Î A S[z] exhausts ØA and misses all of A.
-|

Proposition 3: A is open Û each point of A is an interior point.

Proof: Suppose A is open.
Suppose A(z).
Then A witnesses that z is interior to A.

Conversely, suppose that each point z of A is an interior point.
Then for each z, there is an open set S[z] Í A that contains z.
The union Èz Î A S[z] exhausts A and contains only elements of A.
Hence, the union is precisely A.
-|

The closure of A = cl(A) =  {z Î X: is a limit point of A}.
The interior of A = int(A) = {z Î X: is an interior point of A}.
The boundry of A = bdry(A) = {z Î X: is a boundary point of A}.
Proposition 4:
  1. cl(A) = the least closed superset of A.
  2. int(A) = the greatest open subset of A.
  3. bdry(A) = cl(A) - int(A).
Proof:  1. Suppose z is a limit point of A.
Then by the definition, z is a limit point of B.
Apply proposition 3.
So each closed superset of A contains z.
So the least one does.

Conversely, suppose z is an element of each closed superset of A.
So in particular, z is an element of A.

2. From 1, by duality.

3.  By proposition 1.
-|

Maps and Continuity

The concept of open set is mainly employed to define continuity.  Geometrically, continuity reflects stretching and shrinking without tearing or pasting.  Epistemically (and more fundamentally) it reflects an empirical process according to which approximations of the output are produced in response to increasing information about the input (perhaps with a time lag).
Let F: X®X.
Now define:
F is continuousÛ" open S, F-1(S) is open.
Geometrically, if there is a "gap"or discontinuity in the graph of a unary function defined everywhere on the reals, the pre-image of an open interval containing the point of discontinuity will not be open (why?).

Let's consider what continuity amounts to in the space Pit.

F is empiricalÛ "f "x, y  ((F(f))(x) » y Û $ finite q Í f. (F(q))(x) » y).
Proposition 5:  In the space Pit, F is continuousÛ F is empirical .

Proof:  Suppose F is empirical.
Let basis element [q] be given.
Let f be in the preimage of [q], so that F(f) Î [q].
Then for each x Îdom(q), y,q(x) » y Û $ finite dx Í f. (F(d))(x) » y).
Form the finite union df = Èx Îdom(q)dx.
Thus, df is a finite function.
By construction, [df ] Í F-1([q]) and f Î [df ].
Hence, ÈfÎF-1([q])df = F-1([q]).
So F-1([q]) is open.
To see that the preimage of an arbitrary open set is open, form the open preimage of each basis element included in the set and take the union of these, which is open by axiom 4.

Conversely, suppose F is continuous.
Exercise 4:  Complete the proof.
-|

In Pit, we will focus on two properties of maps:

F is continuous (empirical) Û "f "x, y (F(f))(x) » y Û$ finite q. (F(q))(x) » y.
F is monotoneÛ"f,y, f Í y Þ F(f) Í F(y).
A stronger property than continuity requires that each value of the output function be determined by "past" information about the input function:
F is LipschitzÛ"f "x, y (F(f))(x) » y Û$q. max(dom(q)) £x Ù (F(q))(x) » y.
Exercise 5:  Give an example of an operator on Pos that is continuous but not Lipschitz.  Find an example of an operator that is continuous but not monotone.  Find an example of an operator that is monotone but not continuous or Lipschitz.

The Borel Hierarchy

Topology alone gives rise to a hierarchy analogous to the arithmetical hierarchy of recursion theory.  Here's an extended analogy.
verifiable : open : r.e. ::
refutable : closed : co-r.e.::
decidable : clopen : recursive ::
empirical : continuous : computable
The Borel or "bold-faced" hierarchy on Pit is defined as follows, by transfinite recursion on the ordinals.  The idea is to start out with open sets and to build complexity by countable union and complementation.  Think of the existential quantifiers in the arithmetical hierarchy as countable, "r.e. unions" or unions over r.e. sets of indices.  Thus, the Borel hierarchy allows "ideal" verification in the base case and "ideal" disjunctions at each complexity jump.  In both places, the arithmetical hierarchy insists on an effective concept.

I start with S1 because there are no non-trivial clopen sets in Pos so we cannot recover the open sets as countable unions of clopen sets.   In Baire space, we can start with S0 =  the clopen sets as in recursion theory, since every open set is a countable union of fans, which are clopen sets.  In this respect, Baire is more analogous to computability theory than Pos is.  Here's a way to think of it:  Pos is more analogous to the situation with index sets and Baire is more analogous to the situation of watching a computation evolve, step by step.  In recursion theory, definedness at a position involves an existential quantifier (e.g., halting) but simulating a computation up to a given stage is primitive recursive (empiricallly decidable).

S1(S) Û S is open.
Sa(S) Û $ countable G Í Èg <aSb . S= ÈP Î G ØP.
Pa(S) Û Sa(ØS).
Da(S) Û Sa(S) ÙPa(S).
S0(S) Û P0(S) Û D1(S).
These classes satisfy closure laws analogous to those for the arithmetical hierarchy, except that existentential quantification is replaced with countable union.  Check for yourself.

The initial segment of the hierarchy of height w is called the finite Borel hierarchy.

To establish a finite Borel hierarchy theorem (i.e., the claim that each natural valued level involves something new), we follow our earlier approach of setting up an indexing for each class and diagonalizing once for all over each indexing.  The technique goes back at least to Kuratowski.

We can't use natural numbers as indices, of course, since there are uncountably many open sets.  But we can use functions as indices.

Here's the trick, which works for both Pos and Baire:
Recall the ff indexing q[k] of finite the functions in chapter 8.

q[n](x) = mz £ n $w£ n(<x, z> = d(n, w)).
Each open set S is a countable union of fans [q].
We may, therefore, uniquely code S by listing the finite functions that determine its fans.
W1[f](y) Û $xq[f(x)] Íy.
To deal with the recursive clause, we dovetail one infinite sequence into another to simulate existential quantification over an infinite sequence of variables.

Let d be a function.
Let d[x] denote the restriction of y to the domain {<x, 0>, <x, 1>, ..., <x, n>, ...}.
So given a countable collection of functions f0, ..., fn, ..., we can concoct a single d such that for each x, y,

d[x](<x, y>)  = fx(y).
Now given a countable collection Wn[f0], ..., Wn[fn], ..., we can construct d for f0, ..., fn, ..., as just described and let
Wn + 1[d] = ÈnØWn[f0].
To summarize:
W1[f](y) Û $xq[f(x)] Í y.
Wn + 1[f](y) = $x ØWn[f[x]].
It is easy now to show that we have indices for each finite Borel

Proposition 6:  Sn(S) Û $f. S = Wn[f].
-|

Now the usual Cantor diagonal establishes:
Proposition 7 (finite Borel hierarchy theorem):  Sn Ì Sn + 1.
-|

Tarski-Kuratowski Computations in Topology

The problem of finding upper bounds in the finite Borel hierarchy is to express the set in question in terms of countable unions and intersections of basic open sets (cylinders).  In Pos, cylinders are properly open and count as an extra union.  In Baire they are clopen and count as union-free.  Clearly there will be differences.  For example, totality is trivial (and hence clopen) in Baire but is highly nontrivial in Pos.
Tot(f) Û "y $z f(y) » z
Û "$open
Û ÇÈopen
Û Çopen
So
P2(Tot) in Pos space.
D1(Tot) in Baire space.

Games and Continuous m-Reducibility (Wadge Reducibility)

A Wadge reduction is a continuous many-one reduction.  Believe it or not, this obvious concept is named after a Berkeley graduate student who first worked out the theory as late as the 1980s.
A £W B Û ($ continuous F such that "z, A(z) Û B(F(z))).
Exercise 6:  Show that Wadge reducibility satisfies the obvious topological versions of the usual properties of m-reduction in recursion theory.  In particular, show that it preserves the finite Borel complexity classes.  Hint:  the base case is just the topological definition of continuity!  There is a different way of understanding continuity:  it is just the choice of the right kind of map to satisfy preservation of verifiability downward under many-one reducibility.

Exercise 7:  Show that the obvious topological version of the halting problem (based on the above indexing of the r.e. sets) is open-complete with respect to Wadge reducibility.  Hint:  follow the strategy we used for K.  Does anything change?

An infinite game of perfect information consists of two playersE and O and a winning set W ÍBaire.
Each player plays a natural number, starting with player E, then O, then E, etc., with E playing in even positions and O playing on odd positions.
On a given, infinite play, we say that E wins just in case the play sequence ends up in W.  Otherwise, O wins.  In other words, E tries to drive the sequence into W and O tries to keep it out.
Each player employs a strategy that determines the next play given the plays of one's opponent so far.
A winning strategy for a player wins against all possible opposing strategies.
Since every play sequence is played by some strategy, a winning strategy wins against all possible opposing play sequences.

From the preceding discussion, a strategy determines a continuous (in fact Lipschitz) operator on Baire. Think of the opponent's play sequence as the input and of one's own play sequence as the output.
Consider the following Wadge game with winning set

W[A, B](f) Û the even subsequence of f is in B or the odd subsequence of f is not in A.
Here's the interesting connection made by Wadge:

Proposition 8:
A winning strategy for E in W[A, B] witnesses A £WB.
A winning strategy for O in W[A, B] witnesses B £W ØA.

Proof:  Immediate from the definitions.
-|

A game is determined just either player has a winning strategy.
It it immediate from the preceding result that:

Corollary 9:  If W[A, B] is determined then A £W B Ú B £W ØA.
-|

Notice that one player or the other has to win, but that doesn't immediately imply that either player can be predestined to win, as in tic-tac-toe.  In fact,

Proposition 9: (Gale-Stewart):  Some W is not determined.

Proof:  By a diagonalization using the axiom of choice.  Well-order the strategies for both players and well-order the possible play sequences.  Now proceed by ordinal stages, adding the first play sequence to W or to ØW that witnesses failure of the current strategy to be a winning strategy.  No strategy wins the constructed game
-|

The following is a major set theoretic result and is beyond the scope of the course:

Proposition 9: (Martin's Borel Determinacy Theorem):  If W is Borel then W is determined.
-|

Corollary 10:  For all Borel sets, A £W B Ú B £W ØA.

Exercise 8:  Prove it.
-|

More Epistemology!

Let F be a continuous operator on the Baire space.  We have seen that we may think of F as an empirical process that takes in ever more successive inputs along input function f and that (occasionally) determines more values along the ouput function g.  That is the very image of an empirical process.

Suppose we think of output 1 as a sign that the empirical process is sure that the input stream f satisfies some empirical hypothsis H, which is a subset of Baire.  Think of this as an empirical analogue of "halting" on an input.  We may think of verification with certainty as producing 1 eventually just in case the hypothesis is true of the given input stream.  Define:

Eureka(g) Û 1 occurs in g.
An empirical verification method for H is then just a Wadge reduction witnessing H £ One.
By Wadge's lemma,
H £ Eureka Ú Eureka £ ØH.
So what is a Wadge reduction witnessing the second disjunct?  It is a "demon" who watches the output stream of the scientist and produces a data stream that makes H false just in case the output stream eventually includes a 1, indicating that the scientist has verified the hypothesis.  Thus, Wadge's lemma says that either the scientist or nature (the demon) has a winning strategy in the game of verification.

Eureka is clearly open (why?)
Also, each open set has a verifying scientist and hence is Wadge-reducible to Eureka (just wait for verification of a cylinder in H before outputing 1).
So we have that:

Proposition 7:  Eureka is open-complete.
-|
In other words, a completeness theorem for a success criterion is a Kantian transcendental deduction for that criterion: i.e., a necessary and sufficient structural condition (given by the complexity class) for success of the required kind.

The story can be continued.  Define

Lim-eureka(g) Û g stabilizes to 1.
Think of this as a limiting success criterion for science.  A hypothesis is verifiable in the limit just in case there exists a method that stabilizes to one if and only if the data stream makes the hypothesis true.

Lim-eureka is S2 by Tarski-Kuratowski computation.
Also, each S2 set is verifiable in the limit:

Break the hypothesis into closed subsets.
Enumerate the closed subsets.
Put a bumping pointer at the beginning of the enumeration.  As data come in, bump the pointer each time the closed set pointed to is refuted (i.e., when the complement is verified, according to the preceding construction).
Each time the pointer bumps, conjecture zero.  Otherwise conjecture 1.
Thus, Lim-eureka is S2-complete.

Now we can show that a set is not in S2 by means of a Wadge game between science and nature.

Proposition 8:  The relation defined by

REC(g) Ûg is recursive
is not S2.

Proof:  It suffices to find a winning strategy in the wadge game W[Lim-eureka, ØREC].
Here's how it works.  So long as the "scientist" (the odd player) outputs 1 (indicating confidence in REC), we present the characteristic function of K.
As soon as the scientist changes his mind, we write down 2's.
If the scientist converges to 1 we present the characteristic function of K with chunks of 2's inserted at various points.  Because the chunks between the 2's can be recovered, this function reduces K and hence is not recursive.
Otherwise, we present a function that is a finite variant of the constant 2 function, which is recursive.
Either way, the scienist loses.
-|

A natural criterion of success is decidability in the limit, which requires that the method stabilize to 1 if H is true and stabilize to 0 otherwise.

Exercise 8:  Show that decidability in the limit is possible exactly when the hypothesis is D2.

We can carry the picture higher.  Say that a hypothesis is gradually verifiable just in case there exists a method that ouputs codes of rationals (i.e. k/n is coded by <k, n>) such that the rationals get ever closer to 1 just in case the  hypothesis is true.
Gradual refutability is the obvious dual concept.
Gradual decidability requires both.

Exercise 9:  Characterize the complexity of hypotheses that are gradually verifiable, refutable, and decidable, respectively.  Watch out for the decidable case.

Exercise 10: J.J. Thompson proposed that the atom is a "raisin pudding" consisting of indivisible particles suspended in a continuous medium.  Suppose that your assistant is armed with an infinitely sharp knife and that he can eventually cut any divisible bit of matter if he tries long enough. What is the best sense in which science can test J.J.'s theory?  Hint: describe the outcomes of your assistant's experiments as an infinite tape of natural numbers.