## January 14, 2009

### The Space of Robustness

#### Posted by David Corfield

At Tim Gowers’ blog, there has been a discussion in the ‘somewhat philosophical’ category of How can one equivalent statement be stronger than another?. Gowers gives the example of Hall’s theorem or Hall’s marriage theorem.

In graph theoretic guise,

Let $G$ be a bipartite graph with finite vertex sets $X$ and $Y$ of the same size. A perfect matching in $G$ is a bijection $f: X \to Y$ such that $x$ and $f(x)$ are neighbours for every $x \in X$.

So if members of $X$ are women and members of $Y$ are men, then in this heterosexual universe where women are only prepared to marry men, and vice versa, willingness to marry is represented by an edge between such pairs. A perfect matching sees everyone happily married to a partner. So when does this happy event occur?

Given a subset $A \subset X$, the neighbourhood $\Gamma(A)$ of $A$ is the set of vertices in $Y$ that are joined to at least one vertex in $A$. A trivial necessary condition for the existence of a perfect matching is that for every subset $A \subset X$ the neighbourhood $\Gamma(A)$ is at least as big as $A$, since it must contain $f(A)$, which has the same size as $A$. This condition is called Hall’s condition.

So, if our people can be happily married off, then for any subset of the women, the totality of men at least one of these women is happy to marry is at least as numerous. This is trivially the case, since this totality includes the men they do actually marry.

Much less obviously, Hall’s theorem states that the condition is also sufficient. So long as for every subset of women the subset of men loved by at least one of them is no less numerous, then everyone can be married off happily.

Gower’s observation is that while the existence of a perfect matching and the satisfaction of Hall’s condition are equivalent, the former seems to be stronger as the implication to the latter is very straightforward, while the reverse implication is quite tricky.

In the comments, Terry Tao observes,

Another reason why the “difficult” implication in Hall’s theorem is non-trivial is that it is non-functorial: there is no canonical way to obtain the perfect matching from a bipartite graph obeying Hall’s condition which respects isomorphisms (i.e. relabeling of the graph). Instead, one must make many arbitrary choices. Thus, it largely falls outside the range of “abstract nonsense”. (The fact that the theorem fails in the infinite case is perhaps a symptom of this non-functoriality; the inability to generalise the result to a more abstract setting indicates that the implication must depend sensitively on all of its hypotheses, and so cannot be replaced by overly “soft” techniques that are insensitive to one or more of these hypotheses.)

[Perhaps one could sum up the two cultures of mathematics succinctly as “mathematics which generalises” and “mathematics which does not generalise”? :-)]

As readers will know, I’m very interested in this ‘two cultures’ idea (I and II). From Gowers’ writings about his side of the divide, Tao’s characterisation could be extended to read “mathematics which does not generalise, but which suggestively helps in a number of different areas”.

This idea crops up in another part of the discussion where Gowers wonders why we don’t say that Fermat’s Last Theorem implies and is implied by the four-colour theorem (in ZFC). On this issue, Tao observes

…most “useful” implications in mathematics tend to have at least some robustness with respect to at least some kinds of perturbations.

So, new developments in the area of one statement ought to have an effect on the area of the other statement. All good mathematics must have some degree of this robustness.

It could be said that we at the Café enjoy robustness under the greatest degree of perturbation. But how to think of the space of robustness? Does the functorial/non-functorial mark a sharp split? Is there more to be said about the functorially robust? How much texture is there to the non-functorially robust? And what stops the non-functorially robust descending into the sludge of brute mathematical fact?

A small side thought: remember our attempts to categorify the Cauchy-Schwarz inequality had us looking at $(X \times_f X)$, for $f: X \to Y$, to compare its dimension to $|X|^2/|Y|$. Should we be interested in the fact that it reappears (as $X \times_Y X$) in David Ben-Zvi’s post?:

One of the great advances in representation theory (due in large part to some of the names listed at the top) was the realization that many of the algebras of greatest interest can be realized as convolution algebras of the form $Fun(X \times_Y X)$, where $X$, $Y$ are topological spaces or groupoids (in fact algebraic varieties or stacks) and $Fun$ is a function theory, such as cohomology and K-theory.

But then perhaps the observation that

…the algebra $Fun(X \times_Y X)$ of block diagonal matrices is Morita equivalent to the commutative algebra $Fun(Y)$

suggests we shouldn’t care about dimensions too much.

Posted at January 14, 2009 12:47 PM UTC

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

### Tao on “fruitfulness”; Re: The Space of Robustness

There was a somewhat related thread, on “fruitfulness” in Mathematics.

Tao, Fruitful or Truthful; Re: Two Cultures in the Philosophy of Mathematics?

“Fruitfulness is key. If a neologicist doesn’t care about the fruitfulness of their abstraction principles then they’ve rejected an enormously important part of Fregean thinking.”

An extremely interesting statement!

Did not Terry Tao list this as one of the (nonexlusive) markers of “good mathematics”?
[truncated]

Posted by: Jonathan Vos Post on January 14, 2009 5:21 PM | Permalink | Reply to this

### False yet fruitful; rhetoric and poetry; Re: The Space of Robustness

It fascinates me that a FALSE statement can be fruitful in Mathematics. Readers may supply their own favorite examples, but I’d mentioned that much of the centuries of development of Algebraic Number Theory may be seen as a sequence of false but fruitful “proofs” of Fermat’s Last Theorem.

As Quintilian, the prince of orators, had explained, rhetoric “is an art which relies on moving the emotions by saying that which is false.” Or as Touchstone puts it in Shakespeare’s As You Like It, “The truest poetry is the most feigning.”

Posted by: Jonathan Vos Post on January 14, 2009 6:36 PM | Permalink | Reply to this

### Re: The Space of Robustness

David wrote:

It could be said that we at the Café enjoy robustness under the greatest degree of perturbation.

There are two kinds of coffee beans: Coffea arabica and Coffea robusta. You can tell which one we enjoy at this café.

But how to think of the space of robustness? Does the functorial/non-functorial mark a sharp split?

There’s certainly no sharp split between ‘functorial’ and ‘nonfunctorial’ constructions. As Jim Dolan likes to emphasize, every construction becomes functorial when you reduce the number of morphisms in the source category sufficiently — or in other words, equip its objects with enough extra structure.

A good example is the proof that a set has as many total orderings as permutations. There’s no ‘bijective proof’ in the sense of an equivalence of groupoids over the groupoid of finite sets. But, there’s an equivalence of groupoids over the groupoid of finite totally ordered sets: the extra structure of a fixed total ordering allows us to functorially turn any other total ordering into a permutation.

Of course, a total ordering is the most structure you can put on a finite set! Using that much structure is almost playing tennis with the net down. So consider this equation:

$cosh^2 x = 1 + sinh^2 x$

Thanks to the theory of generating functions, this says there’s one more way to split a finite set into two even sets than into two odd sets. There’s no bijective proof in the sense of an equivalence of groupoids over the groupoid of finite sets. But in this case, just a little extra structure is enough to get a functorial proof.

Anyway: the questions you raise are very deep, much deeper than the ideas I’m toying with here. Perhaps the concept of ‘robustness’ will be part of some future metamathematics that we’re not capable of formalizing yet. And who knows — perhaps someday the ‘two cultures’ split will be formalized in terms of two different measures of ‘quality’ for theorems!

Posted by: John Baez on January 16, 2009 7:25 PM | Permalink | Reply to this

### Re: The Space of Robustness

So consider this equation: $cosh^2 x = 1 + sinh^2 x$ Thanks to the theory of generating functions, this says there’s one more way to split a finite set into two even sets than into two odd sets.

Is that what it means? I would interpret it as saying that there's the same number of ways to do each to a nonempty finite set, but one more way to do it to the empty set.

Certainly the number of ways to do either to an odd set is zero. There is one more way to split an even (finite) ordinal as the ordinal sum of two even ordinals than as such a sum of two odd ones, but I don't see how that's related.

Example with the even set $\{0,1\}$:

• Split into two even sets: $\varnothing \uplus \{0,1\}$, $\{0,1\} \uplus \varnothing$;
• Split into two odd sets: $\{0\} \uplus \{1\}$, $\{1\} \uplus \{0\}$;
• Split into two even ordinals: $\varnothing \uplus \{0,1\}$; $\{0,1\} \uplus \varnothing$;
• Split into two odd ordinals: $\{0\} \uplus \{1\}$ only.
Posted by: Toby Bartels on January 17, 2009 8:26 PM | Permalink | Reply to this

### Re: The Space of Robustness

Addendum: I go into this in detail because I want to make sure that I'm right, and I want to make sure that the puzzle is stated right so that people will be able to solve it.

I solved it, but I probably saw it before, so that may be cheating. But I offer this hint: The very little extra structure needed for a combinatorial proof is closely related to the exception for the empty set.

Posted by: Toby Bartels on January 17, 2009 8:33 PM | Permalink | Reply to this

### Re: The Space of Robustness

Toby wrote:

Is that what it means? I would interpret it as saying that there’s the same number of ways to do each to a nonempty finite set, but one more way to do it to the empty set.

Whoops — yeah, that’s what I should have said.

But here’s how I can pretend what I said was right:

I said “there’s one more way to split a finite set into two even sets than into two odd sets”, and you thought I meant “one more way per finite set” — but there’s really just one more way, total: one more way for the empty set, and the same number of ways for every other set.

Posted by: John Baez on January 17, 2009 10:59 PM | Permalink | Reply to this

### Re: The Space of Robustness

Gowers posed the question “How can one equivalent statement be stronger than another?” and gave the example of Hall’s theorem.

Tao suggests an answer: “… the “difficult” implication in Hall’s theorem […] is non-functorial: there is no canonical way to obtain the perfect matching from a bipartite graph obeying Hall’s condition which respects isomorphisms (i.e. relabeling of the graph). Instead, one must make many arbitrary choices.”

Given this, it’s possible that Hall’s theorem isn’t true in some form of logic where you can only describe a function by a specific algorithm, without making ‘arbitrary choices’.

(I’m tempted to say ‘in a form of logic without the Axiom of Choice’, but since the theorem is about finite sets, I don’t think that’s right.)

So: one way to make precise our intuition that one equivalent statement is stronger than another is by considering not just equivalence relative to a single form of logic, but a family of logics: the statements may not actually be equivalent in all these logics!

Posted by: John Baez on January 16, 2009 9:38 PM | Permalink | Reply to this

### Re: The Space of Robustness

This comment of yours definitely reminds me of Andreas Blass’s Seven Trees in One: look at the last sentence from the abstract:

Abstract: Following a remark of Lawvere, we explicitly exhibit a particularly elementary bijection between the set T of finite binary trees and the set T^7 of seven-tuples of such trees. “Particularly elementary” means that the application of the bijection to a seven-tuple of trees involves case distinctions only down to a fixed depth (namely four) in the given seven-tuple. We clarify how this and similar bijections are related to the free commutative semiring on one generator X subject to X=1+X^2. Finally, our main theorem is that the existence of particularly elementary bijections can be deduced from the provable existence, in intuitionistic type theory, of any bijections at all.

That sounds like a precise version of what you’re suggesting.

Posted by: Todd Trimble on January 16, 2009 10:38 PM | Permalink | Reply to this

### Re: The Space of Robustness

So: one way to make precise our intuition that one equivalent statement is stronger than another is by considering not just equivalence relative to a single form of logic, but a family of logics: the statements may not actually be equivalent in all these logics!

As others have mentioned, interpreting in an arbitrary topos (that is, in constructive logic) is one good way to do this. One commenter on the original post mentioned “Subsystems of Second Order Arithmetic” which is along similar lines (although I don’t know that anyone has made that precise).

While Hall’s marriage theorem is about finite sets and thus doesn’t require the axiom of choice in classical logic, in constructive logic even finite sets can behave in unexpected ways. And not only does the proof of the marriage theorem start with an application of PEM (“either there is a proper subset $A$ with $|\Gamma(A)|=|A|$ or for all $A$, $|\Gamma(A)|\gt|A|$”), but its inductive part assumes that every subset of a finite set is finite.

There is also a relationship between this approach and functoriality, because for several fragments of first-order logic there is a good notion of “functor that preserves that logic.” The ur-example is geometric logic, which is preserved by the inverse images of geometric morphisms.

Posted by: Mike Shulman on January 17, 2009 5:57 AM | Permalink | Reply to this

### Re: The Space of Robustness

Although I'm supposed to be the constructivist around here, it didn't occur to me to think of Hall's theorem constructively. This is because most finite combinatorics can be made easily constructive simply by interpreting it in $\Fin \Set$, the topos of finite sets in the strictest sense of ‘finite’. (That is, every finite set is $0$ or $1$ or $2$ or ….) In particular, I read ‘subset’ as ‘subobject in $\Fin \Set$’, or ‘decidable subset’ (that is a subset whose characteristic function factors through $\{\bot, \top\}$).

In other words, I'd interpret the theorem in an arbitrary topos $E$ simply by interpreting it in $\Fin E$ (see the Lab for how to define ‘finite’ in this sense without reference to an object of natural numbers). Of course, one would still have to check that the proof is (or can be made) constructive, but this sort of thing usually is; the proof at Wikipedia (for the finite case only of course) seems manifestly constructive (with this interpretation).

Posted by: Toby Bartels on January 18, 2009 1:36 AM | Permalink | Reply to this

### Re: The Space of Robustness

The category of sets is to the finite sets as a topos is to what?
For me, the most interesting answer to the question is the *locally* finite sets. For example, in the case of the topos associated to a topological space, one gets the theory of finite covering spaces this way. So the best way of toposifying a statement about finite sets is to think up a natural version of the statement for locally finite sets. This is usually not a well-defined procedure, I would think.

Posted by: James on January 18, 2009 2:11 AM | Permalink | Reply to this

### Re: The Space of Robustness

As you probably know, there are a bunch of different constructive (hence topos-theoretic) notions of “finite set” – see the nLab. One of them, a “decidable K-finite set,” is the same as a locally finite set.

So maybe there is a constructivist answer to the original question, namely “one direction of the implication is true for more notions of ‘finite’ than the other.”

Posted by: Mike Shulman on January 18, 2009 3:20 AM | Permalink | Reply to this

### Re: The Space of Robustness

I didn’t actually know that. I guess I’m of the opinion that locally finite is the (only) right definition (for Grothendieck toposes), but I’d love to be convinced otherwise.

Posted by: James on January 18, 2009 8:34 AM | Permalink | Reply to this

### Re: The Space of Robustness

It’s certainly one of the best. The decidable K-finite objects form a Boolean topos, as Toby pointed out, so all sorts of classical combinatorics can be interpreted with that notion of “finite.” And as you point out it “means what you would expect” in most presheaf and sheaf toposes. But I think it’s good not to forget that the other notions are out there too, since they do also come up occasionally. For instance, the free semilattice generated by an object $A$ is the set of K-finite subsets of $A$.

Posted by: Mike Shulman on January 18, 2009 10:24 PM | Permalink | Reply to this

### Re: The Space of Robustness

Kuratowski-finite sets have their uses in constructive mathematics (and thus, presumably, in a topos).

For example: A discrete topological space, or equivalently a discrete locale (that is, a locale whose frame is the power set of some set $S$), is compact if (and only if) $S$ is Kuratowski-finite. More generally, there are analogies between ‘compact subspace’ and ‘K-finite subset’. (And of course, if you want to phrase the definition of compactness in terms of ‘finite subfamily’ and interpret ‘family’ as an unindexed collection of subsets, then you must really mean K-finite.)

Posted by: Toby Bartels on January 18, 2009 11:06 PM | Permalink | Reply to this

### Re: The Space of Robustness

Hmmm. It’s pretty hard to argue with the statement that compactness is a reasonable notion of finiteness in a general topos, and generally different from local finiteness. In fact, it might be hard to think of something I agree more with. I concede.

Posted by: James on January 19, 2009 8:30 AM | Permalink | Reply to this

### Re: The Space of Robustness

Okay, you’re certainly right as far as that goes. So you have a constructive version saying “for any finite bipartite graph, meaning a pair $(A,B)$ of finite sets and a decidable binary relation between them, if for any decidable subset $T$ of $A$, the marriage condition holds, then there exists a matching.” And I suppose you can argue that “a pair of finite sets with a decidable binary relation” is the most appropriate constructive notion of “finite bipartite graph.”

I guess that if you are the constructivist around here, then I am the not-quite-a-constructivist who knows just enough to be dangerous. (-:

Perhaps then reverse mathematics (“subsystems of second order arithmetic”) is the way we have to go to logically analyze the strength of the statement.

Posted by: Mike Shulman on January 18, 2009 2:43 AM | Permalink | Reply to this

### Re: The Space of Robustness

I guess that if you are the constructivist around here, then I am the not-quite-a-constructivist who knows just enough to be dangerous. (-:

No, you're the not-quite-a-constructivist who isn't bound by preconceived notions of how to do constructive combinatorics and so can think of what I would not have thought of.

Perhaps then reverse mathematics (“subsystems of second order arithmetic”) is the way we have to go to logically analyze the strength of the statement.

I agree. More generally: $p \to q$ is stronger than $q \to p$ if it holds in fewer contexts, which agrees perfectly with how ‘stronger’ is used in logic.

Assuming that it is in fact a theorem (at least in contexts that we find of actual interest for their own sakes), then we can also say that $p \to q$ is deeper and less trivial than $q \to p$. However, it would be a mistake to conflate depth with strength in general; for example, depth is often achieved by rephrasing $r$ as $s$, where $r \leftrightarrow s$ is rather trivial (though not weak!) and $s$ is weaker than $r$. Depth is also achieved by getting the definitions just right, so that the theorems then become easy to prove (and often quite weak in this sense). The nice thing about comparing $p \to q$ and $q \to p$ is that they are equally complicated, so that depth and strength will better matched.

Posted by: Toby Bartels on January 18, 2009 3:46 AM | Permalink | Reply to this

### Re: The Space of Robustness

Are there any signs of category theory making sense of reverse mathematics, “subsystems of second order logic”, etc.?

Posted by: David Corfield on January 19, 2009 9:25 AM | Permalink | Reply to this

### Re: The Space of Robustness

From the little that I know about it (mostly thanks to Damir Dzhafarov), my current guess is that $RCA_0$ is closely related to the logic of complemented subobjects in a non-Boolean Heyting category with a NNO. He and I have been meaning to sit down and work this out precisely for a while.

Posted by: Mike Shulman on January 19, 2009 7:45 PM | Permalink | Reply to this

### Re: The Space of Robustness

Do keep us informed of your progress! I’d love to know whether the concepts of reverse mathematics gel with those of category theory. I don’t know why, but I imagined they wouldn’t.

Posted by: David Corfield on January 20, 2009 11:18 AM | Permalink | Reply to this

### Re: The Space of Robustness

It would be interesting to find a merger between reverse mathematics and category theory, but I wouldn’t expect reverse mathematicians to cheer on such a prospect. Some of the most prominent exponents of reverse mathematics, thinking here especially of Stephen Simpson and his allies, have exhibited incredible hostility toward category theory. This was most apparent in raging discussions – “brawls” would be a more appropriate term – on the list FOM (Foundations of Mathematics) about 10 years ago. Mostly concerning categorical foundations of mathematics, which seemed like an effrontery to these guys, but it could also be detected overall: the general perception seemed to be that category theory plays at most a minor technical role in the fabric of mathematics.

Posted by: Todd Trimble on January 20, 2009 3:46 PM | Permalink | Reply to this

### Re: The Space of Robustness

That’s why I’d like a category theoretic take-over!

Posted by: David Corfield on January 20, 2009 4:08 PM | Permalink | Reply to this

### Re: The Space of Robustness

I am under the impression that that Stephen Simpson is milder about category theory nowadays.

In any case, there is the categorical project of algebraic set theory which has been used to capture various forms of comprehension in constructive set theory. One may thus view algebraic set theory as a contribution to constructive reverse mathematics. [This is only one aspect of AST.]

There has been quite a bit of interest in constructive reverse mathematics in the previous years. For instance by Ishihara.

The full connections between these ideas, the ideas in CZF and the ones in AST have not been worked out, but this is a start.

Bas

Posted by: Bas Spitters on January 20, 2009 4:57 PM | Permalink | Reply to this

### Re: The Space of Robustness

Bas, I hope you’re right, but I’d be amazed if Simpson or Harvey Friedman were the least bit sympathetic to algebraic set theory. If you have evidence of that, I’d be very interested.

Posted by: Todd Trimble on January 20, 2009 5:20 PM | Permalink | Reply to this

### Re: The Space of Robustness

Todd, I can only say that I had pleasant private discussions with him about the effective topos at the Oberwolfach meeting on Proof theory. The wine and cheese at the MFO probably helped :-)

Simpson’s lecture was about issues related to intuitionism.

Bas

Posted by: Bas Spitters on January 20, 2009 5:59 PM | Permalink | Reply to this

### Re: The Space of Robustness

Thanks, Bas. I admit that I don’t follow FOM any more (I think it’s become a closed and moderated list, although the archives are open to public view), so I don’t know if there has been a change in attitude toward category theory.

I’ve met Simpson only once (in 2001, at a logic conference), and I can corroborate your impression that in person he comes off as friendly and eager to chat, far more so than his behavior on the internet led me to expect.

Posted by: Todd Trimble on January 20, 2009 7:31 PM | Permalink | Reply to this

### Re: The Space of Robustness

Well, one thing that threw me for a while was that one of the statements equivalent to $ACA_0$ over $RCA_0$ is, I believe, “every injective function $N\to N$ has an image.” For a while this looked like a death knell to a categorical interpretation of the base system $RCA_0$, at least, since in categorical logic every monomorphism is its own image.

But then I came up with the idea I mentioned before of the logic of complemented subobjects. The “$\Delta_1$-comprehension axiom” says that you can pick out a subset as long as it is both an image and a dual image, which basically amounts to saying that it is a complemented subobject. This also nicely explains how $RCA_0$ manages to be “constructive” in the sense of recursion-theory while still having Boolean logic.

When we get around to working out details, I’ll let you all know, probably on the nLab.

Posted by: Mike Shulman on January 20, 2009 4:42 PM | Permalink | Reply to this

### Re: The Space of Robustness

Here’s a little example in the spirit of John’s comment above and many comments at Gowers’ blog. I like it, and it might appeal to the regulars here.

Let $p$ be a prime number. Here are two conditions on a finite group: (1) it has an element of order $p$, and (2) its order is a multiple of $p$.

By Lagrange’s theorem (1) implies (2), and by Cauchy’s theorem (2) implies (1); so the two are equivalent. But if you’re like me, it feels like the first direction doesn’t really require a true argument (even if it might not be obvious when you first learn the subject), whereas the second does.

My favorite way of weakening structure is passing from the category of sets to a general topos. (I might not be the only one around here like that…) From my point of view, these are very natural contexts where choice doesn’t work well, even in the finite case. And actually, Cauchy’s theorem fails in general toposes. For instance, work in the topos of sets equipped with an automorphism, which you might call $BZ$. Then the group $Z/3Z$ with its non-trivial automorphism is a group in this topos, but it has no non-trivial map (in the topos) from the point. So there is no element of order 3.

I would guess that Lagrange’s theorem is still true and that the proof is the same, but I haven’t checked it.

Here’s another question: A third equivalent statement (1’) is that the group contains a subgroup of order $p$. Then the example above satisfies (1’). Is it equivalent to (2) in a general topos?

Posted by: James on January 17, 2009 3:17 AM | Permalink | Reply to this

### Re: The Space of Robustness

Are there good cases of statements which are true in your topos $B Z$, and which say something interesting about groups when read externally?

Posted by: David Corfield on January 20, 2009 11:05 AM | Permalink | Reply to this

### Re: The Space of Robustness

I’d guess the theorem that $H^n(Z,Z)=0$ for all $n\geq 2$ is an answer to an equivalent form of your question: are there interesting statements about the group $Z$ which can be expressed nicely in terms of the topos $BZ$? But unfortunately, I don’t know what that nice expression actually is.

A similar but less interesting statement is that $H^1(Z,K)\neq 0$, where $K$ is a field. I think the topos-theoretic translation of this that not every surjective homomorphism of $K$-vector spaces in $BZ$ splits. This actually kind of nice because it shows that any choice can cause problems, not just having to do it infinitely many times.

It would be nice to come up with an example about non-abelian groups using $H^1$ of $Z$ with coefficients in a non-abelian group.

Posted by: James on January 21, 2009 6:05 AM | Permalink | Reply to this
Read the post Paris in the Spring
Weblog: The n-Category Café
Excerpt: Mathematical ideas and how they combine
Tracked: April 15, 2010 12:41 PM

Post a New Comment