I have already given an argument for the non-consonance of the Sorgenfrey line Rℓ here. I would like to deal with the case of the space Q of rational numbers, after Costantini and Watson [1]. This would be a bit too long to cover entirely, so the bulk of the explanation will be for another time. I will explain why the compact subsets of Q are all scattered, a notion that I will explain below. Reading between the lines, the Costantini-Watson argument relies on a property that I will characterize through the use of a topological game G(K), resembling the strong Choquet game (see Section 7.6 in the book), in which we will see that player I has a winning strategy if K is compact and scattered—and that is an if and only if in any T2 space. I have not seen that published anywhere, but maybe I just don’t know enough. In any case, I feel that characterization of compact scattered sets through a topological game is worthy of some attention.
Scattered compact subsets
I said that we would see that all the compact subsets of Q are scattered. And hence, we need to understand that notion first.
Let X be a topological space. An isolated point of a subset D of X is any point x of D that has an open neighborhood U in X such that U ∩ D = {x}; if you prefer, such that {x} is open in D seen as a subspace of X. The points of D that are not isolated are called the limit points of D, and those are exactly the points of D that are limits of nets of points of D–{x}.
A subset D of X is dense-in-itself if and only if every point of D is a limit point of D, namely if and only if it has no isolated point. A scattered space is a space whose only dense-in-itself subset is the empty set.
Q itself is dense-in-itself, as a subset of itself; in other words, Q has no isolated point. Hence Q is not scattered. However, we have the following, which, rather amazingly, follows from the Baire property.
Lemma A. Every non-empty compact subset of Q has at least one isolated point. Hence every compact subset of Q is scattered (as a topological subspace of Q).
Proof. Let K be a compact subset of Q. We consider K as a subspace of Q. As such, it is T2, because Q is T2. Being compact and T2, K is locally compact (Proposition 4.8.8 in the book). Being T2, K is sober (Proposition 8.2.12), and every locally compact sober space is Choquet-complete, hence Baire (Proposition 8.3.24). We can arrive at the same conclusion by the following, alternate route. Since K is compact in Q, it is also compact in R (in particular, sequentially compact). The natural metric d on R turns it into a complete metric space, and we know that every (sequentially) compact subspace of a complete metric space is itself complete (Proposition 3.4.6). Therefore K is completely metrizable, hence Baire. You may use Theorem 7.6.15 plus Proposition 8.3.24 for that, but you may also have learned that every complete metric space is Baire independently.
Anyway, K is a Baire subspace of Q. This means that the intersection of countably many dense open subsets of K is dense. Taking complements, the union of countably many closed sets with empty interiors (in K) has empty interior (in K). We consider the sets {x}, where x ranges over the countably many elements of K. Those sets are closed. For each x ∈ K, {x} has non-empty interior in K if and only if {x} is open in K, if and only if {x} = U ∩ K for some open subset U of Q, if and only if x is isolated in K. Hence, if K has no isolated point, then all the sets {x} with x ∈ K are closed sets with empty interior, and their union is K, whose interior (in K) is K itself; hence, if K has no isolated point, then it is empty. By contraposition, if K is non-empty, then it has an isolated point.
Let now D be any non-empty dense-in-itself subset of K. The closure clK(D) of D in K is compact, since it is a closed subset of a compact set. It is also non-empty, so it has an isolated point x, as we have proved in the first part of the lemma. By definition of ‘isolated’, U ∩ clK(D) = {x} for some open neighborhood U (in K) of x. In particular, U intersects clK(D); then, it must also intersect D, and the only point at which U and D can intersect must be x. It follows that x ∈ U ∩ D ⊆ U ∩ clK(D) = {x}, so U ∩ D = {x}. This means that x is isolated in D, which is impossible since D is dense-in-itself. ☐
We will also need the following pretty easy observation.
Lemma B. Every subset of a scattered space is scattered.
Proof. Let K be a scattered space, and A be a subset of K, seen as a subspace. We consider any dense-in-itself subset D of A. If D had an isolated point x in K, then by definition there would be an open neighborhood U of x in K such that U ∩ D = {x}. Then U ∩ A would be an open neighborhood of x in A, with the property that x ∈ (U ∩ A) ∩ D ⊆ U ∩ D = {x}, so (U ∩ A) ∩ D = {x}; hence x would be an isolated point of D in A, contradicting the fact that D is dense-in-itself in A. Therefore D has no isolated point in K, meaning that D is dense-in-itself in K. Since K is scattered, D must be empty. We have shown that every dense-in-itself subset D of A is empty. Therefore, A is scattered. ☐
Decomposing compact scattered subsets, and scattering heights
In the following, let X be any topological space.
The compact scattered subsets K of a X can be stratified, as follows. If K is non-empty, then we form the subset K0 of all isolated points of K. For each x ∈ K0, there is an open neighborhood Ux of x in X that intersects K at x only. Hence U0(K) ≝ ∪x ∈ K0 Ux is an open subset of X whose intersection with K is exactly K0. It follows that K–K0 = K–U0(K) is the intersection of a compact set with a closed set, hence is itself compact. We will actually need to remember that it is obtained as K minus some open set. (This will enable us to not make any unwarranted demands on X, such as Hausdorfness or well-filteredness.)
For an example, consider the compact subset {0} ∪ {1/2n | n ∈ N} of Q. In that case, K0 is the set of all points of the form 1/2n, and this is the simplest example of a compact (necessarily scattered) subset of Q whose points are not all isolated. The simplest shape that U0(K) may take here is ]0, ∞[ ∩ Q; we may also take the union of the sets ](1–ε)/2n, (1+ε)/2n[ ∩ Q, n ∈ N, for any fixed ε>0 such that ε<1.
If K–K0 is empty, we stop here. (That is not the case in the example above.) Otherwise, K’1 ≝ K–K0 is another non-empty compact subset of X (remember that is is compact because it can also be written as K–U0(K)), and therefore K–K0 must be scattered by Lemma B. We can now form its set K1 of isolated points, as above. (In the example, K–K0 = {0}, and now 0 is the only isolated point, so K1={0}.) Just as with K0, there is an open subset U1(K) ≝ ∪x ∈ K1 Ux of X such that K1 = K’1 ∩ U1(K), and then K’1–K1 = K’1–U1(K) = K–U0(K)–U1(K), so K’1–K1 is compact, and in fact equal to K minus some open set.
We repeat the process. If K’2 ≝ K–(K0∪K1) is empty, then we stop here. (That is indeed the case in our example.) Otherwise, K’2 is non-empty, compact, and scattered, and we form its set K2 of isolated points, and so on.
For a more complicated example, take the previous example {0} ∪ {1/2n | n ∈ N}, and add to it all the points in the various sequences {1/2n+1/2m+n+1 | m ∈ N}, converging to 1/2n, for each n ∈ N. Hence our newer example consists of 0, the points 0, 1/2n, and 1/2n+1/2m+n+1, for all m and n. In that case, K0 is the collection of points of the form 1/2n+1/2m+n+1, K1 is the collection of points of the form 1/2n, and K2={0}. You probably start to see the pattern.
We build K0, K1, K2, …, as above. This defines a process that builds pairwise disjoint sets Ki, and a decreasing sequence of non-empty compact scattered subsets K’n ≝ K–∪i=0n–1 Ki of X, which may stop at some stage n (meaning that K’n is empty) or not. Also, each set K’n is not just compact, but can be written as K minus some union of open sets ∪i=0n–1Ui(K).
If the process does not stop at any finite stage, then we obtain a decreasing sequence of non-empty compact scattered subsets K’n of X, n ∈ N. If X were well-filtered and T1, we could argue that their intersection K’ω ≝ K–∪i ∈ N Ki is also non-empty and compact. But we can show this even without assuming anything on X. Indeed, K’ω is the intersection of the sets K’n = K–∪i=0n–1 Ki, which are also equal to K–∪i=0n–1 Ui(K), so K’ω is also equal to K minus the union of the chain of open sets ∪i=0n–1 Ui(K), n ∈ N. If K’ω were empty, then K would be included in that directed union of open sets, hence it would be included in one of them, since K is compact; in other words, some K’n would be empty. As we have assumed this not to be the case, K’ω is not empty. Also, K’ω is equal to K minus the infinite union of open sets ∪i=0∞ Ui(K), and is therefore the intersection of K with a closed set, hence is itself compact. By Lemma B, K’ω is also scattered.
Since K’ω is non-empty (in case we have arrived up to this point), the process definitely does not end here. We form the subset Kω of isolated points of K’ω. Then K’ω+1 ≝ K’ω–Kω is compact and scattered, and equal to K minus some open set. If K’ω+1 is empty, then we stop here, otherwise we form the subset Kω+1 of isolated points of K’ω+1, and so on.
Formally, and recalling that X is well-filtered and T1, we define an ordinal-indexed, antitonic sequence of compact scattered sets K’α as follows: K’0 ≝ K, K’α+1 ≝ K’α–Kα where Kα is the set of isolated points in K’α (for any ordinal α), and K’β is the filtered intersection of the sets K’α, α<β, for every limit ordinal β. Also, for every ordinal α, K’α+1 is also equal to K’α–Uα(K) for some open subset Uα(K) of X, from which we deduce that for every ordinal α, K’α is equal to K minus the open set ∪γ<α Uγ(K), by induction on γ. We say that the sequence stops (giving meaning to the informal expression “we stop here” or “the process ends here” that we have used informally until now) at the first ordinal α such that K’α is empty.
That ordinal is called the scattering height of K. It must exist, and here is one possible argument. As long as the sequence has not stopped at any ordinal <α, all the sets Uγ(K) with γ<α are disjoint and non-empty, so the cardinality of ∪γ<α Uγ(K) is at least that of α. Since that cardinality cannot exceed the cardinality of K, the sequence must stop at or before any given cardinal number strictly larger than c, for example the cardinality of the powerset of K.
Since the scattering height of K exists, every point x of K lies in some set Kα(x). Moreover, those sets are pairwise disjoint. Hence every point x of K lies in some unique set Kα(x); α(x) is the scattering height of x in K.
First observation. The scattering height β of the compact set K, namely the least ordinal β such that K’β is empty, cannot be a limit ordinal.
Indeed, this is a variant of the argument we have already used in order to show that K’ω is non-empty, assuming that no K’n was empty, for any n<ω.
Explicitly, if β is a limit ordinal, and the sequence stops at β, then no K’α with α<β can be empty (because β is least). Since K’α = K – ∪γ<α Uγ(K), this means that K is included in none of the open sets ∪γ<α Uγ(K), for any α<β. If K’β = K – ∪γ<β Uγ(K) were empty, then K would be included in ∪γ<β Uγ(K), which is also the union of the chain of open sets ∪γ<αUγ(K), α<β, because β is a limit ordinal. (More explicitly, for every ordinal γ<β, there is an ordinal α such that γ<α and α<β, for example γ+1.) Since K is compact, K must then be included in ∪γ<α Uγ(K) for some α<β, and this is impossible.
Second observation. The last non-empty set of isolated points we see in the sequence, namely Kα where α+1 is the scattering height of the compact set K, is finite. I.e., there are only finitely many points of maximal scattering height in K.
Indeed, since K’α+1 is empty, K’α is equal to Kα, namely all the points of K’α are isolated. Therefore, for every point x in K’α, there is an open neighborhood Ux of x in X such that Ux ∩ Kα = {x}; the family of those sets Ux is an open cover of Kα, and since Kα is compact, it must contain a finite subcover… which, in turn, contains only finitely many points from Kα.
All of that is really an essential part of Costantini and Watson’s proof. This is somehow hidden, but those two observations do occur near the top of page 266 in [1], in the middle of an otherwise technical proof.
A topological game
We arrive at the main topic of this post.
What Costantini and Watson really do with those observations is something that is best described using a certain topological game, which I will define below. I believe it somehow clarifies what is happening, but I haven’t seen this in the literature. This rests on the following.
Lemma C. Let K be a non-empty compact scattered subset of a topological space X.
- The scattering height of K is a successor ordinal α+1, and Kα is finite.
- For every open subset U of X, for every ordinal γ, (K–U)‘γ is included in K’γ.
- For every open subset U of X, the scattering height of K–U is less than or equal to the scattering height, α+1, of K.
- If additionally, U contains Kα, then the scattering height of K–U is strictly less than that of K, hence is smaller than or equal to α.
Proof. Since K is non-empty, its scattering height is not 0. By the first observation above, it is not a limit ordinal, so it must be a successor ordinal α+1. By the second observation, Kα is a finite set. This proves item 1. Also, by definition of the scattering height, K’α=Kα.
Let us prove item 2. We claim that (K–U)‘γ is included in K’γ for every ordinal γ; by definition, (K–U)‘0=K–U, (K–U)‘γ+1 = (K–U)‘γ–(K–U)γ where (K–U)γ is the set of isolated points in (K–U)‘γ, and (K–U)‘β = ∩γ<β (K–U)‘γ for all limit ordinals β. This is by induction on γ. The only interesting case occurs when showing that (K–U)‘γ+1 is included in K’γ+1=K’γ–Kγ, where Kγ is the set of isolated points of K’γ, knowing by induction hypothesis that (K–U)‘γ is included in K’γ. Since (K–U)‘γ ⊆ K’γ, we have (K–U)‘γ+1 = (K–U)‘γ–(K–U)γ ⊆ K’γ, and it remains to show that (K–U)‘γ+1 does not intersect Kγ. In other words, we wish to show that (K–U)‘γ–(K–U)γ does not intersect Kγ, or equivalently, that (K–U)‘γ∩ Kγ is included in (K–U)γ.
Let x be a point of (K–U)‘γ ∩ Kγ. By definition of Kγ, x is isolated in K’γ, namely there is an open neighborhood U of x in X such that U ∩ K’γ = {x}. Since x ∈ (K–U)‘γ ⊆ K’γ, we also have U ∩ (K–U)‘γ = {x}. Therefore x is isolated in (K–U)‘γ, namely x is in (K–U)γ. This finishes the proof of item 2.
Item 3 follows from item 2 directly: we know that K’α+1 is empty, so by item 2, (K–U)‘α+1 is empty as well.
As for item 4, we note that for every ordinal γ, (K–U)‘γ is included in (K–U)‘0=K–U, since the sets (K–U)‘γ are smaller and smaller as γ increases. In particular, no (K–U)‘γ intersects U. Taking γ≝α, we obtain that (K–U)‘α is included in K’α, namely in Kα, and does not intersect U. Hence it is included in Kα–U. But that set is empty, so (K–U)‘α is empty.
It follows that the scattering height of K–U, namely the least ordinal γ such that (K–U)‘γ is empty, is less than or equal to α. It is therefore strictly smaller than the scattering height α+1 of K. ☐
Here is the game we will play. It involves two players, I and II. I will use a relatively informal, but traditional, way of describing it.
The game G(K). Given a topological space K, we start the game G(K) with C0 ≝ K. In round n+1 (n ∈ N), we have a set Cn (we have just said what C0 is), and player I wins immediately if Cn is empty. Otherwise,
- Player I picks an element xn+1 from Cn.
- Player II must respond with an open neighborhood Vn+1 of xn+1;
we let Cn+1 ≝ Cn–Vn+1 and we proceed to the next round.
A winning strategy of player I is one that allows it to eventually win (i.e., to force some Cn to be empty), whatever player II chooses as open neighborhoods at each round. At each round, the two players are allowed to consult the past history of the game, namely the whole sequence of points xi, of sets Ci, and of open sets Vi defined earlier, in order to make their decisions.
In the book, we have looked at various notions of strategies, where the players had access to only part of the history. We will find it important to look at so-called positional strategies for player I, namely those strategies where player I decides which finite set of elements to pick in round n as a function of Cn only, without looking at any of the rest of the history of the game. (Those are, in particular, stationary strategies.)
Note that, starting from a compact space K, all the sets Cn obtained in each round are compact, too, since they are obtained (by induction on n) by removing an open set from a compact set. This game looks a lot like the strong Choquet game: we have two players, one of them chooses some points, the other one chooses some open sets. But there are many differences: player I must choose xn+1 in Cn, namely outside the previous open sets chosen by player II; and player II chooses open sets that it wishes to exclude, instead of trying to force the play to happen inside the open set. Or, taking complements, player II chooses closed sets and player I chooses points inside that closed set. Also, the winning condition is different, although really it is equivalent to require that some Cn is empty or that their intersection is empty, if we start from a compact set K.
Proposition D. For every compact scattered subset K of a topological space X, player I has a winning strategy in the game G(K); additionally, it has a positional winning strategy.
Proof. First, a disclaimer: no, player I will most certainly not play the isolated points of Cn. Quite the opposite, in fact. In the second example we gave above, namely {0} ∪ {1/2n | n ∈ N} ∪ {1/2n+1/2m+n+1 | m ∈ N}, player I will first play just 0 in order to win; and 0 is essentially the farthest you can think of from an isolated point in that set: its scattering height is 2, the largest possible value achievable in that example. Whatever open neighborhood V1 of 0 player II proposes, removing V1 from {0} ∪ {1/2n | n ∈ N} ∪ {1/2n+1/2m+n+1 | m ∈ N} will only leave finitely many elements. Then player I will be able to play them, one after another, in the subsequent rounds, and win the game. (Oops! Update, May 31st. No, whatever open neighborhood V1 of 0 player II plays, removing V1 will remove 0 as well as all but finitely many of the points 1/2n, n ∈ N, but each point of the form 1/2n can come with infinitely many accompanying points 1/2n+1/2m+n+1, m ∈ N, as well. Let us imagine that removing V1 leaves at least one point of the form 1/2n in place. In that case, there are only finitely many of them, and player I will play them, round after round. Whenever player I plays such a point of the form 1/2n, namely any point of scattering height 1, player II will be forced to play an open neighborhood around it, removing all the points 1/2n+1/2m+n+1, m ∈ N except finitely many—for that fixed n. After finitely many rounds, all the points 1/2n of scattering height 1 will have been eliminated, and we will finally find ourselves in the situation where only finitely many elements 1/2m+n+1, of scattering height 0, will remain. Player I will then simply play them one after another in the final rounds. Funnily, that was the exact situation I initially wanted to describe, but I got mixed up. Thanks to Xiaodong Jia for spotting this!)
Let us now prove Proposition D. We assume that there is a compact scattered subset K of X such that player I has no positional winning strategy in G(K). Since the class of ordinals is well-founded, there must be one of least possible scattering height. By Lemma C, item 1, this scattering height is a successor ordinal α+1, and Kα is finite. Among all the compact scattered subset K of X such that player I has no positional winning strategy in G(K) and with scattering height equal to α+1, we pick one such that the cardinality of Kα is least. To sum up, we pick K so that player I has no positional winning strategy in G(K), and such that the pair (scattering height α+1 of K, cardinality of Kα) is minimal in the lexicographic ordering.
Kα is non-empty (otherwise the scattering height of K would be smaller than or equal to α), so let us pick a point x from Kα. We let player I start the game by playing x1≝x (first round). Whatever open neighborhood V1 of x1 player II plays (and taking U≝V1), K–U has scattering height at most α+1 by Lemma C, item 3. If K–U is non-empty, then K–U has scattering height exactly α+1, and by Lemma C, item 2, (K–U)‘α is included in K’α; it is also included in K–U, does not contain x, and is equal to (K–U)α (since, by definition of the scattering height, (K–U)’α+1 = (K–U)‘α–(K–U)α is empty), so the cardinality of (K–U)α is strictly smaller than the cardinality of Kα. If K–U is empty, then by Lemma C, item 4, the scattering height of K–U is strictly smaller than the scattering height of K. In any case, the pair (scattering height α+1 of K–U, cardinality of (K–U)α) is lexicographically strictly smaller than the pair (scattering height α+1 of K, cardinality of Kα).
By our minimality assumption on K, player I must have a winning positional strategy in the game G(K–U), and we let player I continue the game G(K) by playing as in G(K–U). More precisely, in round 2 of the game G(K), player I will play as if in round 1 of G(K–U), using its winning positional strategy. In round 3 of G(K), it will play as if round 2 of G(K–U), and so on. This way of tacking a play in G(K–U) onto a first round by the two players is made possible by the fact that the strategy player I uses in G(K–U) is positional; therefore it cannot see that the history has been made one round longer under the rug.
Having done this, we reach a contradiction: the strategy we have just described on G(K) is positional, and allows player I to win in G(K). However, we had assumed there no positional strategy was winning for player I in G(K). ☐
Characterizing compact scattered subspaces, take 1
One may wonder whether the converse of Proposition D holds. Namely, let us imagine that player I has a winning strategy in G(K); is K compact and scattered?
One half of that question is easy.
Lemma E. Let X be a topological space, and K be a subset of X. If player I has a winning strategy in G(K), then K is compact.
Proof. If K is not compact, we claim that player II has a strategy that forces the game to go on for infinitely long. In particular, player I has no winning strategy, positional or not.
Indeed, if K is not compact, then it has an open cover (Ui)i ∈ I with no finite subcover. At each round n, if player I picks xn+1, then player II only needs to pick some Uin+1 containing xn+1. With those choices, there is no chance that any set Cn will be empty, because Cn is K minus Ui1 ∪ … ∪ Uin, and if Cn where empty, then the sets Ui1, …, Uin would form a finite subcover of K of (Ui)i ∈ I. ☐
Game trees
The other half will require X to be T2. But, more importantly, it will require us to examine the game tree T(K,σ) of the game G(K), given that player I plays according to a given strategy σ. This is defined much like the game trees we used in the book in order to reason on the strong Choquet game (Section 7.6.2). Informally, we build the game tree as follows.
- First, there is a root, which we place at the top, and the root is labeled with K.
- In general, the vertices at depth n are labeled with the possible current states Cn of the game at round n. For each vertex v at depth n, we build its successors (which we draw right below v, and which are all at depth n+1, by definition) as follows. Let us imagine that v is labeled with Cn. If Cn is empty, then v has no successor: v is a leaf of the tree T(K,σ). Otherwise, we use player I’s strategy σ to compute a point xn+1 in Cn. For every possible open neighborhood Vn+1 of xn+1 that player II may play next, we form a new successor v’ of v, and we label it with Cn+1 ≝ Cn–Vn+1.
A bit more formally (and as in the book), we define the vertices of T(K,σ) as being the finite histories C0, x1, V1, C1, …, xn, Vn, Cn (n≥0), where each point xi is computed using the strategy σ from the current history C0, x1, V1, C1, …, xi–1, Vi–1, Ci–1 (1≤i≤n), where each Vi is an open neighborhood of xi, and where finally C0=K and Ci ≝ Ci–1–Vi for every i, 1≤i≤n. The label of such a vertex C0, x1, V1, C1, …, xn, Vn, Cn is simply Cn, and its successors are all the finite histories of the form C0, x1, V1, C1, …, xn, Vn, Cn, xn+1, Vn+1, Cn+1 (with an additional triple xn+1, Vn+1, Cn+1 tacked to its end, obeying the obvious constraints).
The game tree T(K,σ) organizes all possible plays of the game G(K) where player I plays according to strategy σ, in a sense that will hopefully be clear. Given any strategy that player II relies on in order to pick Vn+1 at round n+1, for every n, the successive points xi and sets Vi, Ci will form a branch of the tree, namely a path starting from the root, going from one vertex to a successor. Conversely, any branch of the tree can be obtained by (at least) one player II strategy.
Additionally, if σ is a winning strategy for player I, then all the branches of T(K,σ) are finite. Whatever branch we pick, it can be obtained by letting player II play according to some strategy, but since σ is winning for player I, some Cn along this branch will be empty; and that means that the vertex that it labels is a leaf.
One should be aware that, although all the branches of T(K,σ) are finite, there may fail to be a uniform upper bound on the lengths of those branches. For example, there may be a branch of length 1, one of length 2, one of length 3, and so on, with no upper bound on the lengths of those branches.
Well-founded induction
A tree whose branches are all finite is called a well-founded tree, and a nice reasoning principle that is available on such trees is the principle of well-founded induction:
- Given a property P of vertices, in order to show that P holds of every vertex v (in short, P(v)), it suffices to show that, for every vertex v, P(v) holds under the assumption (called the induction hypothesis) that P(v’) already holds for every successor v’ of v.
Logically, well-founded induction is the following formula:
(∀vertex v, (∀v’ successor of v, P(v’)) ⇒ P(v)) ⇒ (∀vertex v, P(v)),
which may look intimidating, but look: that is really similar to well-founded induction on the natural numbers, which is the following formula:
(∀n ∈ N, (∀m<n, P(m)) ⇒ P(n)) ⇒ (∀n ∈ N, P(n)),
and which means that, in order to prove that a property P holds of every natural number n, it suffices to prove P(n) under the assumption (induction hypothesis) that P(m) already holds for every m<n. (Oh, if you’re not that much into logic, ∀ is “for all”, and ⇒ is “implies”. I will also use ∃ for “there exists”.)
Let me justify why well-founded induction holds on any tree with no infinite branch. (This is a standard exercise in logic, so please forgive me if you find this boring.) What we will show is that, if well-founded induction fails, then the tree must contain an infinite branch. The negation of well-founded induction is the following formula, once we push negations inwards, using the rules not-∀=∃-not, not(A ⇒ B)=(A and not B), and so on:
(∀vertex v, (∀v’ successor of v, P(v’)) ⇒ P(v)) and (∃vertex v, not P(v)).
It will be more practical to exchange the two sides of the conjunction (‘and’), so the negation of well-founded induction can be written as:
(∃vertex v, not P(v)) and (∀vertex v, (∀v’ successor of v, P(v’)) ⇒ P(v)).
Since A ⇒ B is equivalent to not-B ⇒ not-A, we can rewrite the latter form of the negation of well-founded induction as:
(∃vertex v, not P(v)) and (∀vertex v, (not P(v)) ⇒ (∃v’ successor of v such that not P(v’))).
Now, from the first conjunct (∃vertex v, not P(v)), we obtain that there is a vertex v0 such that not P(v0). Using the second conjunct (∀vertex v, (not P(v)) ⇒ (∃v’ successor of v such that not P(v’))) on v0, we obtain that there is a successor v1 of v0 such that not P(v1). Using the second conjunct once again, this time on v1, there is a successor v2 of v1 such that not P(v2). And so on, and so forth: we obtain an infinite branch v0, v1, v2, … in the tree, as promised.
Logicians would argue that the ‘and so on and so forth’ hides an appeal to the so-called axiom of dependent choices, which is a weak form of the axiom of choice. But we are using the axiom of choice all the time in topology anyway. (Some logicians would also argue that the above argument is not constructive, too, and that is inherent.) Oh, before we come back to our main subject, the fact that all branches are infinite does not just imply the principle of well-founded induction: the two notions are equivalent (in the reverse direction, just prove that all branches rooted at v are finite by well-founded induction on the vertex v). In fact, the principle of well-founded induction is the standard characterization of well-founded trees in constructive mathematics.
Characterizing compact scattered subspaces, take 2
Let us return to our point. If player I has a winning strategy σ in the game G(K), then all the branches in the game tree T(K,σ) are finite, hence we can use well-founded induction on the vertices of T(K,σ) and show the following.
Proposition F. Let X be a T2 space, and K be a subset of X. If player I has a winning strategy σ in the game G(K), then K is scattered.
Proof. We consider the following property P: for any vertex v of T(K,σ), labeled with some set Cn, P(v) holds if and only if Cn is scattered. We will prove that P(v) holds for every vertex v by well-founded induction. This means that we have the following induction hypothesis at our disposal: for every successor v’ of v in T(K,σ), v’ is labeled by a scattered set.
In order to show that Cn is scattered, we consider any dense-in-itself subset D of Cn. We wish to show that D is empty. If v is a leaf (namely, if Cn is empty), then D is empty, trivially. Otherwise, let xn+1 be the point of Cn played by player I using σ. (Formally, the vertex v is a history C0, x1, V1, C1, …, xn, Vn, Cn, and we apply σ to that history in order to obtain xn+1.) We proceed with the following steps.
- Let us imagine that D contains a point y distinct from xn+1. Since X is T2, we can find two disjoint open neighborhoods U and V of xn+1 and y respectively. We let player II play U for Vn+1, and this gives us a successor v’ of v in T(K,σ): formally, v’ is the history C0, x1, V1, C1, …, xn, Vn, Cn, xn+1, U, Cn+1, where Cn+1 ≝ Cn–U.
By induction hypothesis, Cn+1 is scattered. Since D is dense-in-itself and V is open, the intersection D ∩ V is also dense-in-itself (exercise!). But D ∩ V is included in Cn+1, since D is included in Cn and V is disjoint from U. Since Cn+1 is scattered, D ∩ V must be empty… but that is impossible, since y is in D ∩ V. - Hence D contains no point distinct from xn+1. If D={xn+1}, then D consists of a unique, isolated point. This is impossible, since D is dense-in-itself. Therefore D is empty, as promised.
What have we got now? We have proved that P(v) holds for every vertex v of the game tree T(K,σ). In other words, all the vertices of T(K,σ) are labeled with scattered sets. This is in particular true for the root of the tree, which is labeled by K. Hence K is scattered. ☐
We sum up all of our findings in the following theorem.
Theorem. Let X be a topological space, and K be a subset of X. Consider the following claims:
- K is compact;
- K is scattered;
- player I has a positional winning strategy in the game G(K);
- player I has a winning strategy in the game G(K).
Then (1 and 2) ⇒ 3 ⇒ 4 ⇒ 1. If X is T2, then we also have 4 ⇒ 2.
In particular, if X is T2, then K is compact scattered if and only if player I has a winning strategy in G(K), and that strategy can be taken to be positional.
Let me say again what G(K) is, so that you don’t have to grope for it in this page:
- C0 ≝ K; at each round n, player I wins if Cn is empty, otherwise:
- Player I picks an element xn+1 from Cn.
- Player II responds with an open neighborhood Vn+1 of xn+1;
let Cn+1 ≝ Cn–Vn+1 and proceed to the next round.
Next time, we will see how this can be used to show that Q is not consonant, following Costantini and Watson [1]. This relies on a clever, and rather technical construction in which the above theorem plays a crucial rôle (although that argument is totally hidden), but which also requires some entirely unrelated trickery with bases of clopen sets, a mysterious transition system, and limit superiors in the lattice of closed subsets.
- Camillo Costantini and Stephen Watson, On the dissonance of some metrizable spaces, Topology and its Applications 84 (1998), 259—268.
— Jean Goubault-Larrecq (May 20th, 2022)