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¹ Æ.Proposition 0 (Duality): z is a limit point of S Û z is not an interior point of Ø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.
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.
-|
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}.Proposition 4:
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}.
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.
-|
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.A stronger property than continuity requires that each value of the output function be determined by "past" information about the input function:
F is monotoneÛ"f,y, f Í y Þ F(f) Í F(y).
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.
verifiable : open : r.e. ::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.
refutable : closed : co-r.e.::
decidable : clopen : recursive ::
empirical : continuous : computable
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.These classes satisfy closure laws analogous to those for the arithmetical hierarchy, except that existentential quantification is replaced with countable union. Check for yourself.
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).
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].
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.It is easy now to show that we have indices for each finite Borel
Wn + 1[f](y) = $x ØWn[f[x]].
Proposition 6: Sn(S)
Û
$f. S = Wn[f].
-|
Now the usual Cantor diagonal establishes:
Proposition 7 (finite Borel hierarchy theorem): Sn
Ì
Sn
+ 1.
-|
Tot(f) Û "y $z f(y) » zSo
Û "$open
Û ÇÈopen
Û Çopen
A £WB Û ($ 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£WB
Ú
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£WB Ú B£W ØA.
Exercise 8: Prove it.
-|
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.
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.Thus, Lim-eureka is S2-complete.
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.
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.