May 15, 2009

The Relevance of Predicativity

Posted by David Corfield If I get around to writing a second book in philosophy of mathematics, one thing I’ll probably need to retract is the ill-advised claim made in the first book that the notion of predicativity is irrelevant to mainstream mathematics.

Here’s a passage which goes directly against such a thought, from Nik Weaver’s Is set theory indispensable?

…the predicative universe exhibits a strikingly exact fit with the universe of ordinary mathematics. This is particularly well illustrated by the dual Banach space construction in functional analysis. Classically, every Banach space $V$ has a dual Banach space $V'$, but predicatively this construction is only possible when $V$ is separable. Remarkably, it seems to be a general phenomenon that for any “standard” Banach space $V$, its dual is also “standard” if and only if $V$ is separable. In other words, start with any well-known Banach space $V$ that commonly appears in the functional analysis literature, and iteratively take duals to create a sequence $V$, $V'$, $V''$,… . It will generally be the case that if $V$ is in common use then $V'$, $V''$, etc., will also be in common use – up to the first nonseparable space in the sequence. All spaces after that point will be highly obscure.

For example, take $V = L^1(\mathbb{R})$ (separable). Then $V' = L^{\infty}(\mathbb{R})$ (nonseparable), and $V''$ is an obscure space that has no standard notation. Or take $V = C[0, 1]$ (separable). Then $V' = M[0, 1]$ (nonseparable), and $V''$ is an obscure space that has no standard notation. Take $V = K(\mathcal{H})$ (the compact operators on a separable Hilbert space $\mathcal{H}$; separable). Then $V' = T C(\mathcal{H})$ (the trace class operators on $\mathcal{H}$; also separable), $V'' = B(\mathcal{H})$ (the bounded operators on $\mathcal{H}$; nonseparable), and $V'''$ is an obscure space that has no standard notation. If $V = c_0$ (separable) then $V' = l^1$ (separable), $V'' = l^{\infty}$ (nonseparable), and $V'''$ arguably has a standard notation – it is the space of Borel measures on the Stone-Čech compactification of the natural numbers – but it is certainly an obscure space that appears in the literature with extreme rarity. Examples of this type could be multiplied endlessly.

The explanation of this phenomenon is simple: generally speaking, duals of nonseparable spaces are highly pathological objects about which little of value can be said. This is characteristic of impredicative mathematics generally.

Does this tally with people’s experience?

Posted at May 15, 2009 4:53 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1967

Re: The Relevance of Predicativity

It matches my experience, back in the days when I did functional analysis.

I had a nice conversation about Nik Weaver’s work with Toby Bartels this Wednesday. He could summarize it a lot better than I could. But very roughly, it seems that Weaver has a version of logic that’s strong enough for most math that people actually do, but much weaker than ZFC. In this setup classical logic applies to countable sets, intuitionistic logic applies to larger sets, and the dual of a nonseparable Banach space doesn’t even exist.

I first heard of Weaver when learning about the Feferman-Schütte ordinal $\Gamma_0$.

According to Feferman, $\Gamma_0$ is the first ordinal that can’t be defined predicatively — and induction up to $\Gamma_0$ allows us to prove the consistency of predicative analysis. But Weaver has different views on this issue. Feferman has argued against these views, and Weaver has argued back. I’m too ignorant to have an opinion.

Posted by: John Baez on May 15, 2009 8:17 PM | Permalink | Reply to this

Re: The Relevance of Predicativity

I can’t say I care much about whether this or that predicative system is strong enough to do this or that portion of mathematics.

What I’m after are cases where the concept of predicativity casts light on ordinary mathematics, such as the link with separability of Banach spaces. Do we have more instances of this kind? Does category theory anything to say about the concept?

Posted by: David Corfield on May 16, 2009 10:38 AM | Permalink | Reply to this

Re: The Relevance of Predicativity

On nlab you mention Heyting pretoposes and predicative categories of sets. Is there a good philosophical reference on this somewhere?

Posted by: Kea on May 16, 2009 1:24 PM | Permalink | Reply to this

Re: The Relevance of Predicativity

This argument reminds me of the dichotomy between nice objects and nice categories. That is, the universe of impredicative mathematics is nice, whereas (Weaver is arguing that) the nice objects are the predicative ones. This raises (at least) two questions in my mind:

1. Is there a non-logical characterization of “predicative object” in an impredicative theory?
2. Is there any precise sense in which “predicative objects” can be shown to be “nice” in an impredicative theory?

Also, I have to ask: are the real numbers a “highly pathological object about which little of value can be said?” Or does Weaver’s version of predicativism allow the real numbers?

Posted by: Mike Shulman on May 17, 2009 4:04 AM | Permalink | Reply to this

Re: The Relevance of Predicativity

Also, I have to ask: are the real numbers a “highly pathological object about which little of value can be said?” Or does Weaver’s version of predicativism allow the real numbers?

The real line is separable and as such no problem for Weaver.

Posted by: Toby Bartels on May 17, 2009 7:14 PM | Permalink | Reply to this

Re: The Relevance of Predicativity

This argument reminds me of the dichotomy between nice objects and nice categories. That is, the universe of impredicative mathematics is nice, whereas (Weaver is arguing that) the nice objects are the predicative ones.

I see predicativism as about levels. If $A$ is an infinite set, then there's already something a little fishy about quantification over $A$, but it gets even worse if you use (universal) quantification over $A$ as a hypothesis or quantify over functions from $A$ or properties of $A$, and then it's worse yet if you use these as hypotheses, and so on.

You are limiting yourself if you refuse to even talk about such things, so we want a nice category (like a topos) where they can all be done. But at the same time, the predicativists have a point that you shouldn't blithely use constructs at higher levels to define new individuals at lower levels. In particular, by talking (without restriction) about sets of numbers, you can prove more things about numbers themselves than you ever could before, possibly things that you would rather remain agnostic about.

In other words, what is impredicative about thinking of $Set$ as a topos is not so much that it has power objects as that it has both power objects and equalisers, and in particular that you can form equalisers of things like $A \rightrightarrows \mathcal{P}A$ or worse.

Posted by: Toby Bartels on May 17, 2009 7:54 PM | Permalink | Reply to this

Re: The Relevance of Predicativity

Ok, so instead of a binary niceness criterion for objects we have a gradation thereof. But my questions still apply.

Posted by: Mike Shulman on May 18, 2009 4:33 AM | Permalink | Reply to this

Re: The Relevance of Predicativity

Ok, so instead of a binary niceness criterion for objects we have a gradation thereof.

I think that, to a predicativist, accepting power sets is something like accepting the axiom of Grothendieck universes. The original motivation for this is simply to be able to talk about more and more abstract ideas: on the one hand, (natural) numbers, properties of numbers, properties of properties of numbers, and so on; on the other hand, small categories, categories of small categories, categories of categories of small categories, and so on. But if one naïvely justifies this with an axiom of power sets or an axiom of universes, then one has also allowed things to be proved about natural numbers (and hence about small categories) that could never have been proved before (such as the consistency of $\mathbf{PA}$ or the consistency of $\mathbf{ETCS}$). And maybe that is not really what one wanted; certainly it is not what motivated the new axiom.

So yes, there's a gradation from $A$ to $\mathcal{P}A$ to $\mathcal{P}\mathcal{P}A$ and so on, but I wouldn't so much say that these are less and less nice (rather, more and more abstract, or more and more large) but that the equaliser of $A \rightrightarrows \mathcal{P}A$ is not nice.

But my questions still apply.

I don't mean to imply that they don't! Since I can't answer them yet, I'm instead trying to clarify what I think is relevant about them.

Posted by: Toby Bartels on May 18, 2009 7:55 PM | Permalink | Reply to this

Re: The Relevance of Predicativity

One remark about the relation between predicativity and categorification:

1. Predicativity may be a difficult concept, but slightly simplifying I think we may say that the core statement of predicativity is “power sets are problematic”

2. The categorified analogon of the power set is the category of presheafs on a category. Here the predicativist critique is entirely justified, because we can not arbitrarily iterate this construction. The reason is that the category of presheafs on a small category is large, and thus to iterate the the presheaf construction, we need a hierarchy of Grothendieck universes.

Posted by: anon on May 18, 2009 3:43 PM | Permalink | Reply to this

Re: The Relevance of Predicativity

A way to combine these, which is appropriate for the constructive school of predicativity (which accepts function sets but not power sets, and is generally considered too impredicative by the classical school of predicativism) is to say that the set of truth values is large.

Classically, of course, the set of truth values is $\{\top,\bot\}$, which is finite, small by anybody's standards. But if you're a constructivist, then you don't accept that this is the set of truth values, and then it becomes quite reasonable that (like the category of small sets, the $2$-category of small categories, etc) the set of truth values may be large.

Posted by: Toby Bartels on May 18, 2009 7:24 PM | Permalink | Reply to this

Re: The Relevance of Predicativity

Some people look at the full subcategory of the category of presheaves consisting of those which are small colimits of representable presheaves. Then all hom sets are small. This seems very reasonable to me. What I think is more interesting, though, is sheaves which are small colimits (in the category of sheaves) of representable sheaves. Sometimes I think this would be a better definition of (Grothendieck) topos, in that maybe it could avoid universes. It would be great if someone tried to develop things systematically from that point of view.

Posted by: James on May 19, 2009 8:48 AM | Permalink | Reply to this

Re: The Relevance of Predicativity

I just read some of Weaver’s papers. I think it’s a shame that he writes so polemically; it took me a while to get past his antipathy for ZFC and recognize the real content in what he is saying (especially because I think a lot of the reasons he dislikes ZFC are unreasonable). And I would venture to guess that many mathematicians are less open-minded than I am.

However, once I got past the polemic, I realized that he does have interesting mathematical things to say. In fact, he came closer than anyone else has to convincing me that predicativism is a viable way to do mathematics. (I still wouldn’t give much for his chances of convincing many mainstream mathematicians to adopt it anytime soon, though, short of someone discovering a contradiction in ZFC.)

I was quite surprised, though, given how much he makes of ZFC’s supposed vast disconnect from mathematical practice, how closely he still hews to the viewpoint of material (membership-based) set theory. It is obvious to me that structural (categorical) set theory is much more closely aligned to mathematical practice. Of course the natural question is whether there is a structural set theory with comparable strength to Weaver’s “CM.” It seems likely that it corresponds to a Heyting pretopos with a NNO satisfying some additional axioms, such as perhaps decidability and exponentiability of the NNO. Perhaps one might need to include some extra structure like a class of small maps as in algebraic set theory. But I haven’t looked at it carefully yet; any thoughts?

Posted by: Mike Shulman on May 19, 2009 3:45 AM | Permalink | Reply to this

Post a New Comment