THE UTILITY OF THE UNCOUNTABLE

JUSTIN TATCH MOORE

In my lecture at the 2011 Congress on Logic, Methodology, and the Philosophy of Science in Nancy, France, I spoke on an additional axiom of set theory — the Proper Forcing Axiom — which has proved very successful in settling combinatorial problems concerning uncountable sets. Since I have already written a exposition on this subject [43], I have decided to address a broader question in this article: why study uncountability?

In some circles within logic, there has been an ongoing campaign to stress the importance of countability in mathematics — and to marginalize the uncountable. While much of mathematics does concern objects which can be codified as hereditarily countable sets, this often does not reflect how mathematics is discovered or developed. More significantly, there are technical difficulties which can arise in mathematics — often quite unexpectedly — which are fundamentally uncountable in their character. The purpose of this article is survey some instances where uncountability has been useful in the discovery process, essential to the solution of a problem, or at least has offered a fruitful perspective. We will also will examine settings in which restricting attention to countable objects artificially limits the perspective and gives an incomplete picture of the mathematical phenomenon under consideration.

In this article, we will take countable mathematics to mean the study of that which can be encoded in the hereditarily countable sets — the domain of discourse of second order arithmetic. For instance a complete metric space can be encoded as the completion of a countable metric space. Even Borel or suitably definable subsets of such a space have a countable description and as such lie within the scope of “countable mathematics.” Nonseparable spaces or nonmeasurable subsets of ℝ are typical examples of objects which are essentially uncountable in their nature.

1991 Mathematics Subject Classification. 03-02.

Key words and phrases. uncountable.

The research of the author was supported in part by NSF grant DMS–0757507.

None of the mathematics in this article is my own. I have generally tried to include references to the original works when it is reasonable to do so and otherwise provide a standard reference where the material can be found.

1. The theory of algebraically closed fields

One of the great ironies of logic is surely that the theory of algebraically closed fields of characteristic 0 is complete while Peano’s Axioms for ℕ are not only incomplete but cannot be completed in any intelligible way. Ostensibly, ACF_{0} attempts to achieve more generality through abstraction than just to axiomatize the theory of the complex numbers. On the other hand, PA was formulated with the intention of axiomatizing a single model, namely (ℕ, +, ·, 0, 1, <).

Equally remarkable is how natural it is to employ uncountability to prove the completeness of ACF_{0} — a statement which itself is purely arithmetical in nature. To illustrate this, I will sketch the argument presented in [35]. To be clear, this is not the original argument of Robinson [48], but it is an elegant illustration of how uncountability can play a role in proving an arithmetical statement.

The following are the two main ingredients:

Vaught’s Test. If T is a consistent theory in a countable language, T has no finite models, and any two models of T of cardinality ℵ_{1} are isomorphic, then T is complete.

Transcendence Degree. (see, e.g., [22]) If two algebraically closed fields have the same characteristic and transcendence degree, then they are isomorphic.

Vaught’s Test has a very short proof using the Lowenheim-Skolem Theorem: if T does not decide ϕ, then there are consistent extensions T_{0} and T_{1} of T which include ϕ and ¬ϕ respectively and which have infinite models. By the Lowenheim-Skolem Theorem, T_{0} and T_{1} have models of cardinality ℵ_{1}. Such models are then isomorphic, contradicting that one satisfies ϕ and the other satisfies ¬ϕ. Notice that the form of the Lowenheim-Skolem Theorem needed here is fundamentally uncountable in character.

The proof that ACF_{0} is complete can now be finished as follows. By Vaught’s Test, it is sufficient to show that any two algebraically closed fields of characteristic 0 and of cardinality ℵ_{1} are isomorphic. This is true by observing that the transcendence degree of an uncountable algebraically closed field is equal to its cardinality. As with the Lowenheim-Skolem theorem, we fundamentally need here the notion of not only infinite but of uncountable transcendence degree.

2. Semigroup dynamics and Ramsey theory

Recall the following two theorems concerning partitions of ℕ:

van der Waerden’s Theorem. [61] If ℕ = ⋃_{i<d} K_{i}, then there is an i < d such that K_{i} contains arbitrarily long arithmetic progressions.

Hindman’s Theorem. [20] If ℕ = ⋃_{i<d} K_{i}, then there is an i < d and an infinite H ⊆ ℕ such that all finite sums of distinct elements of H are in K_{i}.

Both of these theorems were first proved by elementary means. Still, these elementary proofs are quite complex and the modern perspective is that the standard proofs of these statements go by way of semi-group dynamics. The basic idea is as follows. We begin with the discrete semigroup (ℕ, +) and then form the Čech-Stone compactification βℕ. The operation + extends to a semigroup operation on βℕ. This operation is moreover continuous in the left argument: p ↦ p+q is continuous for each q. The compactness of βℕ allows for the construction of algebraic objects which have powerful combinatorial consequence for ℕ.

For instance Glazer observed that the following lemma of Ellis implies that βℕ contains an idempotent (other than 0).

Ellis’s Lemma. [11] If S is a left topological compact semigroup, then S contains an idempotent.

Galvin had already observed that such idempotents can be used to prove Hindman’s Theorem. If p + p = p, then any element K of p contains a set H such that all finite distinct sums from H lie in K; the set H can be constructed by an easy recursive procedure (see [21] or [58]). Gowers later extended this argument in [15] to prove a stronger combinatorial statement which he then used to draw geometric conclusions about the Banach space c_{0}. Unlike Hindman’s Theorem, there is currently no known elementary proof of Gowers’s result.

The reader may also find Harrington’s proof of the Halpern-Läuchli theorem interesting (see [60]). This proof utilizes both the Erdős-Rado theorem (i.e. the partition relation ℶ_{d}^{+} → (ℵ_{1})_{ω}^{d+1}) and the method of forcing. While the other proofs of the Halpern-Läuchli theorem are more elementary, this proof offers those comfortable with forcing a more intuitive proof.

3. Serre’s Conjecture

Next we will turn to an example from group theory. The point here is not only to mention a very remarkable result, but to give an example of how “real mathematicians” are not satisfied with limiting themselves to second order arithmetic, even when this might seem to be a completely natural thing to do.

A profinite group is an inverse limit of a directed system of finite groups. These can be equivalently characterized as being those compact topological groups which are totally disconnected — they have no nontrivial connected subsets. Notice that, when separable, such groups have a countable description — the inverse system of groups which defines them is countable. Serre made the following conjecture after proving that it is true for pro-p groups (this also was asked by Mel’nikov in 7.37 of [40]).

Conjecture. If G is a profinite group which is topologically finitely generated and H is a finite index subgroup of G, then H is open.

So in particular, the subgroup structure of G already determines the topology of G; in any profinite group, the open subgroups form a neighborhood of the identity. If the requirement that G be topologically finitely generated is dropped, then it is easy to construct counterexamples.

Example. Let G = 2^{ℕ}, equipped with coordinatewise addition modulo 2. Let U be an ultrafilter on ℕ and let H be the collection of all g in G such that {i ∈ ℕ : g(i) = 0} is in U. It is easily verified that H is a subgroup of index 2 and that H is not open unless U is a principal ultrafilter.

On the other hand, it is not difficult to show using Pettis’s Theorem (see [27, 9.9]) that if H is a subgroup of a Polish group G and H has finite index, then either H is open or else H fails to have the Property of Baire (a set has the Baire Property if it differs from an open set by a set of first category). In particular, Serre’s conjecture is true even without the assumption that G is topologically finitely generated if we require that H is Borel or even analytic.

Thus Serre’s conjecture becomes equivalent to asserting that H has additional regularity properties which it obtains just by virtue of the algebraic structure. While the analysis using Pettis’s Theorem is presumably well known (and not at all difficult), a proof of Serre’s Conjecture was only given very recently by Nikolov and Segal [45]. The proof itself is a tour de force in the theory of finite groups and brings closure to a long line of research on the subject [18], [39], [50], [51]. It should be remarked that this is related to another more general pursuit: understanding when algebraic constraints on functions imply topological constraints such as continuity. The study of automatic continuity dates back to Cauchy; see [49] for a recent survey of work in this area.

4. The additivity of strong homology

If one wishes to have a theory of homology which extends to general topological spaces, this becomes a rather subtle matter. One such theory which was developed was that of strong homology. While the development is beyond the scope of this paper (the interested reader is referred to [34] for a complete treatment) we will discuss an example of how a computation in strong homology reduces to a problem in uncountable combinatorics.

In [41], Milnor proposed the following natural axiom known as additivity that a homology theory might satisfy. It asserts for every family X_{i} (i ∈ I) of topological spaces, the natural inclusions of X_{i} into ∐_{i∈I} X_{i} induce an isomorphism of groups

⨁_{i∈I} H_{p}(X_{i}) ≃ H_{p}(∐_{i∈I} X_{i}).

Now consider the following example due to Mardešić and Prasolov.

Example. [33] For each d > 0, set z_{n} = (2^{−n}, 0, 0, …, 0) and define

X_{d} = ⋃_{n=0}^{∞}{x ∈ ℝ^{d+1} : |x − z_{n}| = 2^{−n}}.

Thus X_{d} is a sequence of nested d dimensional spheres which converge to the origin. The space X_{d} is compact and its homology groups coincide with the Steenrod homology groups:

H_{p}(X_{d}) = \begin{cases}ℤ^{ℕ} & if p = d \\ ℤ & if p = 0 \\ 0 & otherwise \end{cases}

The additivity axiom would imply that

H_{p}(X_{d} × ℕ) = ⨁_{n=0}^{∞} H_{p}(X_{d}).

Mardešić and Prasolov have shown, however, that if strong homology is used then

H_{i}(X_{d} × ℕ) = \begin{cases}⨁_{i=0}^{∞} ℤ^{ℕ} & if p = d \\ lim^{d−p} A & if 0 < p < k \\ lim^{d} A ⊕ (⨁_{i=0}^{∞} ℤ) & if p = 0 \\ 0 & if p > d \end{cases}

Here A is the inverse system which is defined as follows. Set D_{f} = {(i, j) ∈ ℕ^{2} : j < f(i)} and define

A_{f} = ⨁_{(i,j)∈D_{f}} ℤ.

If f ≤ g are in ℕ^{ℕ}, then D_{f} ⊆ D_{g} and we have a natural restriction map ϱ_{g,f} : A_{g} → A_{f}. The family A_{f} (f ∈ ℕ^{ℕ}), equipped with these restrictions, becomes an inverse system of abelian groups.

The derived limits lim^{k} A are quite complicated and only understood in the single case mentioned below. They are in all cases apparently sensitive to set-theoretic assumptions. In particular, Mardešić and Prasolov have shown that if the Continuum Hypothesis is true, then lim^{1} A ≠ 0 and in particular that strong homology is not additive. Dow, Simon, and Vaughan have shown on the other hand, that the Proper Forcing Axiom implies that lim^{1} A = 0.

Combinatorially, lim^{1} A = 0 is equivalent to the following assertion [33]: if ϕ_{f} (f ∈ ℕ^{ℕ}) is a coherent family of functions with dom(ϕ_{f}) = D_{f}, then there is a single Φ : ℕ^{2} → ℕ such that, for each f ∈ ℕ^{ℕ}, ϕ_{f} is, modulo a finite error, equal to the restriction Φ ↾ D_{f}. Here ϕ_{f} (f ∈ ℕ^{ℕ}) is coherent if for each f, g ∈ ℕ^{ℕ} the set

{(i, j) ∈ D_{f} ∩ D_{g} : ϕ_{f}(i, j) ≠ ϕ_{g}(i, j)}

is finite.

So far, only lim^{1} A = 0 has been examined in the set-theoretic literature. It appears to be a highly non-trivial problem to determine whether these groups can all be trivial in a single model of set theory.

5. Gaps and automorphisms of P(ℕ)/fin

The problem of whether lim^{1} A = 0 discussed in the previous section is a special instance of a more general set-theoretic problem which frequently arises in applications of set theory: what types of gaps are present in quotients of P(ℕ) and under what circumstances can they arise? What is interesting is that when questions arising outside of set theory are boiled down to a question concerning gaps, the gaps involved rarely if ever come with regularity restrictions. That is, these naturally arising questions are of an uncountable nature. Moreover, the development of the general theory of gaps has in turn guided a parallel theory of definable gaps.

Before proceeding, we will review some terminology. A gap in P(ℕ)/fin is a pair A, B of subsets of P(ℕ) such that:

• A ∩ B is finite whenever A ∈ A, B ∈ B, but

• there is no single C ⊆ ℕ satisfying C ∩ B is finite for all B ∈ B

and A \ C is finite for all A ∈ A. Gaps in P(ℕ)/fin where first studied by Hausdorff in [19]. Todorcevic was the first to emphasize the Ramsey-theoretic nature of gaps and also stress their important role in applications. In [54], he formulated a powerful graph-theoretic dichotomy known as the Open Coloring Axiom in order to study its influence on gaps:

OCA: If G is a graph whose vertex set is a separable metric space and whose edge set is topologically open, then either G has a countable vertex coloring or else contains an uncountable clique.

(It is interesting to note that the formulation of OCA can be traced to problem of studying the isomorphism types of subsets of ℝ, something seemingly unrelated to gaps. Specifically, the definition of OCA was derived from similar statements considered by Abraham, Rubin, and Shelah in [1] which in turn were derived from a result of Baumgartner [4].) Further information on gaps can be found in [55].

Next we will turn to a problem whose solution involved the analysis of gaps.

Problem. If ϕ is an automorphism of the Boolean algebra P(ℕ)/fin, is there a function f : ℕ → ℕ which induces ϕ?

That is, is there an f such that ϕ([A]) = [B] if and only if the image of A under f and B differ by a finite set? If this is the case, we say that ϕ is a trivial automorphism. It is interesting to note here that while an automorphism of P(ℕ)/fin is not a priori an object of second order arithmetic, a trivial automorphism is.

It turns out that the answer to the above problem is independent of ZFC. If one assumes the Continuum Hypothesis, then P(ℕ)/fin is ℵ_{1}-saturated and there are 2^{2^{ℵ_{0}}} automorphisms of P(ℕ)/fin (and so in particular not all are induced by a map from ℕ to ℕ). On the other hand Shelah has shown that it is consistent with ZFC that all automorphisms of P(ℕ)/fin are trivial [52]. Later Shelah and Steprāns showed that PFA implies all automorphisms of P(ℕ)/fin are trivial [53]. Their proof was further simplified and carried out under the weaker assumption of OCA and MA by Veličković [63]. The reader is referred to [25], [24], and [12] for subsequent work on this subject. More recently Philips-Weaver [47] and Farah [13] have adapted this method to solve a longstanding problem in the theory of operator algebras originating in [5].

What is also interesting about Shelah’s solution of the automorphism problem was that it was later discovered that there is an effective analog of Shelah’s theorem: any automorphism of P(ℕ)/fin which has a Baire measurable lifting is trivial [62]. It is important to note, however, that this effective theorem — which could be regarded as a result in second order number theory — was discovered by analyzing the combinatorics of Shelah’s independence proof and the Shelah-Steprān’s proof from PFA. Moreover, while proofs which utilize PFA often yield effective counterparts as corollaries, the converse is not true.

There are, in fact, other instances where solutions to effective versions of problems have been given while the original problem remains open and apparently intractable. The following are two examples.

Problem. (see [16]) Suppose that C is a compact convex subset of a locally convex topological vector space. If every closed subset of C is a G_{δ} set, is C necessarily metrizable?

Problem. [3] (see [42]) If G is a separable Fréchet group, must G be metrizable?

In the case of the first problem, Todorcevic has shown that the answer is positive if C is homeomorphic to a compact subset of the the Baire class one functions on a Polish space [56] (this is a natural regularity assumption on C in this context). In the case of the second problem, it is not difficult to show that the problem reduces to the case in which G is countable. Todorcevic and Uzcágeti have shown that if G is a countable Fréchet group and the topology on G is analytic as a subset of the compact metric space P(G) ≡ 2^{G}, then G is metrizable [59]. Consistent counterexamples to both problems are known (see [32] and [42] respectively).

6. The Separable Quotient Problem

Next we turn to another instance in which restricting attention to objects of countable character does not give the full picture. One of the most basic questions about Banach spaces concerns the existence of Schauder bases in these spaces. The following question is often attributed to Banach himself, although it was only later that it was made explicit in print.

Problem. (see [46]) Does every infinite dimensional Banach space have an infinite dimensional quotient with a basis?

Nothing about this problem suggests that the problem concerns “uncountability” — which in this context should be interpreted as nonseparability. Still, Johnson and Rosenthal were able to prove that this problem has a positive answer within the class of separable Banach spaces [23]. This reduced Banach’s original problem to the following form, which is more prevalent in the literature today.

Separable Quotient Problem. Does every infinite dimensional Banach space have an infinite dimensional separable quotient?

The reader is referred to [44] for a survey of this problem. I will note two more recent results in the positive direction.

Theorem. [57] Assume PFA. Every Banach space of density ℵ_{1} admits a nonseparable quotient with a basis.

Theorem. [2] If X is an infinite dimensional Banach space, then X^{∗} has an infinite dimensional separable quotient.

7. The determinacy of Gale-Stewart games

One of the most profound examples of how large sets can influence countable combinatorics is surely the determinacy of Gale-Stewart games. Recall that in a Gale-Stewart game, two players alternately play elements x_{n} of some set X, one element for each natural number. Both players have perfect information. Player I wins if the outcome ⟨x_{n} : n < ∞⟩ is in some pre-specified set Γ; Player II wins otherwise. Such a game is determined if one of the two players has a winning strategy. The simplest theorem concerning the determinacy of Gale-Stewart games was already known to Gale and Stewart.

Closed Determinacy. If Γ ⊆ X^{ℕ} is closed, then the Gale-Stewart game specified by Γ is determined.

The proof is quite simple: Player I always plays to maintain that Player II does not have a winning strategy. Either this is impossible and Player II has a winning strategy from the beginning of the game or else Player I has arranged that at no point in the game did Player II have a winning strategy. The key point is that, in a closed game, if Player II wins a play of the game, she has already won at a finite stage of the game (i.e. all further plays are irrelevant).

The determinacy of Gale-Stewart games is of interest primarily because regularity properties of subsets of ℝ and other Polish spaces can be recast in terms of the existence of winning strategies in games which are associated to these sets (see, e.g., [27, §21]). In general, Gale-Stewart games need not be determined; the Axiom of Choice can readily be used to construct games which are not determined. On the other hand, sets Γ ⊆ ℕ^{ℕ} which are in some sense regular do tend to specify determined games.

Borel Determinacy. [37] If Γ ⊆ ℕ^{ℕ} is Borel, then Γ is determined.

What is remarkable is that all known proofs of determinacy ultimately rely on the determinacy of closed games: one reduces the determinacy of Γ ⊆ ℕ^{ℕ} to the determinacy of some equivalent closed game Γ^{∗} ⊆ X^{ℕ}. The set X underlying this “unraveled” game is typically much larger than ℕ. For instance, H. Friedman has shown that Borel Determinacy is not provable in ZFC without the powerset axiom [14]. In fact any proof of Borel determinacy must use, in an essential way, ℵ_{1} iterations of the power set operation.

Earlier, Martin had proved the determinacy of analytic games from the existence of a measurable cardinal [36]. Harrington proved that the determinacy of analytic games is equivalent to the existence of x^{♯} for each x ⊆ ℕ, thus demonstrating the necessity of large cardinals in Martin’s proof [17]. The determinacy of projective games was proved by Martin and Steel from the existence of infinitely many Woodin cardinals [38] — an assumption which was shown by Woodin to be essentially optimal.

Notice that the determinacy of projective games is formalizable in second order arithmetic and concerns the properties of the hereditarily countable sets. Even the proof of the determinacy of Borel games, however, already makes essential use of transfinite iterates of the powerset operation. In the case of analytic determinacy, the proof moreover requires the use of large cardinals. The reader is referred to [26] for further reading on determinacy and large cardinals, as well as an extensive bibliography on the subject. Some further information on the history of determinacy can be found in [28].

8. Large cardinals, braids, and left self distributivity

Next we turn to an example where very large sets have proved useful both in establishing facts about finite algebraic structures and in improving the efficiency of algorithms for comparing braids. A binary system (S, ∗) is called a LD system if it satisfies the left self distributive law:

a ∗ (b ∗ c) = (a ∗ b) ∗ (a ∗ c)

Left self distributivity showed up independently in the literature in two very different contexts. On one hand, it came naturally out of attempts by Brieskorn, Joyce, Kauffman, and their students to develop invariants for studying the braid group [8]. Roughly speaking, one colors the strands at the top of a braid using colors of a binary system (S, ∗). The operation dictates how the strands change the colors of other strands in a diagram representing the braid. In order for this procedure to yield an invariant for braids, (S, ∗) must be an LD system. The reader is referred to [8] for more details. Suffice it to say that this use of an LD system makes it desirable to understand free LD systems — those not satisfying any laws other than those which follow logically from the LD law.

In a separate branch of mathematics, LD systems were being studied for a completely different purpose. It was part of the folklore in set theory that the family E_{λ} of non-identity elementary embeddings from V_{λ} into itself formed an algebraic structure which moreover satisfied the left self distributive law [8]. Such embeddings are known as rankto-rank embeddings. Postulating the existence of a λ for which there is a non-identity elementary embedding from V_{λ} to V_{λ} is an example of a large cardinal axiom; in fact it is among the strongest of the large cardinal axioms (see [26]). In particular, the existence of rank-to-rank embeddings cannot be proved within ZFC.

In [30], Laver proved that if j is a rank-to-rank embedding, then the algebra (A, ∗) generated by j is free. This was in sharp contrast to the LD systems — such as a group equipped with conjugation — which had been employed previously in the study of braids. Then in [29], Laver used the existence of a rank-to-rank embedding to prove that the word problem in LD systems is decidable. This in turn led to efficient new algorithms for comparing braids [7] [31]. Only later was Dehornoy able to remove the use of large cardinals from solution to the decision problem for LD systems [6].

Still, large cardinals played a remarkable and unique role in this development. Furthermore, there are questions concerning certain finite LD systems which so far have only been settled using large cardinal assumptions. An LD system is cyclic if it has a single generator a and there is a p > 1 such that the left associated power

a_{[p]} = ((a ∗ a) … ∗ a) ∗ a

equals a. Laver has shown that any cyclic LD system has 2^{n} elements for some n and is unique up to isomorphism. If for a given n ∈ ℕ we define ∗ on {1, …, 2^{n}} by

a ∗ 1 = \begin{cases}a + 1 & if a < 2^{n} \\ 1 & if a = 2^{n} \end{cases}

then there is a unique extension of ∗ a binary operation which is left self distributive. This LD system is the n^{th} Laver table A_{n}. The following summarizes the important properties of the Laver tables:

• a ∗ p = (a + 1)_{p} if a < 2^{n} and 2^{n} ∗ a = a.

• if m < n, then the function π : A_{n} → A_{m} defined by π(a) = b if a ≡ b mod 2^{m} is a surjective homomorphism.

• if a ∈ A_{n}, then there is a p ≤ n such that a ∗ b = a ∗ b′ if b ≡ b′

mod 2^{p} and a ∗ b < a ∗ (b + 1) if 1 ≤ b < 2^{p}. In fact if a ∈ A_{n} and 2^{p} is the period of row a, then b ↦ a ∗ b defines a monomorphism of A_{p} into A_{n} (this is nothing more than the left self distributive law). Moreover, since each A_{n} is cyclic, all such monomorphisms arise in this way.

If we work within the category of one generator LD systems, then the Laver tables have an inverse limit A_{∞}. We now have the following result which is a consequence of work of Laver and Steel (see [8]).

Theorem. If there is a rank-to-rank elementary embedding, then A_{∞} is free.

It is not known whether this result can be proved in ZFC. On the other hand, it still is possible that one might be able to prove this theorem within Peano Arithmetic.

The freeness of A_{∞} has many equivalents, even working over a weak base theory such as Primitive Recursive Arithmetic [10]. One equivalent is that for every p there is an n such that the period of row 1 in A_{n} is at least p. On the other hand, Dougherty has shown that the function p ↦ n which witnesses this cannot be primitive recursive [9]. Moreover he has shown that the least n for which the period of row 1 is at least 32 is A_{9}(A_{8}(A_{8}(254))), where A_{k}(n) is the k^{th} level of the Ackermann function [9].

In addition to the original sources mentioned above, further reading can be found in [8], which serves as a comprehensive source on this subject.

9. Concluding remarks

Of course there has been no attempt at being comprehensive in choosing the topics presented above; I do not even pretend to have taken a representative selection. The examples all appear to have a somewhat ad hoc character to them. There is some truth to this and in fact that is partly the point — it is very difficult to predict from the outset of one’s study of a problem whether uncountability or some higher order of infinity is at all relevant. For instance, the conventional wisdom even among set theorists would be that uncountability should not be at all relevant understanding to the completeness of ACF_{0}, the Ramsey theory of the countably infinite, or the freeness of A_{∞}. The above discussion shows that even when it can be avoided, uncountability can still play an illuminating role in understanding the countable.

Additionally, the study of uncountability for its own sake sometimes leads to unexpected results about objects of a countable or even finite nature. Even if the use of uncountability ultimately turns out to be inessential, its role in the discovery process should not be ignored. This can be seen in Dehornoy and Laver’s algorithm for the word problems for LD systems and braids. It can also be seen in Veličković’s observation that Shelah’s proof shows that if an automorphism of P(ℕ)/fin has a Baire measurable lifting, then it is induced by a function from ℕ to ℕ.

Finally, there is the lesson illustrated in Serre’s conjecture and the Separable Quotient Problem: mathematicians do care about arbitrary subsets of Polish spaces and sets of unrestricted cardinality. All too often logicians make assumptions about what “real mathematicians” care about, what they are interested in, and what their biases are, without spending enough time exploring real mathematics itself. Even if these biases are as prevalent as we’ve come to believe they are (something I doubt), the examples above (and many more) are compelling testimony as to why these biases are misinformed and unnecessarily restrictive.

References

[1] U. Abraham, M. Rubin, and S. Shelah. On the consistency of some partition theorems for continuous colorings, and the structure of ℵ_{1}-dense real order types. Ann. Pure Appl. Logic, 29(2):123–206, 1985.

[2] S. A. Argyros, P. Dodos, and V. Kanellopoulos. Unconditional families in Banach spaces. Math. Ann., 341(1):15–38, 2008.

[3] A. V. Arhangel′skiĭ and V. I. Malykhin. Metrizability of topological groups (Russian). Vestnik Moskov. Univ. Ser. I Mat. Mekh., (3):13–16, 1996.

[4] J. E. Baumgartner. All ℵ_{1}-dense sets of reals can be isomorphic. Fund. Math., 79(2):101–106, 1973.

[5] L. G. Brown, R. G. Douglas, and P. A. Fillmore. Extensions of C^{∗}-algebras and K-homology. Ann. of Math. (2), 105(2):265–324, 1977.

[6] P. Dehornoy. Preuve de la conjecture d’irréflexivité pour les structures distributives libres. C. R. Acad. Sci. Paris Sér. I Math., 314(5):333–336, 1992.

[7] A fast method for comparing braids. Adv. Math., 125(2):200–235, 1997.

[8] Braids and self-distributivity, volume 192 of Progress in Mathematics. Birkhäuser Verlag, Basel, 2000.

[9] R. Dougherty. Critical points in an algebra of elementary embeddings. Ann. Pure Appl. Logic, 65(3):211–241, 1993.

[10] R. Dougherty and T. Jech. Finite left-distributive algebras and embedding algebras. Adv. Math., 130(2):201–241, 1997.

[11] R. Ellis. Distal transformation groups. Pacific J. Math., 8:401–405, 1958.

[12] I. Farah. Analytic quotients: theory of liftings for quotients over analytic ideals on the integers. Mem. Amer. Math. Soc., 148(702), 2000.

[13] All automorphisms of the Calkin algebra are inner. Ann. of Math. (2), 173(2):619–661, 2011.

[14] H. M. Friedman. Higher set theory and mathematical practice. Ann. Math. Logic, 2(3):325–357, 1970/1971.

[15] W. T. Gowers. Lipschitz functions on classical spaces. European J. Combin., 13(3):141–151, 1992.

[16] G. Gruenhage and J. Tatch Moore. Perfect compacta and basis problems in topology. In Elliott Pearl, editor, Open Problems in Topology II. Elsevier, 2007.

[17] L. Harrington. Analytic determinacy and 0^{♯}. J. Symbolic Logic, 43(4):685–693, 1978.

[18] B. Hartley. Subgroups of finite index in profinite groups. Math. Z., 168(1):71– 76, 1979.

[19] F. Hausdorff. Die graduierung nach dem endverlauf. Abhandlun. König. Sc̈hsis. Gessellsch. Wissenschaften, Math.-Phys. Kl., pages 296–334, 1909.

[20] N. Hindman. Finite sums from sequences within cells of a partition of N. J. Combinatorial Theory Ser. A, 17:1–11, 1974.

[21] N. Hindman and D. Strauss. Algebra in the Stone-Čech compactification, volume 27 of de Gruyter Expositions in Mathematics. Walter de Gruyter & Co., Berlin, 1998. Theory and applications.

[22] T. W. Hungerford. Algebra, volume 73 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1980. Reprint of the 1974 original.

[23] W. B. Johnson and H. P. Rosenthal. On ω^{∗}-basic sequences and their applications to the study of Banach spaces. Studia Math., 43:77–92, 1972.

[24] W. Just. A weak version of AT from OCA. In Set theory of the continuum (Berkeley, CA, 1989), volume 26 of Math. Sci. Res. Inst. Publ., pages 281– 291. Springer, New York, 1992.

[25] W. Just and A. Krawczyk. On certain Boolean algebras 𝒫(ω)/I. Trans. Amer. Math. Soc., 285(1):411–429, 1984.

[26] A. Kanamori. The Higher Infinite. Springer Monographs in Mathematics. Springer-Verlag, Berlin, second edition, 2003. Large cardinals in set theory from their beginnings.

[27] A. S. Kechris. Classical Descriptive Set Theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995.

[28] P. Larson. A brief history of determinacy. In The Handbook of the History of Logic, volume 6. Elsevier, 2012.

[29] R. Laver. A division algorithm for the free left distributive algebra. In Logic Colloquium ’90 (Helsinki, 1990), volume 2 of Lecture Notes Logic, pages 155– [30] The left distributive law and the freeness of an algebra of elementary

embeddings. Adv. Math., 91(2):209–231, 1992.

[31] Braid group actions on left distributive structures, and well orderings in the braid groups. J. Pure Appl. Algebra, 108(1):81–98, 1996.

[32] J. Lopez-Abad and S. Todorcevic. Generic Banach spaces and generic simplexes. J. Funct. Anal., 261(2):300–386, 2011.

[33] S. Mardešić and A. V. Prasolov. Strong homology is not additive. Trans. Amer. Math. Soc., 307(2):725–744, 1988.

[34] S. Mardešić. Strong shape and homology. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2000.

[35] D. Marker. Model theory: An introduction, volume 217 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002.

[36] D. A. Martin. Measurable cardinals and analytic games. Fund. Math., 66:287– 291, 1969/1970.

[37] Borel determinacy. Ann. of Math. (2), 102(2):363–371, 1975.

[38] D. A. Martin and J. R. Steel. A proof of projective determinacy. J. Amer. Math. Soc., 2(1):71–125, 1989.

[39] C. Martinez and E. Zelmanov. Products of powers in finite simple groups. Israel J. Math., 96(part B):469–479, 1996.

[40] V. D. Mazurov and E. I. Khukhro, editors. The Kourovka notebook. Russian Academy of Sciences Siberian Division Institute of Mathematics, Novosibirsk, sixteenth edition, 2006. Unsolved problems in group theory, Including archive of solved problems.

[41] J. Milnor. On axiomatic homology theory. Pacific J. Math., 12:337–341, 1962.

[42] J. Tatch Moore and S. Todorcevic. The metrization problem for Fréchet groups. In E. Pearl, editor, Open Problems in Topology II. Elsevier, 2007.

[43] J. Tatch Moore. The Proper Forcing Axiom. Proceedings of the 2010 meeting of the ICM, Hyderabad, India.

[44] J. Mujica. Separable quotients of Banach spaces. Rev. Mat. Univ. Complut. Madrid, 10(2):299–330, 1997.

[45] N. Nikolov and D. Segal. On finitely generated profinite groups. I. Strong completeness and uniform bounds. Ann. of Math. (2), 165(1):171–238, 2007.

[46] A. Pełczyński. Some problems on bases in Banach and Fréchet spaces. Israel J. Math., 2:132–138, 1964.

[47] N. C. Phillips and Nik Weaver. The Calkin algebra has outer automorphisms. Duke Math. J., 139(1):185–202, 2007.

[48] A. Robinson. On the metamathematics of algebra. North-Holland, Amsterdam, 1951.

[49] C. Rosendal. Automatic continuity of group homomorphisms. Bull. Symbolic Logic, 15(2):184–214, 2009.

[50] J. Saxl and J. S. Wilson. A note on powers in simple groups. Math. Proc. Cambridge Philos. Soc., 122(1):91–94, 1997.

[51] D. Segal. Closed subgroups of profinite groups. Proc. London Math. Soc. (3), 81(1):29–54, 2000.

[52] S. Shelah. Proper forcing, volume 940 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1982.

[53] S. Shelah and J. Steprāns. PFA implies all automorphisms are trivial. Proc. Amer. Math. Soc., 104(4):1220–1225, 1988.

[54] S. Todorcevic. Partition Problems In Topology. Amer. Math. Soc., 1989.

[55] Gaps in analytic quotients. Fund. Math., 156(1):85–97, 1998.

[56] Compact subsets of the first Baire class. J. Amer. Math. Soc., 12(4):1179–1212, 1999.

[57] Biorthogonal systems and quotient spaces via Baire category methods. Math. Ann., 335(3):687–715, 2006.

[58] Introduction to Ramsey spaces, volume 174 of Annals of Mathematics Studies. Princeton University Press, Princeton, NJ, 2010.

[59] S. Todorcevic and Carlos Uzcátegui. Analytic topologies over countable sets. Topology Appl., 111(3):299–326, 2001.

[60] S. Todorchevich and I. Farah. Some applications of the method of forcing. Yenisei, Moscow, 1995.

[61] B. L. van der Waerden. Beweis einer baudetschen vermutung. Nieuw Arch. Wisk., 15:212–216, 1927.

[62] B. Veličković. Definable automorphisms of 𝒫(ω)/fin. Proc. Amer. Math. Soc., 96(1):130–135, 1986.

[63] OCA and automorphisms of (ω)/fin. Topology Appl., 49(1):1–13, 1993.

Department of Mathematics, Cornell University, Ithaca, NY 14853– 4201, USA

  E-mail address: justin@math.cornell.edu