Foundations

October 30, 2006

Posted by David Corfield

Something that has long troubled me is the question of why philosophers have shown what to my mind is an unwarranted interest in ‘foundational’ mathematical theories which make little or no contact with mainstream mathematics. Two posts have made me reconsider the problem. Alexandre Borovik discusses Zilber’s work on the Schanuel conjecture, while Kenny Easwaran wonders whether string theorists may use mathematics which depends on conjectured axioms of set theory.

In comments to both I mention the model theorist Angus MacIntyre’s interest in foundational theories which do make contact with the mainstream. He personally wants to relate some of Gropthendieck’s ideas to model theory. To return to the philosophers, is their interest in disconnected theories just a vestige of earlier failed foundationalist projects, or is there a continuing rationale?

For myself, I find Yuri Manin’s notion of foundations very attractive:

I will understand ‘foundations’ neither as the para-philosophical preoccupation with the nature, accessibility, and reliability of mathematical truth, nor as a set of normative prescriptions like those advocated by finitists or formalists. I will use this word in a loose sense as a general term for the historically variable conglomerate of rules and principles used to organize the already existing and always being created anew body of mathematical knowledge of the relevant epoch. At times, it becomes codified in the form of an authoritative mathematical text as exemplified by Euclid’s Elements. In another epoch, it is better expressed by the nervous self-questioning about the meaning of infinitesimals or the precise relationship between real numbers and points of the Euclidean line, or else, the nature of algorithms. In all cases, foundations in this wide sense is something which is relevant to a working mathematician, which refers to some basic principles of his/her trade, but which does not constitute the essence of his/her work. (Georg Cantor and His Heritage: 6)

This notion of foundations is closely related to what I’m driving at in this post about getting the ‘causal’ ordering of concepts right.

Posted at October 30, 2006 9:01 AM UTC

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

132 Comments & 2 Trackbacks

Re: Foundations

$MathML-enabled post (click for more details).$

Kenny Easwaran wonders whether string theorists may use mathematics which depends on conjectured axioms of set theory.

I doubt that there is anything in the relation of string theory (as currently understood) to set theory that is not already in the relation of quantum field theory to set theory.

From time to time I hear physicists chat about whether or not Gödel’s incompleteness theorem has any implication on physics. But I have never seen a convincing argument.

I could imagine that parts of physics depend on the axiom of choice. But I don’t know to which degree.

Posted by: urs on October 30, 2006 10:37 AM | Permalink | Reply to this

Re: Foundations

I could imagine that parts of physics depend on the axiom of choice.

You’d be surprised where AC shows up. One place in particular is algebraic geometry, where from what I can tell you basically can’t do without it. From what I hear, a certain chunk of the mathematics we’ve managed to fill in for string theory is essentially algebraic geometry, so that puts AC in play for string theory.

Posted by: John Armstrong on October 30, 2006 11:50 AM | Permalink | Reply to this

Re: Foundations

Kenny was imagining axioms beyond ZFC, and so beyond Choice. Choice has been given a thorough category theoretic going over. I wonder whether one could say something general here, that foundational concepts not easily expressible in category theoretic terms are unlikely to be useful. MacIntyre says something to this effect: “In much of modern mathematics, the set-theoretic component is of minor interest, and basic notions are geometric or category-theoretic.” (p. 197 of this).

Posted by: David Corfield on October 30, 2006 1:03 PM | Permalink | Reply to this

Re: Foundations

“In much of modern mathematics, the set-theoretic component is of minor interest, and basic notions are geometric or category-theoretic.”

This is very true, and part of why I reflexively shy away from Platonism/formalism debates, since they are based in the mathematics that was done a hundred years ago. I think most mathematicians realize this on some level and that leads to a general disinterest/distrust of the philosophy of mathematics since the philosophy hasn’t kept up with the mathematics.

Of course, then I ran into a book about structuralism and nothing has been the same since. Now I don’t see how anyone who takes Lawvere seriously can be anything but an ardent structuralist of some flavor or another.

—–

note to the administrators: why is it that many times I’ll hit preview and the site says that the comment is valid, but when I then hit ‘post’ it spits back, “Please preview your modified entry before posting it.” Usually this seems accompanies by changing ” into some control string or another, but not always.

Posted by: John Armstrong on October 30, 2006 1:18 PM | Permalink | Reply to this

Re: Foundations

…then I ran into a book about structuralism and nothing has been the same since

Which book was that? Many have been written with only a passing nod in the direction of category theory. If yours was one of these, did you think it got to the heart of the matter, or were you just glad that it didn’t seem to be a century out of date?

Regarding the ‘Preview’ request, as far as I encounter it, whenever I have made an alteration to the comment, including the first writing, it asks me to preview before posting. You seem to be getting this even without making alterations. Which browser are you using?

Posted by: David Corfield on October 30, 2006 1:27 PM | Permalink | Reply to this

Re: Foundations

The book was Shapiro’s Philosophy of Mathematics: Structure and Ontology. It didn’t really have that much directly on category theory, but the subject was raised a few times. Just providing that framework was enough for my own preconscious thoughts to click into place and fill in his category theory gaps.

—–

I’m using Safari 2.0.4 on OS 10.4.8

Posted by: John Armstrong on October 30, 2006 2:09 PM | Permalink | Reply to this

Re: Foundations

Is this just ‘catch-up’ philosophy, or did you see lines of research opening up in Shapiro’s theses? Around 1900 philosophical ideas did some work in the development of foundational languages. Philosophical ideas have also had their effect on category theory via Mac Lane and Lawvere. If we are to live up to Michael Friedman’s demand that philosophy be involved in prospective rationality, the development of new constitutive langauges, then we need to act like them.

Posted by: David Corfield on October 30, 2006 6:13 PM | Permalink | Reply to this

Re: Foundations

Honestly I must confess that I don’t know enough of the SotA to say whether it was catch-up or new. It was aimed at a popular audience, or at least more popular than it could have been. On that I’d guess it skews towards catch-up but I can’t say for sure.

Posted by: John Armstrong on October 30, 2006 11:08 PM | Permalink | Reply to this

Re: Foundations

It seems like a lot of this categorical stuff gets justified using Grothendieck universes which have something to do with “strongly inaccessible cardinals” about which I know nothing, but apparently their existence is outside of ZFC.

Posted by: Aaron Bergman on October 30, 2006 3:18 PM | Permalink | Reply to this

Re: Foundations

MacIntyre seems to be concerned with the ‘serious’ use of set theory in model theory, in the sense Urs used it for category theory:

There is still a difference between using a category here and there and taking things seriously.

So one might need to distinguish between a ‘here and there’ use and a ‘serious’ use of set theoretic principles. Perhaps one might invoke the continuum I have discussed elsewhere which runs from useless to useful to essential.

Posted by: David Corfield on October 30, 2006 5:57 PM | Permalink | Reply to this

Re: Foundations

$MathML-enabled post (click for more details).$

A Grothendieck universe $U$ is just a set of sets that contains the empty set and is closed under all the operations you ever use, as listed here.

So, working in $U$ is almost like like working in the class of all sets.

The advantage is that when you want to say “the set of all sets”, you can do it without Bertrand Russell’s ghost rapping you over the knuckles with a paradox. You just say “the set of all sets in $U$ ” - or in other words, “ $U$ ”.

This is handy, because in category theory there are lots of very important theorems about “the category of all categories” - the one problem being that in normal set theory, there is no category of all categories.

So, we say a category is small if its set of objects lies in $U$ and its set of morphisms lies in $U$ . Then we can talk about the “category of all small categories” - and this really exists. It’s just not small.

There are times when we need to play this trick more than once. For example, the category of all categories really comes with extra structure - it’s a 2-category! Let’s call this $\mathrm{Cat}$ . There are lots of nice theorems about “the 2-category of all small 2-categories”, but alas, $\mathrm{Cat}$ does not live in there: it’s not small.

To get around this, we just assume our Grothendieck universe $U$ is an element of some bigger Grothendieck universe, say $U'$ .

As you can see, we might need to keep doing this. So, we adopt the Axiom of Universes: every set is a member of some Grothendieck universe.

The key thing to keep in mind is that all this is just a trick to do perfectly reasonable mathematics without having to worry about Russell’s paradox. It’s not that we’re wild-eyed logicians desperately eager to construct ever-larger sets. It’s just that a good way way to state theorems about categories is to talk about $\mathrm{Cat}$ , the 2-category of all categories. And, a good way to state theorems about things like $\mathrm{Cat}$ (namely 2-categories) is to talk about $2\mathrm{Cat}$ , the 3-category of all 2-categories. And so on. But, it’s no fun having Russell’s ghost rapping us on the knuckles all the time. So, we beat him back with the Axiom of Universes.

Of course, you may think it’s a bit wild-eyed to prove theorems about all 3-categories so you can deduce consequences about $2\mathrm{Cat}$ so you can deduce consequences about 2-categories so you can deduce consequences about $\mathrm{Cat}$ so you can deduce consequences about categories so you can deduce consequences about some specific category so you can deduce consequences about objects in there. But honest - it’s perfectly reasonable, and lots of fun.

Posted by: John Baez on October 30, 2006 6:16 PM | Permalink | Reply to this

Re: Foundations

$MathML-enabled post (click for more details).$

The general theorems of mathematical physics are quite heavily influenced by the axiom of choice - mainly theorems that involve real or functional analysis. But concrete computations are, I believe, completely unaffected by the axiom of choice.

The discussion over at Antimeta that David was referring to raised the point that one might want to check which additional axioms are actually required for describing the observed world around us - or which are required for describing the speculative world of quantum gravity.

Let $T$ be a “physical theory” of your choice, for you favorite notion of “theory”, like $T =$ classical mechanics, $T =$ quantum mechanics or $T =$ quantum field theory.

Does $T$ require the axiom of choice?

Or is it like this: $T$ is most conveniently formulated using AC, but for practical purposes we could do without?

Posted by: urs on October 30, 2006 7:00 PM | Permalink | Reply to this

Re: Foundations

$MathML-enabled post (click for more details).$

These different “ $T$ ’s” - classical mechanics, quantum mechanics, quantum field theory - sound quite vague to me.

We can formulate any of these theories in a stripped-down way using a minimum of logical infrastructure. But then, we need more infrastructure to prove deeper theorems.

If by “quantum mechanics” you mean “everything about quantum mechanics that you’ll find proved in Reed and Simon’s 4-volume masterpiece”, then you definitely need some powerful infrastructure, to get the Hahn-Banach and Tychonoff theorems - they use ZFC, and the axiom of choice is essential in their approach.

For an easier example, you might let $T$ be “the theory of groups”. If we simply mean “theory” in the sense of Lawvere’s “algebraic theories”, we can formulate this using very stripped-down logic. But then, we can only prove theorems like $((g h)h^{-1})g^{-1}= 1.$ If we want to get the classification of finite simple groups, we need more logical infrastructure. And if we want to settle the Whitehead problem, we’ll need to go beyond ZFC!

In physics I think it’s important to identify the amount of infrastructure needed to do concrete calculations - the sort we check against experiment. This is less than the amount we need to prove general theorems.

An interesting case is Penny Smith’s (sadly erroneous) proof that the Navier-Stokes equations have global solutions. I don’t know if she used results relying on the axiom of choice, but I wouldn’t be surprised, because the Hahn-Banach theorem and Tychonoff theorem are so basic in functional analysis. Interestingly, even when she thought she’d proved existence of global solutions, she emphasized that her method would not provide an algorithm to numerically solve the equations. This suggests she was using nonconstructive methods, e.g. proof by contradiction or the axiom of choice. That’s pretty common in this subject.

Posted by: John Baez on October 30, 2006 8:26 PM | Permalink | Reply to this

Re: Foundations

“It’s not that we’re wild-eyed logicians desperately eager to construct ever-larger sets.”

This comparison doesn’t exactly seem fair to me. The Axiom of Universes is exactly the axiom that states there is a proper class of strongly inaccessible cardinals. Grothendieck postulated it to make various proofs easier (namely ones about categories of categories). Set theorists postulated it to make other proofs easier (namely ones about the consistency of ZFC and the like).

It turns out that the desires of the set theorist drive an endless search for new axioms (because the issues they’re interested in are very often things about consistency and construction of models and the like) while the desires of algebraists so far only go up to this point. But the set theorists aren’t after these things just because they’re big - they’ve just got their own sort of evidence.

And especially once one gets past measurable cardinals, the evidence does become more mathematically interesting, involving determinacy considerations for sets of real numbers and the like, rather than just consistency.

Posted by: Kenny Easwaran on October 31, 2006 6:39 PM | Permalink | Reply to this

Re: Foundations

John wrote about Grothendieck’s universe axiom:

Of course, you may think it’s a bit wild-eyed to prove theorems about all 3-categories so you can deduce consequences about 2Cat so you can deduce consequences about 2-categories so you can deduce consequences about Cat so you can deduce consequences about categories so you can deduce consequences about some specific category so you can deduce consequences about objects in there. But honest - it’s perfectly reasonable, and lots of fun.

But at the same time, you should remember that you really are making your axiom system stronger. That is, even if you intend to use this axiom only to simplify the overhead as you prove a theorem about objects in a specific category, it may (in principle) turn out that this theorem actually cannot be proved in the weaker axiom system (ZFC, say).

Now, the only examples that I know of this are terribly artificial, piggy-backing on Gödel’s incompleteness theorems. But they are always there. This is because each stage of the universe axiom (assuming that you do apply it only one universe at a time, as usual) proves the consistency of the previous stage; but that previous stage (if in fact consistent) cannot prove its own consistency.

I somehow doubt that there are any interesting examples. But there really ought to be a way to know for sure.

Posted by: Toby Bartels on November 1, 2006 10:51 AM | Permalink | Reply to this

Re: Foundations

$MathML-enabled post (click for more details).$

Urs Schreiber wrote:

I could imagine that parts of physics depend on the axiom of choice.

The general theorems of mathematical physics are quite heavily influenced by the axiom of choice - mainly theorems that involve real or functional analysis. But concrete computations are, I believe, completely unaffected by the axiom of choice.

For example, when kids in math grad school get serious about integrals, they learn Lebesgue integration. The standard theory of Lebesgue integration says there are nasty things called nonmeasurable sets: subsets of the line whose length is undefined. But, you use the axiom of choice to show these nonmeasurable sets exist! If you’re willing to drop the axiom of choice and use the axiom of determinacy instead, you can show that all subsets of the real line are measurable.

When you actually come to doing integrals, you never meet a nonmeasurable set, so none of this matters when it comes to concrete computations.

Another thing we use a lot in analysis is Tychonoff’s theorem: any product of compact spaces is compact. This implies the Banach-Alaoglu theorem: the unit ball in the dual of any Banach space is weak- $\star$ compact. People use this a lot to prove existence of solutions of differential equations.

But again, if you actually want to exhibit a solution of a differential equation, you don’t use these general theorems. Everything the axiom of choice helps you do is nonconstructive: it doesn’t really let you do anything concrete, it just lets you prove you “could” do it.

People also use the axiom of choice to prove the Hahn-Banach theorem, another basic tool in analysis. This says that you can always extend a bounded linear operator from a subspace of a Banach space to the whole thing.

The point is that the axiom of choice guarantees you can do various things, without saying how. In concrete situations you often can see how.

So, the axiom of choice just lets you prove theorems without worrying about certain “details” that become crucial when you’re doing concrete calculations. However, you pay a price for this: it lets you construct nasty things like nonmeasurable sets, which you’d never see how to construct in practice.

All this suggests we should adopt a flexible attitude towards axiom systems: instead of believing in one and regarding its consequences as true, we should think of each extra axiom as giving us extra powers, and pay some attention to what each extra power lets us do. Even if we don’t “really” have these extra powers in general, we may have them in certain circumstances.

Of course it’s a lot of work keeping track of more than one axiom system, so most mathematicians don’t have the patience for it.

Posted by: John Baez on October 30, 2006 5:48 PM | Permalink | Reply to this

Re: Foundations

Actually, all this determining where exactly AC comes up ties into a question Zuckerman asked me today.

Consider a rooted tree so that
(a) every vertex has a finite number of children
(b)every path from the root terminates (in a finite number of steps)

Does it follow from this that the tree is finite?

I gave two different proofs off the top of my head that it does, which led him to ask the follow-up: do those require the Axiom of Choice? I didn’t think so, but I had trouble convincing him of that fact. Maybe someone here has an idea how to settle it?

Posted by: John Armstrong on October 30, 2006 11:06 PM | Permalink | Reply to this

Choice.

It’s often hard to notice use of dependent choice. Look up “König’s Lemma”.

Posted by: Toby Bartels on October 31, 2006 12:22 AM | Permalink | Reply to this

Re: Foundations

AC really only applies to infinite sets: you can always apply the choice “trick” on finite sets.

It seems obvious to me that the tree is finite: if the largest number of child nodes for any node is m and the longest path in the tree is of length n, the total number of nodes in the tree is going to be bounded by m to the n, which is clearly finite for any finite m and n.

König’s Lemma only applies to graphs taken by assumption to have an infinite number of nodes.

If you had to use it or AC in this proof, it would suggest that you had an infinite tree. ;-)

Posted by: Marc Hamann on October 31, 2006 3:03 AM | Permalink | Reply to this

Re: Foundations

So what’s the a priori finite set you think you’re making a choice over? The dual to your statement about when you need AC is that if you assert that you don’t need AC you’re assuming that a given set is finite.

Posted by: John Armstrong on October 31, 2006 3:19 AM | Permalink | Reply to this

Re: Foundations

So what’s the a priori finite set you think you’re making a choice over?

I’m not taking any a priori set. I’m saying that you don’t need to invoke the AC until you know you have an infinite set.

To grasp this, consider a different approach to solve the problem: show that you can do choice on this set (for example that in a finite number of steps, using plain ZF, you can select any particular path from any particular directed subset) without invoking the AC: you would thereby prove that the set is finite.

Posted by: Marc Hamann on October 31, 2006 4:21 AM | Permalink | Reply to this

Re: Foundations

Okay, let’s see it. I’ve got two proofs and both seem to use Dependent Choice (which if you paid attention is what we’re considering). It’s easy enough to wave your hands and say “it all works out”, but it’s harder to step up and prove it.

1. Assume each node has finitely many children and the tree is infinite. Then the root has at least one infinite child. Choose one (finite) and recurse: that child has at least one infinite child. Choose one (finite) and so on. This gives an infinite path, so the first condition cannot be satisfied.

The problem is that even though each choice is finite, which choice is to be made depends on the choices that came before. This is DC.

2. Consider the algorithm for a breadth-first search. This walks through the tree and visits every node. An infinite recursion is not possible since that would mean an infinite depth path. Also, no node requires more than a finite number of iterations of its for-loop.

It seems that the algorithm must terminate, but something still feels uneasy to me. Besides that, the tree only comes with a set of children rather than an ordered set, so the algorithm must choose an order (finite) at each node. It doesn’t seem to depend on anything outside the node itself, but I think I’m right to be cautious here.

So, if you can prove that the second one actually is tight and never uses DC, great. If not, what’s your proof?

Posted by: John Armstrong on October 31, 2006 4:56 AM | Permalink | Reply to this

Re: Foundations

Suppose for contradiction that this tree is infinite. At a finite depth there are only a finite number of nodes (by induction), so the depth must be unbounded.

Step 1

Choose one vertex at depth 1, one at depth 2 etc. We get an infinite sequence of vertices a_1, a_2….

Step 2

For each of a_1, a_2, etc in turn, we check if the depth 1 grandparent vertex has an infinite number of members of the sequence {a_n} in its subtree. When we find an a_m that this is true, we halt* and throw out any members of {a_n} that don’t belong to this subtree.

Repeat the process on the new subtree, with the (still infinite) subsequence of {a_n}, and so on to get an infinite path, which is a contradiction.

*We know that this process will halt after a finite number of steps, since the number of depth 1 vertices is finite, and so at least one depth 1 vertex must have an infinite subsequence of {a_n} in its subtree, while only a finite subset of {a_n} can have depth 1 grandparent vertices that don’t have this property, so they will be exhausted in a finite number of steps.

Step 1 involves finite choice, and the choices are independent.

Step 2 is deterministic.

Does this solve the problem?

Posted by: simon on October 31, 2006 7:35 AM | Permalink | Reply to this

Re: Foundations

That was needlessly complicated. Since the set of vertices at depth n is finite, we can order it with no problem.

So first, choose such an ordering, for the whole tree at each depth independently.

Now choose the first vertex at depth 1 with an infinite subtree, then the first at depth 2 that belongs to that subtree, and has its own infinite subtree, etc.

We aren’t really making dependent choices since we are “choosing” deterministicly using an ordering independent of our choices.

Posted by: simon on October 31, 2006 7:53 AM | Permalink | Reply to this

Re: Foundations

So first, choose such an ordering, for the whole tree at each depth independently.

So for each depth (which may be infinite a priori) choose one of a finite set of orders on the nodes of that depth. Sorry, that’s CC.

Posted by: John Armstrong on October 31, 2006 3:58 PM | Permalink | Reply to this

Re: Foundations

I believe these proofs still require Choice. I remember hearing that without Choice, it is consistent that there is an infinite sequence of finite sets (in fact, sets of cardinality 2) with no choice function on them. The analogy is that with an infinite set of pairs of socks, one can’t choose one sock from each pair.

If you could order the whole tree, then you could order this infinite set of socks, and then pick the first element of each. So your proof (either requiring an ordering of the tree, or a choice of one element at each level) seems to require Choice.

Posted by: Kenny Easwaran on October 31, 2006 6:48 PM | Permalink | Reply to this

Re: Foundations

I should have reviewed the axiom of choice, and not assumed that I could guess the meanings of terms like dependent choice from context, before commenting. Embarrassing, but thanks for the correction.

Posted by: simon on November 8, 2006 2:51 AM | Permalink | Reply to this

Re: Foundations

If not, what’s your proof?

My joke about König’s Lemma notwithstanding, Toby’s idea is actually the easiest.

Towards a contradiction, assume there are infinite nodes in the tree. Then by König’s Lemma, there would be at least one infinite path, which contradicts the premise.

As with AC, DC still only adds power to ZF for infinite sets: you already have all you need to make the choice for strictly finite cases, as simon has demonstrated.

Posted by: Marc Hamann on October 31, 2006 3:22 PM | Permalink | Reply to this

Re: Foundations

Yes, I follow the use of König’s lemma. That uses DC, though, and you seemed to indicate that you could do it without DC.

Posted by: John Armstrong on October 31, 2006 3:56 PM | Permalink | Reply to this

Re: Foundations

Since ultimately I’m a computer scientist, the easiest way to show the reasoning here is to describe an algorithm and give an indication how it uses ZF.

My claim is that a traversal of the tree described (finite branching/finite paths) necessarily terminates (and hence finite).

Start at the root (which was given), iterate (in random order) over the finite list of children and recursing on each.

Surely you will accept I can do this on a finite set without using any kind of choice axiom? If not, even membership and subset would imply choice.

Since each iteration is over a finite number of elements, it will terminate. Since each recursive path down the tree is stipulated by assumption to be finite, it will terminate.

Therefore, the traversal as a whole will terminate. Therefore, there are a finite number of nodes.

We can easily model this in pure set theory by representing the tree as a set whose members are the root’s children, each child’s members are its child nodes, etc.
The requirement that all paths are finite is the Axiom of Foundation, and the bound on the size of each node set ensures that we can iterate over each of these using only basic set-theoretic operations.

Posted by: Marc Hamann on October 31, 2006 4:41 PM | Permalink | Reply to this

Re: Foundations

Maybe increasing the pseudocode to include a list node.visited_children so the random selection won’t repeat. That gives a decision process.. I think that might plaster over the handwaving I did in proof 2.

Actually, I just thought of another that might work in a different way: Tree = {*} or {finite set of Trees}. * is finite, and if each of finitely many children is finite then the tree is finite, so by induction all such trees constructible in finitely many steps are finite. Since every path from the root terminates, the tree is constructible in finitely many steps.

Or is there a hidden choice in there?

Posted by: John Armstrong on October 31, 2006 4:54 PM | Permalink | Reply to this

Re: Foundations

We can do it purely set theoretically too. To simplify things, let’s assume urelements with a distinct one for each leaf node.

Starting from our root set, which has a finite cardinality, take the grand union. The cardinality of the resulting set will be finite, since it will grow at most by a finite number.
Continue taking the grand union, each time adding only finitely many, until you have only urelements in the set.
This state must be arrived at in a finite number of steps by the well-foundedness condition.

Since each step added only finitely many to the cardinality, the final set also has finite cardinality.

Posted by: Marc Hamann on October 31, 2006 7:11 PM | Permalink | Reply to this

Re: Foundations

Well-foundedness says that each branch is only finitely deep, not that there is a single depth that no branch exceeds.

Posted by: Kenny Easwaran on November 2, 2006 10:42 PM | Permalink | Reply to this

Re: Foundations

Well-foundedness says that each branch is only finitely deep, not that there is a single depth that no branch exceeds.

I’m starting to wonder if I’m being put on…
But, please remember the OTHER condition that there is finite branching. If there is a finite number of branches (which has gone over ad nauseam) and each branch is finite, there must be a maximum length of branches.

Another thing for the doubters to remember is that just because the infinite case is not constructively provable does NOT mean that the finite case in not constructively provable. The excluded middle doesn’t hold in intuitionistic math, and provability can be expected to be different across the finite/infinite divide.

Posted by: Marc Hamann on November 3, 2006 4:35 AM | Permalink | Reply to this

Re: Foundations

Finite branching just means that at each branch point there are only finitely many immediate successors. Without some form of Choice, finite branching and no infinite paths don’t entail that there are only finitely many branches in total, with a uniform upper bound on their length.

If you assume that the tree is finite, everything’s fine - there’s no need for choice. But proving that the tree is finite is exactly what we need to do here! Contrary to what someone said earlier, Choice is unnecessary only when we know the relevant collection of sets to be finite, but it is often necessary when we don’t know whether it’s finite or infinite. (That earlier comment suggested that it was only necessary when we knew the collection to be infinite.)

Posted by: Kenny Easwaran on November 4, 2006 1:43 AM | Permalink | Reply to this

Re: Foundations

Contrary to what someone said earlier, Choice is unnecessary only when we know the relevant collection of sets to be finite, but it is often necessary when we don’t know whether it’s finite or infinite. (That earlier comment suggested that it was only necessary when we knew the collection to be infinite.)

As over-played as this thread has gotten now, I think we actually might have learned/been reminded of some important things.

First, there is a bigger gulf between constructive mathemetics and traditional formalist mathematics than arguing about a couple axioms: the systems generated can be quite different in their interpretations of particular structures, for example, in this case, the notion of infinity.

Second, as Gödel proved, you often can’t coherently formulate a proof about a system from within the system. In the current instance, the proof about infinity is dependent upon whether you admit infinity as a given rather than a constructed entity.

Third, foundational discussions are fractious and difficult. Maybe CT shouldn’t want to become a foundation; it might bring an end to the relative harmony of the CT community. ;-)

Posted by: Marc Hamann on November 4, 2006 7:51 PM | Permalink | Reply to this

Re: Foundations

“Actually, I just thought of another that might work in a different way: Tree = {*} or {finite set of Trees}. * is finite, and if each of finitely many children is finite then the tree is finite, so by induction all such trees constructible in finitely many steps are finite. Since every path from the root terminates, the tree is constructible in finitely many steps.

Or is there a hidden choice in there?”

There’s no hidden choice, but there’s a hidden assumption: that if every path is finite, then there is a finite number n such that every path has length not greater than n. This isn’t true a priori (it’s false if we drop the stipulation that each node has a finite number of children, for example), and in this case it’s equivalent to what you’re trying to prove.

Posted by: Adam Stephanides on November 2, 2006 3:23 PM | Permalink | Reply to this

Re: Foundations

We can easily model this in pure set theory by representing the tree as a set whose members are the root’s children, each child’s members are its child nodes, etc.

Incidentally, this is exactly what got Zuckerman started in the first place: the topos of hereditarily finite sets.

Posted by: John Armstrong on October 31, 2006 4:57 PM | Permalink | Reply to this

Re: Foundations

Incidentally, this is exactly what got Zuckerman started in the first place: the topos of hereditarily finite sets.

My best guess to a response (without knowing the actual content of his beef) is that it is easy to confuse performing a choice operation constructively with invoking a choice axiom ex machina, even though they are quite different beasts. ;-)

Posted by: Marc Hamann on October 31, 2006 7:21 PM | Permalink | Reply to this

Re: Foundations

He wasn’t complaining, just exploring, so I think “beef” is overstating it a bit. He’s gotten into set theory lately, and even poking into ill-founded set theory. One of his latest toys is this topos.

Basically, at the department’s tea he asked me about the finiteness of that tree, and it was obvious to me. Then he asked if I could do it without even dependent choice and I’m still not entirely sure.

Posted by: John Armstrong on October 31, 2006 8:00 PM | Permalink | Reply to this

Re: Foundations

I don’t see how this is different from the approaches above. Each particular iteration will eventually terminate by reaching an end node, but it’s not clear that there are only finitely many iterations unless you already know the entire tree is finite (after all, you have one iteration for each node).

I believe that given a countably infinite set of pairs with no choice function, it should be quite easy to construct an infinite tree with only pairwise branching and no infinite branches. So there should be no way to prove this theorem without assuming some fairly weak form of choice that prevents this situation. König’s Lemma seems like exactly what we want.

Posted by: Kenny Easwaran on October 31, 2006 7:14 PM | Permalink | Reply to this

Re: Foundations

I believe that given a countably infinite set of pairs with no choice function, it should be quite easy to construct an infinite tree with only pairwise branching and no infinite branches

Well, all I can say is prove (or demonstrate) that and we might have more to talk about.

;-)

Posted by: Marc Hamann on October 31, 2006 7:29 PM | Permalink | Reply to this

Re: Foundations

“I believe that given a countably infinite set of pairs with no choice function, it should be quite easy to construct an infinite tree with only pairwise branching and no infinite branches.”

I’ll give it a go: suppose S = {S_1, S_2, S_3, …} is such a set. Then let the tree’s nodes be the empty set (the root), and all finite sets of the form {a_1, a_2, …, a_n} for some n, where a_i is a member of S_i for all i less than or equal to n. The children of any node N are the two nodes which contain all of N’s elements and one additional element. This tree is infinite, but it has no infinite branch, because an infinite branch would define a choice function on S.

Note that though there is no infinite branch, there are branches of any finite length. Also, the tree has no leaves, and so the traversal described by Marc Hamann in his Oct. 31 4:41 PM post never completes a single path.

(Apologies for the poor formatting.)

Posted by: Adam Stephanides on November 1, 2006 3:03 PM | Permalink | Reply to this

Re: Foundations

Also, the tree has no leaves, and so the traversal described by Marc Hamann in his Oct. 31 4:41 PM post never completes a single path.

How could a tree with no leaves have finite paths? A path in a tree is finite precisely because it terminates in a leaf.

Posted by: Marc Hamann on November 1, 2006 3:31 PM | Permalink | Reply to this

Re: Foundations

Yes, it’s a counter-intuitive situation: we can always extend any finite path by one more step, but we can’t “take the limit,” so to speak, of this process to get an infinite path. This is the sort of thing that can happen when you don’t have any form of choice.

If the absence of leaves bothers you, you can enlarge the tree by attaching to each node a single child node with no successors. There will still be no infinite paths.

Posted by: Adam Stephanides on November 2, 2006 3:13 PM | Permalink | Reply to this

Re: Foundations

we can always extend any finite path by one more step

The specific requirement was: “Every path from the root terminates”. That flies directly in the face of this statement. If any finite path can be extended, then how can any be said to terminate?

Posted by: John Armstrong on November 2, 2006 4:17 PM | Permalink | Reply to this

Re: Foundations

we can always extend any finite path by one more step

The specific requirement was: “Every path from the root terminates”. That flies directly in the face of this statement. If any finite path can be extended, then how can any be said to terminate?

There is no contradiction. In this example, it is true that every path terminates and that no path terminates. That’s because there are no (maximal) paths!

There are, of course, plenty of partial paths (that is paths in the general sense without regard to whether they can be extended). However, there are no maximal paths (that is paths that cannot be extended).

(Note that a lot of people are using the word “path” on this thread to refer to partial paths, and that’s how I would use the word by default. However, the requirement “Every path from the root terminates” is obviously intended to apply only to maximal paths; for paths in general, it’s true only for the empty tree!)

Posted by: Toby Bartels on November 2, 2006 8:29 PM | Permalink | Reply to this

Re: Foundations

This feels incredibly like cheating. For one I don’t see how it’s “obvious” at all that “path” really means “maximal path”.

Posted by: John Armstrong on November 2, 2006 9:42 PM | Permalink | Reply to this

Re: Foundations

Requiring that every partial path be contained in some maximal path would do what you want. It is a consequence of choice that in every tree, every partial path is contained in some maximal path. You might be able to prove this result without choice if you restrict to trees with this property - but note how that changes the theorem!

Posted by: Kenny Easwaran on November 2, 2006 10:46 PM | Permalink | Reply to this

Re: Foundations

I don’t see how it’s “obvious” at all that “path” really means “maximal path”.

Because otherwise:

the requirement “Every path from the root terminates” […] for paths in general, it’s true only for the empty tree!

But Kenny (below) has a different interpretation by defining “terminates” to mean «is contained in a finite maximal path». Then we can take the requirement to refer to all (partial) paths, which (as Kenny points out) in principle changes the meaning of the theorem. (In particular, it makes Adam's first counterexample fail.)

However, Adam's second counterexample, using the trick of adding an extra (third) leaf to each node, still works.

Posted by: Toby Bartels on November 2, 2006 11:17 PM | Permalink | Reply to this

Re: Foundations

I must confess this thread is starting to seem like sophistry or trolling, but in the hope that it is a sincere pursuit of understanding, and that you aren’t working with some definition of tree which is incommensurate with mine, here is my simplest explanation of how König’s lemma can require choice, but what I’ll call the “Darn Useful Heuristic” (DUH for short) lemma does not.

Let F be a predicate meaning “is finite”. The form of König’s lemma is:
¬ F(tree) → ¬ F(branching) ∨ ¬ F(paths)

The form of the DUH lemma is:
F(branching) ∧ F(paths) → F(tree)

At first glance, the classical logicians among you will say that these are logically equivalent statements. However, you can also see that they are only equivalent using the law of the excluded middle. So if we are doing purely constructive proofs (otherwise why quibble about choice?), these two statements are NOT the same fact.

An important thing to note is that the premise of the DUH lemma introduces no infinite values. In contrast, König’s starts with an infinite premise, and has already disqualified itself from constructive proof.

Another interesting thing to note is that, even in purely constructive proofs, you can start with finite premises and end up with infinite conclusions (non-terminating proofs). So if you find a terminating proof of DUH (as I have shown) it is true, but you still had enough power prove that a proof will NOT terminate (though some proofs may not be able to terminate and you can’t prove that.)

So the very basic fact from computer science about one of the most studied mathematical structures in human history is true and constructive, even though the most common formulation of it “from the infinite end” is not constructively true.

Posted by: Marc Hamann on November 3, 2006 2:44 PM | Permalink | Reply to this

Re: Foundations

So if we are doing purely constructive proofs (otherwise why quibble about choice?)

Plenty of people trust the principle of excluded middle but not the full axiom of choice, going back at least to Russell & Whitehead (and possibly further, but I’m not sure if anybody ealier was this explicit). AC implies LEM, but not conversely.

An important thing to note is that the premise of the DUH lemma introduces no infinite values. In contrast, König’s starts with an infinite premise, and has already disqualified itself from constructive proof.

There are plenty of constructive proofs involving infinite sets. Furthermore, the DUH lemma makes reference to a tree not known (a priori) to be finite, so at the very least any proof of it must use principles that apply to infinite sets, lest the proof beg the question.

Another interesting thing to note is that, even in purely constructive proofs, you can start with finite premises and end up with infinite conclusions (non-terminating proofs). So if you find a terminating proof of DUH (as I have shown) it is true, but you still had enough power prove that a proof will NOT terminate (though some proofs may not be able to terminate and you can’t prove that.)

I have no idea what this paragraph means!

Anyway, the DUH lemma implies the principle of denumerable choice from finite sets, as I have just shown. That argument is perfectly constructive; that is, it doesn’t use the principle of excluded middle (nor any other form of the axiom of choice, nor other constructively suspect principles like impredicative definitions), although of course it requires an axiom of infinity to even state (so finitists would consider it meaningless, at least as it stands). I’m pretty sure that the proof of the converse is also constructive, but I’m not positive, since I haven’t written it out in detail. All the same, I think that we should understand things first using (possibly) classical logic, since this is probably more familiar to us all.

Let me emphasise one point: Any valid proof of the DUH lemma must use principles that apply to denumerable (as well as finite) sets. To assume that (the set of nodes of) the tree is finite is to assume the conclusion. One must allow for the possibility that the tree is infinite until one has shown otherwise.

Posted by: Toby Bartels on November 4, 2006 12:09 AM | Permalink | Reply to this

Re: Foundations

I have no idea what this paragraph means!

I will have to assume at this point that we are talking about some completely different notion of “tree”, “finite branching” or “finite path” or otherwise live in different mathematical universes.

I hope yours brings you useful insights and accomplishes for you what you want it to.

Posted by: Marc Hamann on November 4, 2006 1:27 AM | Permalink | Reply to this

Re: Foundations

Marc wrote:

I [Toby] wrote:

Marc wrote:

[something about non-terminating proofs]

I have no idea what this paragraph means!

I will have to assume at this point that we are talking about some completely different notion of “tree”, “finite branching” or “finite path” or otherwise live in different mathematical universes.

Well, my mathematical universe for this discussion has basically been ZF set theory, since that's the universe most familiar to mathematicians (at least when they get down to details, for the record) in the absence of the axiom of choice. But actually everything that I've said works perfectly well in a type-theoretic version, such as Zermelo type theory (and therefore internal to any Boolean topos) or even weaker, predicative type theories (categorically speaking, internal to a pretopos, more or less). When practical, I've also avoided (and at least noted my use of) the law of excluded middle; except where that appears, things could be formalised in CZF set theory or a Martin-Löf type theory (and internalised to any LCC pretopos).

Of course I don't make any specific reference to such formalisations, keeping things loose as mathematicians usually do (even without thinking about it). But for the record, those are formalisations that could be used. (Some parts of this thread did interpret the tree as the membership tree of a hereditarily well founded set, which can be formalised in type/category theory but is much nicer in set theory. But I didn't go there.)

In all of these contexts, proofs are necessarily finite things. I don't mind talking about non-terminating proofs, but I don't see the connection.

I have definitely required the set of finite sequences from a given infinite sequence of sets. If you don't believe in that, then you don't believe in Adam's counterexamples (at least not as I've spelt out the details). However, as long as accepting such a set is consistent with your universe (in the sense that there is a consistent formal system interpreting your universe together with that construction), then those counterexamples are still enough to show that the theorem cannot be proved without a choice principle.

If you're still interested: What is your universe?

Posted by: Toby Bartels on November 6, 2006 10:53 PM | Permalink | Reply to this

Re: Foundations

I wrote in part:

[T]he DUH lemma implies the principle of denumerable choice from finite sets, as I have just shown. That argument is perfectly constructive[.]

But that’s not right, since the form of the theorem that I used isn’t (constructively) equivalent (AFAICT) to the DUH Lemma. (I was so pleased to tell Marc that my proof was constructive that I neglected to notice that it did not prove what he wanted!) In fact, it was basically König’s Lemma, at least if you write König’s Lemma as I’ve most often seen it phrased:
F(branching) ∧ ¬ F(tree) → ¬ F(paths)
where ‘¬’ is taken in a strong sense (existence of an infinite counterexample).

However, the metamathematical argument still works, as follows:

Postulate. The principle of denumerable choice from finite sets (the ‘principle’) cannot be proved, even using LEM.

To verify the postulate is beyond the scope of this comment (because I don’t know enough metamathematics to do it), but can be found in references on set theory. Even the truth of the postulate, of course, depends on one’s formal system; but it is true for ZF and hence also for any weaker (intuitionistic, predicative, whatever) system.

Proposition 1. Using LEM, the DUH Lemma and König’s Lemma are equivalent.

Proposition 2. Using LEM, the weak form of the DUH Lemma (with the requirement that every path be contained in a maximal path) and the (similarly) weak form of König’s Lemma (‘the theorem’) are equivalent.

Proposition 3. The strong form of each lemma (from Proposition 1) implies the weak form of that lemma (from Proposition 2).

These Propositions are all immediate; note that Proposition 3 does not require LEM.

Theorem. The theorem implies the principle.

This is what I proved (without using LEM) in this comment (which was based on an example by Adam’s second counterexample).

Corollary. The DUH Lemma cannot be proved, even using LEM.

This is what you get by tossing all of the above together, in the style of Lewis Carroll, and seeing what pops out.

Now, an interesting variation on this question would be to use some system of reasoning (still constructive) that is not weaker than (but rather incomparable with) ZF, such as full-blown intuitionism (as practised by Brouwer and still studied in Nijmegen and elsewhere). In particular, Brouwer’s Fan Theorem is probably relevant. But you will need some additional assumptions, whatever they may be, to prove the DUH Lemma, or ‘the theorem’, or ‘the principle’.

Posted by: Toby Bartels on November 7, 2006 5:12 PM | Permalink | Reply to this

Re: Foundations

I was going to let sleeping dogs lie, Toby, but you have been so persistent in your interest in the problem I feel obliged explain where I’m coming from. ;-)

A very close reading of the Wikipedia article for the (graph theoretic) König’s Lemma has enough information to see where I’m coming from, but it requires being sensitive to certain unstated assumptions to see it.

In particular, note:

This issue cannot arise if the graph is assumed to be countable.

One thing to understand is that from a strict comptational constructive point of view, you can’t build ANY uncountable set at all.
But even in a system that admits uncountable sets, such as ZF, you would need choice to show that an uncountable TREE could exist. (Consider that the relation parent-of(x, y) establishes a complete partial order on the elements of the tree.)

Many of the set-theoretic axioms are like this: you only need them if you admit uncountable sets (or certain kinds of operations on countable sets that ultimately imply uncountable sets) and want to impose some additional structure on them.

To understand the objection to the “counter-example” that you and Adam were proposing, add to the previous assumption/theorem that uncountable trees are inadmissible the notion that “a tree has finite paths” implies for me that all paths are closed; if the path is not closed it would be infinite.

Another way to express my position that uncountable trees are inadmissible, and finite paths are closed is to say that for me trees are by definition discrete (all subsets are clopen). With a discrete structure, if you can’t expand infinitely horizontally and you can’t expand infinitely vertically, and there aren’t any other dimensions, where would the infinity be hiding?

Anyway, I hope my explanation of my position has been illuminating (if of nothing else, that foundations discussions are very tricky and have many hidden assumptions and consquences), and we will end up either agreeing or agreeing to disagree. ;-)

Posted by: Marc Hamann on November 7, 2006 9:34 PM | Permalink | Reply to this

Re: Foundations

One thing to understand is that from a strict comptational constructive point of view, you can’t build ANY uncountable set at all.

I don't really like this attitude, even for constructive mathematics intended for a computational interpretation, because IMO uncountable sets (like the set N^N of all infinite sequences of natural numbers) should sometimes be used as a type of arbitrary procedures (themselves not necessarily computable) coming as inputs to a computation from somewhere outside: a computer user, a scientific measurement, or some other oracle. Thus even in Markov's Russian school of recursive constructive mathematics (where it is taken as axiomatic that every element of N^N, and even every partial sequence, is recursive), still the set N^N exists (and can be proved uncountable by Cantor's diagonal argument).

But this is only a side remark; I'll put away my philosophical prejudices for now.

But even in a system that admits uncountable sets, such as ZF, you would need choice to show that an uncountable TREE could exist.

OK, I'll accept this. (I might quibble over the meaning of the word ‘tree’, but I don't think that this affects anything here.) However, just because you need choice to refute the claim that all trees are countable, that doesn't mean that you can prove that claim just because you don't accept choice.

In fact, if I understand your position correctly now, then you are using the following ‘additional assumption’ (as I put it last time): Every set (or at least every set that can be the set of nodes of a tree) is countable. Even better (again if I understand your position correctly), it ought to be a theorem (in a very stripped down constructive mathematics, with neither any axioms of choice nor any classically false axioms) that every countable tree satisfies the DUH Lemma.

So, with this proviso, I no longer believe that you are wrong. (That's good, right? $-_^$ ) In particular, in Adam's counterexample, given that the set of nodes is countable, we can enumerate them once and for all, then construct an infinite path (without any axiom of choice) by always picking the first regular child. In fact, if I'm not messing up, this actually shows that the principle of countability (if I may call it that) implies the principle of denumerable choice from finite sets. (And thus, the principle of countability and the principle of excluded middle together imply both the principle of countable choice from finite sets and König's Lemma.)

Actually, the only thing that I don't see yet is how the principle of countability implies the DUH Lemma! (I can prove it if I use excluded middle as well, since then it's equivalent to König's Lemma, but that's not very interesting.) I'm willing to take your word for it (especially since Wikipedia, in the form of Carl Mummert seems to confirm this), but I'd appreciate it if you could explain to me:

Given an enumeration of the nodes of a tree, finitely branching and with all paths finite, how do you (preferably without using any axiom of choice, but if necessary then using discrete choice from finite sets) construct an upper bound on the number of nodes? (In particular, you might explain why this program must terminate, in light of Kenny's response to it.)

Posted by: Toby Bartels on November 8, 2006 4:42 PM | Permalink | Reply to this

Re: Foundations

I don’t really like this attitude, even for constructive mathematics intended for a computational interpretation

If I want to model something that could actual be turned into a terminating program, I necessarily have to put such limitations on my proofs.

If I’m studying a mathematical principle in more general terms as a kind of theoretical upper bound on computational ideas, I will by all means use a more powerful mathematics. In such a case, though, I don’t shy away from using some kind of choice axiom… in for a penny, in for a pound. ;-)

However, just because you need choice to refute the claim that all trees are countable, that doesn’t mean that you can prove that claim just because you don’t accept choice.

From my point of view, I would say that what is really happening is that the actual content of the claim changes depending on what system it is formulated in.

This is actually an interesting philosophical point that would distinguish a mathematical Realist from a Constructivist or a Formalist (at least as verifiable proof-theoretic methodologies rather than as self-identifications. ;-) )

As a member of the latter camp (hybrid constructivist/formalist), I feel inherently that concepts that can’t be generated from my axioms are outside the realm of discourse for the proof. I’m comfortable that the objects picked out by the predicate infinite(x) is actually different in each case.

A mathematical Realist might take a different position and say “Uncountable sets are a real mathematical phenomenon, so it is reasonable to judge a system’s power with respect to it even if it inadmissible in that system, i.e. not already a consequence of the predefined axioms.”

I think one of the problems is that most people haven’t really thought about which of these they are: they just happen to be whichever. ;-)

Given an enumeration of the nodes of a tree, finitely branching and with all paths finite, how do you (preferably without using any axiom of choice, but if necessary then using discrete choice from finite sets) construct an upper bound on the number of nodes?

I’ve been trying to figure out the best way to present this given the limitations of the medium (and my spare time ;-) ), and the clearest approach I’ve come up with is to use a simple game semantics.

The game is between two people, Verifier and Falsifier.

Falsifier’s goal is to build an infinite tree with finite branching and finite paths. He starts with a countably infinite store of nodes to add to the tree and a pre-placed node, the root, that is coloured green.

Falsifier can add any finite number of children to a green node per turn, each of which will be introduced coloured red. At any time, Falsifier can choose to colour the current green node red, and make any other node in the tree green, thus opening that node for expansion. To generate a chain, he can successively shift the green marking to a child, add a new child and shift the green to that new child, etc.

So a green node represents a potentially infinite sub-tree, a “slot” either for infinite branching or an infinite path.

At any turn, Falsifier can claim victory and turn the tree over to Verifier, whose goal is to traverse the entire tree, rejecting the tree as not meeting the specification if he finds a green node, whereby he wins. If the Verifier’s traversal doesn’t terminate in a finite number of steps, he loses.

It becomes obvious that Falsifier can’t win, because on any turn n he can either colour the green node red and not add a new green one to meet the preconditions, thus shutting off the opportunity to add the rest of his infinite store or he can pass the tree back to Verifier with the green node still there, leaving the tree potentially infinite, but losing because he fails the preconditions.

You can see that even if we allow any finite number of nodes to be added per turn, and allow as many green nodes as you like at any turn, Verifier will STILL be able to accept or reject any tree in a finite number of steps for any turn n (a simple induction).

The only way that Falsifier could win is if he was allowed to add an infinite tree pre-coloured to red in one go, and of course that would be a petitio principii.

Posted by: Marc Hamann on November 8, 2006 8:05 PM | Permalink | Reply to this

Re: Foundations

This proof seems to implicitly assume that the game terminates in a finite number of steps: i.e., Falsifier can only make a finite number of moves. But of course, if Falsifier can only make a finite number of moves, and can only add a finite number of nodes at each move, then the final tree must be finite. To put it another way, if your proof were valid, it would still be valid without the assumption that each node has a finite number of children; but without this assumption the theorem is clearly false.

“The only way that Falsifier could win is if he was allowed to add an infinite tree pre-coloured to red in one go, and of course that would be a petitio principii.”

On the contrary, assuming that Falsifier can’t do this is the petitio principii, since that’s equivalent to the assertion you’re trying to prove. (If the objective were to prove that an infinite tree satisfying Armstrong’s conditions exists, then you’d be correct; but we already know that can’t be done in ZF, since it contradicts AC.)

Posted by: Adam Stephanides on November 12, 2006 8:44 PM | Permalink | Reply to this

Re: Foundations

This proof seems to implicitly assume that the game terminates in a finite number of steps: i.e., Falsifier can only make a finite number of moves.

No: this is a straightforward induction on N (which of course is infinite). Even if (especially if)we allow the game to go on for ever, Falsifier can never both meet the requirements for the tree and the contra-requirement that it is infinite. This works because each step is finitary, even if we admit infinite steps.

On the contrary, assuming that Falsifier can’t do this is the petitio principii, since that’s equivalent to the assertion you’re trying to prove.

I must respectfully disagree: the onus placed on each player is quite clear: it is falsifier’s job to build such a tree. Perhaps, if you are not familiar with game semantics or proof theory, this might be a bad formulation for convincing you. If that is so, my apologies; it meets my criteria for being convincing, and I can’t see how to make it more so.

Posted by: Marc Hamann on November 12, 2006 9:53 PM | Permalink | Reply to this

Re: Foundations

“Given an enumeration of the nodes of a tree, finitely branching and with all paths finite, how do you (preferably without using any axiom of choice, but if necessary then using discrete choice from finite sets) construct an upper bound on the number of nodes? (In particular, you might explain why this program must terminate, in light of Kenny’s response to it.)”

I think I can do this, actually. (That is, I know I have a proof, but I’m not completely sure it avoids LEM.) So, suppose we have a tree T with an enumeration, satisfying the conditions of DUH. (Actually, we only need to assume that the nodes of T can be totally ordered.) Construct a sequence of nodes of T as follows: a_0 is the root node r. If a_n has children not yet visited by the sequence, then a_(n+1) is the lowest-numbered of these. Otherwise a_(n+1) is the parent node of a_n, unless a_n = r, in which case the sequence terminates. Clearly, if the sequence terminates, then it’s a traversal of T and T is finite.

But in any case, we know that any node only appears a finite number of times: in fact, if it has n children it appears at most n+1 times. So we can construct another sequence as follows: b_0 = a_0 = r, and b_(n+1) is the node which immediately follows the last occurrence of the node b_n in the sequence of a’s, if one exists. Otherwise the sequence terminates at b_n.

At some point this sequence must terminate, since otherwise it would be an infinite path. Say it terminates at b_i. But by construction, this is only possible if the sequence of a’s also terminates at the node b_i (which therefore must equal a_0 = r). So the sequence of a’s terminates, and therefore is a traversal, and T is finite.

Posted by: Adam Stephanides on November 14, 2006 2:54 AM | Permalink | Reply to this

Re: Foundations

Thanks, Adam! I think that your argument here is probably essentially the same as the argument that Marc was making, but I understand yours better.

I’m pretty sure that your construction of the sequence (b_0, b_1, …) is legitimate (without any form of choice, note even LEM). Only the final step is problematic; you assume that since this sequence can’t be infinite, then it must be finite. This is an example of LEM, but (in this context) it follows from Markov’s Principle (MP), a (very) weak form of LEM accepted by (as the name implies) the Markovian school of constructivism (and also by at least one Brouwerian intuitionist).

Furthermore, it’s easy to see that DUH (applied to denumerable trees) implies Markov’s Principle: Given any infinite sequence of 0s and 1s that is not all 0s, form an unbranching tree whose nodes are all initial segments that consist of all 0s. Then DUH implies that this is finite, so the original sequence has at least one 1 (immediately following the final node) —and this is precisely what MP states.

So to Marc: I now agree that you are correct, given Markov’s Principle (which is classically true) and the Principle of Countability. So as far as I’m concerned, this thread may now die. $^_^$

Posted by: Toby Bartels on November 17, 2006 12:36 AM | Permalink | Reply to this

Re: Foundations

“Only the final step is problematic; you assume that since this sequence can’t be infinite, then it must be finite. This is an example of LEM”

Wouldn’t that depend upon whether the condition on paths is expressed positively,as “every path is finite,” or negatively,as “no path is infinite”? In Marc Hamann’s formulation, it’s expressed positively, although I phrased the step as if it were expressed negatively (not having much experience with constructive math).

“but (in this context) it follows from Markov’s Principle (MP), a (very weak form of LEM accepted by (as the name implies) the Markovian school of constructivism(and also by at least one Brouwerian intuitionist).

“Furthermore, it’s easy to see that DUH (applied to denumerable trees) implies Markov’s Principle: Given any infinite sequence of 0s and 1s that is not all 0s, form an unbranching tree whose nodes are all initial segments that consist of
all 0s. Then DUH implies that this is finite”

Again, it seems to me that this is true if the condition on paths is expressed negatively, but not if it’s expressed positively.

Posted by: Adam Stephanides on November 24, 2006 8:48 PM | Permalink | Reply to this

Re: Foundations

To be honest, I’m getting more confused the more that I look at this. To respond to you, I have to look precisely at the definition of path, which then seems to expose a flaw in your argument (that MP —if even this is necessary— implies DUH for countable trees), wich I can fix by looking precisely at the definition of tree, which then casts doubt on my argument (that DUH implies MP), and I get all turned around.

Suffice to say: * DUH definitely follows from MP and the Axiom of Countability (even if MP is not actually necessary) without requiring any other form of AC or EM; * the necessity of MP depends carefully on details of definitions that have so far been unstated.

Since Marc probably believes in MP anyway (at least, it seems pretty common among constructivists motivated by computability issues —going back to Markov himself), I’m not going to worry about it.

Posted by: Toby Bartels on November 25, 2006 12:19 AM | Permalink | Reply to this

Re: Foundations

$MathML-enabled post (click for more details).$

Maybe everyone’s getting caught up on “paths” and “trees” when that’s not how the question originally arose. To wit:

Consider a hereditarily finite set. That is, a finite set all of whose elements are hereditarily finite. Foundation tells us that we can’t find an infinite path $\{x_i\}_{i\in\mathbf Z}$ with $x_{i+1}\in x_i$ for all $i$ . The question is: are there only a finite number of elements “in” the set at all?

Posted by: John Armstrong on November 25, 2006 2:47 AM | Permalink | Reply to this

Re: Foundations

This is a different question than the one you originally asked, though: the Axiom of Foundation states that any non-empty set S has a member disjoint from S, and without AC this is stronger than the “no infinite descending membership chain” principle.

In fact, your present question can be answered affirmatively without AC. Let S be the given set. Suppose T(S), the transitive closure of S (that is, the set of all members of S, all members of members of S, all members of members of members of S, and so on), is infinite. Then let S’ be the subset of T(S) containing those elements whose transitive closures are themselves infinite. By the same argument as in the usual proof of Konig’s Lemma, the set {S} U S’ contains no element disjoint from itself, contradicting the Axiom of Foundation.

If, in your original question, you replace the “no infinite paths” condition with “every subset of nodes contains a node which is not the parent of any node in that subset,” then we can similarly prove that the tree is finite without using AC.

It’s also easy to prove that “hereditarily finite” is equivalent to “having finite transitive closure” by transfinite induction, where it’s the full Axiom of Foundation that ensures that transfinite induction works.

Posted by: Adam Stephanides on November 26, 2006 8:50 PM | Permalink | Reply to this

Re: Foundations

Okay, maybe it’s been so long that I need to go through the whole story again.

Dr. Zuckerman was considering hereditarily-finite sets, where he posed the strict question I just posted.

He phrased the question in terms of “trees” and “paths”, which are evidently slightly fuzzy terms.

I posted that form of the question to the board.

The whole discussion has ultimately come unhinged on different people’s interpretations of “trees” and “paths”, and what various statements about them mean.

So I’m suggesting we determine what “trees” and “paths” and all these other things should mean by going back to the real question behind everything else: the question about hereditarily-finite sets.

Posted by: John Armstrong on November 26, 2006 9:26 PM | Permalink | Reply to this

Re: Foundations

By the same argument as in the usual proof of Konig’s Lemma, the set {S} U S’ contains no element disjoint from itself, contradicting the Axiom of Foundation.

Also, doesn’t that argument require dependent choice?

Posted by: John Armstrong on November 26, 2006 9:33 PM | Permalink | Reply to this

Re: Foundations

It’s also easy to prove that “hereditarily finite” is equivalent to “having finite transitive closure” by transfinite induction, where it’s the full Axiom of Foundation that ensures that transfinite induction works.

This is the best way to look at Foundation, in my opinion: one can prove things about all sets by induction on the membership predicate. So to prove that all hereditarily finite sets have finite transitive closure, we need simply check that each finite set whose members all have finite transitive closure has finite transitive closure itself, which is easy. Conversely, to prove that every set with finite transitive closure is hereditarily finite, we need simply check that each set with finite transitive closure and only hereditarily finite members is hereditarily finite (which is even easier).

This form of Foundation is particularly important in constructive set theory; it is taken as an axiom schema in Peter Aczel’s system CZF. The statement that every occupied set has a minimal member is too strong, since it implies excluded middle (as is well known). On the other hand, the statement there exists no infinite decreasing sequence of membership is too weak, since it is a negation (and can therefore prove only other negations, by contradiction).

If we want this theorem (that hereditary finitness is equivalent to finite transitive closure) to work, we must be careful about what we mean by a finite set. There are two common definitions in constructive mathematics, neither of which quite works: * A set is Bishop-finite if it is (in bijective correspondence with) the set of natural numbers less than n for some fixed natural number n (possibly n := 0, of course). * A set is Kuratowski-finite if it is (in bijective correspondence with) a quotient of a Bishop-finite set.

I will add one more definition: * A set is Stephanides-finite (invented purely for the purposes of this discussion, but sometimes called ‘subfinite’) if it is (in bijective correspondence with) a subset of a Kuratowski-finite set.

We need Stephanides-finite sets here. (Obviously, there is one other definition possible: a subset of a Bishop-finite set. But that won’t work either.) Depending on Zuckermann’s purposes, this may be good, bad, or (most likely) irrelevant.

Posted by: Toby Bartels on November 28, 2006 3:05 AM | Permalink | Reply to this

Re: Foundations

I wrote in part:

We need Stephanides-finite sets here.

Hum, actually, I’m not sure that I can prove the union of S-finitely many S-finite sets is S-finite. (It seems obvious, but it isn’t, at least not to me.) So I’m not sure that I can prove that a hereditarily S-finite set has S-finite transitive closure. (But I can definitely prove the converse; given the inductive step, I just need that a subset of an S-finite set is S-finite, which is easy.)

Probably nobody cares about this except me and (perhaps) Marc.

Posted by: Toby Bartels on November 28, 2006 4:47 PM | Permalink | Reply to this

Re: Foundations

“A set is Kuratowski-finite if it is (in bijective correspondence with) a quotient of a Bishop-finite set.”

I can see why Bishop-finiteness won’t work, but not why Kuratowski-finiteness won’t work. Suppose S is a K finite set, and let S’ be the union of S. Then there’s a surjective function f:{1, … , n} -> S, and for each 1<=i<=n a surjective function g_i:{1, … , n_i} -> f(i). What stops us from constructing a surjective function f’:{1, … , (sum(1<=i<= n)n_i)} -> S’ in the obvious way?

Posted by: Adam Stephanides on November 29, 2006 9:23 PM | Permalink | Reply to this

Re: Foundations

I can see why Bishop-finiteness won’t work, but not why Kuratowski-finiteness won’t work.

It works one way: A hereditarily K-finite set has K-finite transitive closure. But (as far I can tell) it won’t work the other way: I can’t prove that a set with K-finite transitive closure is hereditarily K-finite. (If fact, I thought that I had a weak counterexample, but now I’m not sure what it is, so I may yet be confused.)

In contrast, S-finiteness works the other way, but not (as far as I can tell, and in contrast to what I thought at first) the one way. I don’t know if that means anything!

Note that it would probably be best if K-finiteness did work; that seems to be best all-round notion of finiteness.

Posted by: Toby Bartels on November 30, 2006 7:51 PM | Permalink | Reply to this

Re: Foundations

Now you have me curious, though. What was the flaw in my argument that could be fixed by looking closely at the definition of “tree”?

Posted by: Adam Stephanides on November 25, 2006 9:51 PM | Permalink | Reply to this

Re: Foundations

What was the flaw in my argument that could be fixed by looking closely at the definition of “tree”?

I was worried about this line:

b(n+1) is the node which immediately follows the last occurrence of the node bn in the sequence of a’s, if one exists. Otherwise the sequence terminates at b_n.

In general, whether such a last occurrence exists is undecidable. But depending on what one means by path, and whether it’s enough to show directly that a path is finite or simply that a path is not infinite (so that finiteness might follow by MP), then this might not be a problem.

I don’t think that I want to ponder this carefully any more, but you can see that the details matter.

Posted by: Toby Bartels on November 30, 2006 7:59 PM | Permalink | Reply to this

Re: Foundations

I’d assumed this thread had died, but I revisit after about a week and find it’s come back to life. So I’ll again try to explain myself.

“But even in a system that admits uncountable sets, such as ZF, you would need choice to show that an uncountable TREE could exist.”

While this is a side issue, I think this is wrong. Simply let the non-root vertices of the tree be the real numbers, with each real number a direct child of the root.

“To understand the objection to the counter-example that you and Adam were proposing, add to the previous assumption/theorem that uncountable trees are inadmissible the notion that “a tree has finite paths” implies for me that all paths are closed; if the path is not closed it would be infinite.”

Okay, you’re apparently using “paths” to mean maximal paths (the Wikipedia article Toby linked to does the same, so perhaps this is standard usage). But both my counterexamples still satisfy this assumption: in the case of the first one, because there are no paths, as Toby pointed out.

“With a discrete structure, if you can’t expand infinitely horizontally and you can’t expand infinitely vertically, and there aren’t any other dimensions, where would the infinity be hiding?”

With the words “if you can’t expand infinitely vertically,” you’re again assuming that if every branch is finite, there is an n such that every branch has length at most n. I’ll try and explain why I think this is an illegitimate move. All your and John Armstrong’s proofs, it seems to me, depend on one of the following assertions:

1) Every tree satisfying John Armstrong’s assumptions (call such a tree a JA-tree) has a finite number of branches. (Taking “branch” to mean what I would have called a not-necessarily-maximal path.)

2) For every JA-tree there is an n such that every branch has length at most n.

(Your proof here requires one of these two propositions to ensure that the traversal terminates.)

Clearly, from either of these assertions the DUH-lemma follows. But in order to produce a valid proof of the DUH-lemma, you need to either prove 1) without assuming 2), or prove 2) without assuming 1), and as far as I can see you haven’t done this.

Posted by: Adam Stephanides on November 12, 2006 8:43 PM | Permalink | Reply to this

Re: Foundations

Whoa, this thread won’t die. ;-) I do think these are interesting issues though…

While this is a side issue, I think this is wrong. Simply let the non-root vertices of the tree be the real numbers, with each real number a direct child of the root.

You’re right: there is the additional assumption of finite branching there.
If we admit infinitely branching nodes, your construction would work in ZF: as soon the node is finitely branching, you would need some sort of choice to choose the next batch of children. I should have clarified my statement.

As to not accepting any of my proofs, I’ve run out of proof tricks. You seem to believe in infinite trees with no paths, which doesn’t make sense within my definition of a tree; I’m not sure how to bridge that gap.

Posted by: Marc Hamann on November 12, 2006 9:39 PM | Permalink | Reply to this

Re: Foundations

But Kenny (below) has a different interpretation by defining “terminates” to mean “is contained in a finite maximal path”

And I think that’s the answer. Interpreting “terminates” to mean “is contained in a finite maximal” means that on the trees which satisfy the hypotheses, choice does hold. We don’t need to use AC in general because our hypothesis says it works in the cases under consideration.

Posted by: John Armstrong on November 3, 2006 4:53 PM | Permalink | Reply to this

Re: Foundations

Interpreting “terminates” to mean “is contained in a finite maximal” means that on the trees which satisfy the hypotheses, choice does hold.

This is wrong. Choice is not a statement about trees, and the mere fact that one consequence of choice (that every path is contained in a maximal path) holds for a tree does not prove that every other consequence of choice holds for that tree.

In particular, consider Adam’s second counterexample here. In full: Let (S₀, S₁, S₂, …) be a sequence of finite, occupied sets. Recursively define a tree whose nodes are finite sequences; each node will either be regular or exceptional.
* The root (the 0th-level node) is the empty sequence.
* A child of a regular nth-level node X is any sequence of the form X * (x) where x belongs to the disjoint union S_n + 1 (where 1 is your favourite singleton):
** this child is regular if x is taken from S_n;
** this child is exceptional if x is taken from 1.
* Exceptional nodes have no children.

Now every finite path has a maximal finite extension: if the path ends in an exceptional node, then it is already finite; if it ends in a regular node, then extend it by that node’s exceptional child.

An infinite path in this tree consists entirely of regular nodes; it determines precisely a choice function for the original sequence of sets. Therefore, the statement to be proved (‘the theorem’) implies that every such sequence has a choice function, which is the principle of denumerable choice from finite sets (‘the principle’). Of course, to prove that the principle is independent of, say, ZF set theory requires some metamathematical work.

We’ve already seen that the principle proves the theorem; thus the theorem is equivalent to the principle. According to Wikipedia, this equivalence is an exercise in:
* A. Levy. Basic Set Theory (Springer 1979, reprint Dover 2002).
However, I haven’t checked that reference. (Also, presumably it applies to the case where we merely assume that every path is finite, so you shouldn’t trust that citation as an argument by authority anyway.)

Posted by: Toby Bartels on November 3, 2006 11:48 PM | Permalink | Reply to this

Re: Foundations

The Axiom of Choice by Thomas Jech lists a large number of results which require some version of the Axiom of Choice (presumably including Konig’s Lemma), and also discusses the relationships among various weaker forms of the Axiom of Choice. Unfortunately it seems to be out of print.

Posted by: Adam Stephanides on November 4, 2006 2:27 AM | Permalink | Reply to this

Re: Foundations

This is wrong. Choice is not a statement about trees, and the mere fact that one consequence of choice (that every path is contained in a maximal path) holds for a tree does not prove that every other consequence of choice holds for that tree.

I’m sorry, I was a bit terse. I didn’t mean that every invocation of choice would work, but rather…

You know what, I don’t care that much anymore. If I’m going to get yelled at because I don’t quite see things as clearly as you do, I have better things to do with my time.

Posted by: John Armstrong on November 4, 2006 1:24 PM | Permalink | Reply to this

Re: Foundations

If I’m going to get yelled at because I don’t quite see things as clearly as you do, I have better things to do with my time.

I didn’t mean to yell, although I probably shouldn’t have emphasised the word ‘wrong’. Back in the day, one shouted online using ALL CAPS. But that’s so frowned upon now, perhaps the only way to yell is with emphasis. So now perhaps one can no longer emphasise: an example of the euphemism treadmill?

I meant to make a strong statement: that the question of whether the theorem requires some form of choice is not a matter of speculation, nor dependent on other foundational niceties, nor something that I was merely pretty confident of. Rather, I assert it as a proved mathematical fact (with all the strength that implies), and went on to spell out the proof in detail. (This is in contrast to my first statement, referencing König’s Lemma, which I was indeed merely pretty confident of.)

I don’t mind if you don’t want to talk about it anymore; I’m sure that we all have better things to do. But I’m not trying to upset you, and I’m sorry that I did.

Posted by: Toby Bartels on November 6, 2006 11:08 PM | Permalink | Reply to this

Re: Foundations

$MathML-enabled post (click for more details).$

I have a question.

(It doesn’t materially affect the argument, it’s just something I was wondering about.)

Toby Bartels wrote:

Let $(S_0,S_1,S_2,...)$ be a sequence of finite, occupied sets.

[Constructs tree of sequences of members of $S_i$ .]

I presume by occupied you mean non-empty?

Don’t you actually require that (at least an infinite subset of) these sets should have more than one member? If each set has only one member (with at most a finite number of exceptions) then there’s no choice to be made, so no need to invoke the Axiom of Choice. Or have I misunderstood AC?

Posted by: Tim Silverman on November 4, 2006 1:54 PM | Permalink | Reply to this

Re: Foundations

I presume by occupied you mean non-empty?

Yeah, it’s a term that I picked up from constructive set theorists (since without excluded middle, being occupied —having at least one element— is stronger than merely not being empty). Since I was about to remark in another comment that my proof was constructive, this could make a difference. But regardless of that, I think that the word ‘occupied’ suggests a more active mood (as constructivists’ language often does), in this case emphasising why the axiom of choice seems so natural (each set is occupied, we’re given that it has an element/occupant, so of course I can choose one!). Sometimes I forget that other people don’t always know the term.

Don’t you actually require that (at least an infinite subset of) these sets should have more than one member? If each set has only one member (with at most a finite number of exceptions) then there’s no choice to be made, so no need to invoke the Axiom of Choice. Or have I misunderstood AC?

I think that perhaps you’re misunderstanding the purpose of such a principle. Of course there are myriad situations where the principle is unnecessary; you’ve correctly identified one. [*] However, I don’t need, or want, to laboriously spell out that none of them apply. I merely consider the most general situation (relevant to the principle that I’m trying to prove) and show that if the theorem applies to arbitrary such, then so does the principle.

[*] (For another example, of a very different flavour, of such a situation, perhaps the sets S_i are all subsets of some fixed set S, perhaps even the set of natural numbers. Then they could all be ordered at once, and no axiom of choice is required.)

Or to put it another way: I prove (using the theorem about trees) that something is true for every infinite sequence of occupied, finite sets (to wit, that it has a choice function). Then of course it follows that this thing is true of every infinite sequence of occupied, finite sets that satisfies certain extra conditions (such that infinitely many of the sets has more than one element). Whatever conditions you might want to impose on the sequence, you get a relevant corollary free. But my proof covers the most general case: any infinite sequence of occupied, finite sets.

Posted by: Toby Bartels on November 6, 2006 11:35 PM | Permalink | Reply to this

Re: Foundations

“For another example, of a very different flavour, of such a situation, perhaps the sets Si are all subsets of some fixed set S, perhaps even the set of natural numbers. Then they could all be ordered at once, and no axiom of choice is required.”

Just a minor correction, or perhaps elaboration: this is true when S is a totally ordered set, but not for arbitrary sets, because the proposition “every set can be linearly ordered” can’t be proved without some form of the Axiom of Choice. In fact, it implies the Axiom of Choice for sets of finite sets.

Posted by: Adam Stephanides on November 14, 2006 2:26 AM | Permalink | Reply to this

Re: Foundations

All this suggests we should adopt a flexible attitude towards axiom systems: instead of believing in one and regarding its consequences as true, we should think of each extra axiom as giving us extra powers, and pay some attention to what each extra power lets us do. Even if we don’t “really” have these extra powers in general, we may have them in certain circumstances.

I call this attitude mathematical pluralism. (Compare logical pluralism.) I’m interested in Bishop-style constructivism because (to a large extent) it can serve as a neutral common ground for many different sorts of mathematics. The metamathematics of this is already largely understood; we know (more or less) the correspondence between dependent type theory (syntax) and LCC pretopoi (semantics), and we know how to strengthen this by adding such features as impredicativity, infinity, and forms of the axiom of choice (such as excluded middle, enough projectives, etc). Heck, we even know how to turn these category-theoretic models into membership-tree models for the old-fashioned set theorists! (By “we”, incidentally, I don’t mean me personally, except in broad outline.)

However, what I’d really like to see is a variety of interconnected research programmes studying many different, stronger kinds of mathematics. One research programme (based on impredicative definitions, a moderate axiom of infinite universes, and the full axiom of choice) is well advanced: it’s the programme of classical mathematics. But other research programmes should be based on the axiom of determinacy, or Brouwerian continuity principles, or some other useful axioms, together with only weak forms of choice. Instead, the situation is much more fragmented, and you must be a real kook (or just a logician) to consider the consequences of any one of these axioms.

Even more personally, I’d like to see a research programme in analysis based on the axiom determinacy, a suitable general form of Brouwerian continuity, and enough projectives, but with (necessarily) no excluded middle. For various reasons, I think that this ought to be very beatiful and powerful. But I can’t imagine who would work on it!

Posted by: Toby Bartels on October 31, 2006 12:30 AM | Permalink | Reply to this

Re: Foundations

Mathematicians in the area of set theory works on a lot of different models for mathematics. Sometimes the theory is more powerful with less axioms. For example, if you give up CH and the generalized CH you recover a very nice arithmetic for infinite cardinals. And as mentioned above there are all sort of axioms regarding very very large cardinals. I suppose mathematical logicians will be skeptical about novice suggestions on what axioms to give up just like “professionals” in other areas.

Posted by: gina on October 31, 2006 1:09 AM | Permalink | Reply to this

Re: Foundations

Interesting. Presumably if your ideas were taken up, you’d agree that there would be no particular need for this to be the work of someone with a philosophical training. Strong ideas about which systems attract them, perhaps a good knowledge of the history of earlier foundational work, but no need to have studied philosophy, beyond what every educated person should have. I think philosophers’ work lies elsewhere.

Posted by: David Corfield on October 31, 2006 9:29 AM | Permalink | Reply to this

Re: Foundations

If mathematical algorithms are now being patented, we may come to a situation where constructive proofs become potentially valuable where non-constructive proofs do not.

Posted by: David Corfield on November 7, 2006 8:35 AM | Permalink | Reply to this

Re: Foundations

I was in a little debate over on Shtetl-Optimized (which I would link to if I knew how) a few weeks ago about the role of the axiom of choice in algebraic geometry.

My point was that of course you don’t need the axiom of choice in algebraic geometry—it’s just polynomials we’re talking about! Then my opponent went about bringing up a whole list of things that I hadn’t even considered, so I had to declare defeat.

Nevertheless, even though today’s foundations of algebraic geometry do require the axiom of choice very seriously (you need the existence of prime ideals in rings, otherwise Spec R could be the empty set), I believe this is essentially for historical reasons. When Grothendieck began EGA, point set topology was the only option, so that’s what he used. But after SGA 4, it was probably clear to lots of people that topos theory would be a much better foundation for algebraic geometry.

It’s too bad no one has pursued this. Even if you don’t care about the axiom of choice itself, I think it would be really fascinating to see what new concepts you would invent by being forced to do without it. You would have to throw away many old friends (first would be the underlying point set of a space), but the new ones would be better—topos theory itself could have been invented as a result of trying to do topology without point sets. I have no doubt that this would ultimately be successful, simply because algebraic geometry really is just about finite sets of polynomials in finitely many variables. How could you ever need the axiom of choice for something like that?

But I also agree that it is best to have a pluralistic approach. Sometimes I don’t want to sweat the constructive details, but sometimes I want to do something more real. I think choice-dependent theories should be thought of as perfectly respectable first drafts of theories. And Cohen tells us that, like those who believe in gods, we never have to worry about any new contradictions. On the other hand, eliminating choice should also be seen as respectable, by making the theological real.

But if your whole subject really does depend on choice, then I believe you have some soul searching to do…

Posted by: James on October 31, 2006 8:55 AM | Permalink | Reply to this

Re: Foundations

“Something that has long troubled me is the question of why philosophers have shown what to my mind is an unwarranted interest in foundational mathematical theories which make little or no contact with mainstream mathematics.”

What precisely do you refer to, David? (Also what do you refer to by “disconnected theories”?) As a matter of fact I was always puzzled why philosophers are so interested with mathematics to start with. Perhaps the reasons for philosophers’ interest in mathematics do not apply to modern “mainstream mathematics”. Pushing this idea one step further one can speculate whether the reasons for society’s interest in mathematics really extend to modern/mainstream mathematics.

Unlike set theory and some logic that we hear a lot about in college mathematics, category theory is something which is absent from the curriculum. It looks that John and others promote the case for category theory (and n-categories) as foundational objects that should interest mathematicians, philosophers, and even computer scientists(!). I would be happy to see the case for category theory made in an explicit, clear and non-technical way. Why should philosophers be interested in category theory? Why should computer scientists be? and why should mathematicians (who are not already interested) be? David, do you see, as you hinted, how category theory can help getting “casual ordering of concepts right? (I regard the idea of getting the causal ordering of [mathematical] concepts right as romantic, while highly unrealistic. Like other romantic ideas it could lead to interesting discussions.)

Posted by: Gina on October 30, 2006 7:12 PM | Permalink | Reply to this

Re: Foundations

Gina asks why computer scientists should be interested in category theory. That’s a good question. I should answer it sometime, in a nontechnical way. This thread is not the right place.

For now, I just want to note that computer scientists are interested in category theory. They don’t need any convincing. There are lots of conferences on categories and computer science, like this and this. And, there are lots of books and review articles. So, there’s no need for any categorical proselytizing, at least in computer science. The train is already rolling. Here at the n-Category Café we can just jump on!

Posted by: John Baez on October 30, 2006 7:38 PM | Permalink | Reply to this

Re: Foundations

Philosophers have had many and diverse reasons to be interested in mathematics. For many centuries there was no other intricate body of knowledge. In the early modern period, its manifestation in the physical world was taken as a sign of God’s hand. Later it became a battleground for those who believed we had innate knowledge and those who did not. Around 1900 it became a test case for whether any knowledge can be known with certainty. In recent decades, it’s become a cause of trouble for Anglo-American analytic philosophers. For many, their theories of knowledge require causal contact to be made with the objects of knowledge. Perhaps then mathematics is just a form of logic, and so true by virtue of meaning, or perhaps its just a convenient fiction.

As for me, I find mathematics of philosophical interest for many reasons. Four millennia ago people were solving what we’d take to be quadratic equations for their positive roots. What is it that has allowed “one of mankind’s longest conversations” (Mazur)? Where some philosophers take the starting point of a theory of knowledge to be ‘what does it mean for X to know p’ (where p might as well be ‘2 + 2 = 4’), I take its starting points to be ‘how does our knowledge grow?’, ‘what are the conditions for a tradition of enquiry (such as mathematics) to flourish?’.

You can read my ideas for what a philosophical treatment could be here, which gives access to recent papers, my old blog, an excerpt from my book, etc.

You sound sceptical of ‘causal’ talk in mathematics. For Aristotle, the only causes at stake in mathematics are formal ones. I don’t think it amounts to much more than the idea that it’s possible to organise a field objectively. The final sentence of Manin’s quotation in the post may give the impression that although foundations in his sense is relevant to working mathematicians, they need not trouble themselves to contribute to it. Manin goes on in the article to take our favourite n-categories as the emerging foundations, so the prospective best language available to organise mathematics. Presumably we wouldn’t want to see a sharp division of labour in place here. The following quotation from Lawvere wouldn’t admit any interpretation of foundations as being detached from everyday practice:

In my own education I was fortunate to have two teachers who used the term “foundations” in a common-sense way (rather than in the speculative way of the Bolzano-Frege-Peano-Russell tradition). This way is exemplified by their work in Foundations of Algebraic Topology, published in 1952 by Eilenberg (with Steenrod), and The Mechanical Foundations of Elasticity and Fluid Mechanics, published in the same year by Truesdell. The orientation of these works seemed to be “concentrate the essence of practice and in turn use the result to guide practice”. (Lawvere W., ‘Foundations and applications: axiomatization and education,’ Bulletin of Symbolic Logic 9 (2003), 213-224. Also available here).

Posted by: David Corfield on October 31, 2006 10:35 AM | Permalink | Reply to this

Re: Foundations

“You sound sceptical of ‘causal’ talk in mathematics.”

I am skeptical about one linear order for all mathematical facts, as well as a unique concept of “correct” cause. Casual talks of causality are great.

“For Aristotle, the only causes at stake in mathematics are formal ones.”

In some sense, from a purely logical sense “modes ponens” is the only form of causality. (Provocatively stated you can say that from the point of view of logic there is only one trick.)

A concept related to causality coming from computer science is some complexity notion invented by Cristos Papadimitrious. Described provocatively Papadimitrious claims that from the point of view of computational complexity in all of mathematics there are essentially only five tricks. Every proof can be regarded (from the point of view of computational complexity) just as applying one or more of these five tricks.

(Perhaps, as some participants already remarked, modern computer science being an emerging new discipline can offer a lot to philosophers.)

Posted by: Gina on October 31, 2006 7:39 PM | Permalink | Reply to this

Re: Foundations

As a matter of fact I was always puzzled why philosophers are so interested with mathematics to start with. Perhaps the reasons for philosophers’ interest in mathematics do not apply to modern “mainstream mathematics”.

As a matter of fact, several philosophers I’ve talked to about this stuff have suggested a motivation very much like this one. Logic has clear philosophical relevance, as does our knowledge of logic.

The case for basic arithmetic being of philosophical interest is only slightly more tricky. The notion of ontological commitment is extremely important in analytic metaphysics. When I say “the number of planets is 8”, there’s a question of whether I’m just committing myself to some planets, or to a number as well. Frege (and some recent others) have wanted to show that this commitment actually comes already from logic and some constitutive principles about what “number” means, so that it isn’t really a problem for metaphysics.

But many philosophers are skeptical about whether areas of mathematics beyond logic and basic arithmetic are actually of general philosophical interest. They’ll admit that they should be of interest to at least some philosophers of mathematics, but it was once said to me, “will the philosophy of mathematics just become like philosophy of chemistry if you spend all your time engaging those issues” rather than focusing on the “really philosophically interesting” topics of logic and arithmetic.

Posted by: Kenny Easwaran on October 31, 2006 7:04 PM | Permalink | Reply to this

Re: Foundations

So where are you on this, Kenny? My MacIntyrean conception of a theory of knowledge leads me into the thick of mathematics. My MacIntyrean-Collingwoodian conception of metaphysics as the study of first principles/absolute presuppositions leads me there too. But I have the sense that you’re far happier with analytic conceptions of epistemology and metaphysics of the post-Quine era. So how do you respond to the doubters you mention in your last sentence?

Posted by: David Corfield on October 31, 2006 7:49 PM | Permalink | Reply to this

Re: Foundations

I haven’t quite figured out what I think about this stuff yet. At least in part, this is because I think philosophy of any technical area (like philosophy of chemistry) has the potential for shedding important light on questions of philosophical interest to most philosophers. But it’s true, most of it will be focusing on technical work that isn’t directly relevant. Coming up with one’s philosophy of mathematics just from logic and basic arithmetic will surely leave out important parts of the picture. But it’s true that those are the only areas that most philosophers need to directly care about in their own work.

As a naturalist I want to understand a scientific practice in as close a way to how the scientists themselves do as possible. But I can’t do this for most sciences, and I don’t expect most philosophers to do this for mathematics.

Posted by: Kenny Easwaran on November 2, 2006 10:59 PM | Permalink | Reply to this

Re: Foundations

Kenny Easwaran wrote:

[…] it was once said to me, “will the philosophy of mathematics just become like philosophy of chemistry if you spend all your time engaging those issues” rather than focusing on the “really philosophically interesting” topics of logic and arithmetic.

So the person who said this was counting on you to agree that chemistry was not very interesting for philosophers, eh? Which branches of knowledge are considered worthy of a philosopher’s interest in this person’s view? Physics? Biology? Psychology? Sociology? Not chemistry, apparently. How about ornithology?

Is there a hierarchy of prestige at work here, based on the level of abstraction or something?

Somehow the thought of this makes me a bit grumpy. I don’t like the idea that only high-falutin’ lofty stuff is worthy of deep contemplation. If you can see the universe in a grain of sand, why not in mineralogy?

Posted by: John Baez on November 12, 2006 6:37 AM | Permalink | Reply to this

Re: Foundations

I’ve never understood a principled basis for what is counted ‘in’ by analytic philosophers. Would those for whom philosophy of chemistry is decidedly uninteresting think the same of philosophy of physics? If not, would they favour all philosophy of physics, including the 202 page work on Algebraic Quantum Field Theory by Princeton philosopher Hans Halvorson mentioned here?

For some musings about why we should get to feel at home in various practices, see here.

Posted by: David Corfield on November 12, 2006 3:11 PM | Permalink | Reply to this

Re: Foundations

So chemistry can be interesting!

Posted by: David Corfield on November 15, 2006 2:05 PM | Permalink | Reply to this

Re: Foundations

$MathML-enabled post (click for more details).$

I assume you’re being somewhere between middling and extremely ironic - it’s tough to gauge you Brits. While that paper on the periodic table is fun, I think there are much more deeply interesting things for philosophers to ponder about chemistry.

For example: the definition of an “acid”. Having studied pH in school, you may think that the concepts of “acid” and “base” are completely worked out and uncontroversial. Far from it! There are at least three common definitions of an acid. First there’s the Arrhenius definition: an acid is a hydrogen donor, or more precisely a substance that increases the concentration of hydronium ions (H₃O⁺) in a water solution. This is probably the one I learned in school. Later came the Brønsted–Lowry definition, and then the Lewis definition.

It’s a subtle and interesting business - and the really interesting part, which it would take a philosopher to unravel, is figuring out which methods the chemists are using to decide which definition is “right”!

One quickly gets into questions related to the concept of “natural kind” - perhaps “natural quality” is the right word here. Chemists seem to start with an intuitive notion of acid and base: an acid is sour, a base is the opposite. It’s an extremely useful notion! (Why?) But when we try to apply it to increasingly general situations, it gets harder and harder to make precise. What counts as an acid when you’re talking about chemicals dissolved in molten gold? At what point, if any, should one give up on extending this notion?

Chemistry is supposed to reduce to physics, so as soon as you know the underlying physics, there’s some sense in which it shouldn’t matter which extra definitions you introduces - the stuff will do what it does regardless! But, as with any subject, chemistry turns out to have a “tao”: a “grain” like wood that makes it easy to think in certain directions and hard in others. Concepts like “acid” and “base” seem to naturally impose themselves on our thinking. But, they only work well in limited contexts… and these limited contexts have fuzzy edges.

And if you think “acid” is hard to define, just try to define the concept of “chemical bond”!

In short, chemistry is both complicated enough, but also simple and clear enough - with one foot in tradition, another in experiment, and a third in theory - to make a great test case for pondering a lot of issues. Math is also great, but chemistry is different: it’s more concrete, more specific, less a matter of pure thought.

Nobody would have thought of “organic compounds” had not they been there. Nobody would have thought of calcium carbonate, either. Nobody would have gotten themselves into the mess of having to decide if calcium carbonate is an organic compound… had not the world pushed us into it.

Posted by: John Baez on November 16, 2006 8:03 AM | Permalink | Reply to this

Re: Foundations

it’s tough to gauge you Brits.

It was more like middling to slightly ironic. Do you have a range of emoticons to express different shades of irony?

Philosophers of chemistry have often struck me as an embattled lot, having to spend much of their time fending off reductionism to physics, while not feeling as glamorous as their counterparts in biology. But as you point out there are many fascinating questions to consider. In the paper I referred to, think what one could do with:

In spite of presently having more than 700 periodic tables (Mazurs, 1974), these are not new descriptions of the chemical elements or their behaviour. They are just different representations of the same phenomena, different shadows of the same object - the Periodic Law.

How to understand the two uses of ‘same’? If my preferred style of philosophy came to pass, the treatment of ‘sameness’ conditions in different disciplines would certainly be taken to be interesting.

Posted by: David Corfield on November 16, 2006 8:27 AM | Permalink | Reply to this

Re: Foundations

$MathML-enabled post (click for more details).$

David wrote:

To return to the philosophers, is their interest in disconnected theories just a vestige of earlier failed foundationalist projects, or is there a continuing rationale?

I think the philosophers focus on foundations because that’s what they know something about. Zilber’s work on Schanuel’s conjecture really cool. But, the fraction of really cool mathematics that explicitly invokes foundational issues is very small. It should not command as much attention among philosophers as it does.

By the way, I’m not sure I’d say earlier foundationalist projects “failed”. In a practical sense, the foundational work of Frege, Russell, Hilbert, Zermelo, Fraenkel and others succeeded in making most mathematicians feel the problem of foundations is completely settled, and thus utterly dull. In math, when a problem is solved, and it doesn’t suggest more interesting problems, it becomes boring.

However, there’s another sense in which Zermelo-Fraenkel set theory did not settle the problem of foundations. For those who understand him, Lawvere has made it very clear that there are much better foundations for mathematics. The main reason mathematicians stick with Zermelo-Fraenkel set theory is laziness. Having suffered through a course on set theory, or maybe just having heard that something called ZFC settles all foundational problems, most mathematicians don’t have the energy to investigate further.

That’s okay - for most mathematicians. Philosophers with a foundational bent really should dig deeper. But, this requires catching up with what mathematicians and computer scientists did during the 20th century. This may be a bit scary, since the very first step is to go beyond classical Aristotelian logic!

As Toby nicely explained:

Speaking more polemically, classical logic (in the strictest sense) is uninteresting. Its ramifications were fully understood by early 20th century, with the general idea of Boolean algebra. All further research in pure logic, therefore, had to be about something else. This explains why logicians talk so much about non-classical logics (intuitionistic, quantum, etc), quite apart from (and even if they have no interest in) the practical questions that led people like Brouwer and von Neumann to use them.

Posted by: John Baez on October 30, 2006 7:20 PM | Permalink | Reply to this

Re: Foundations

I think the cool side about mathematical logic is that while its birth was towards foundational issues and the pick of its success was to show that the foundations of mathematics are shaky, it became applied mathematics. Mathematical logic was and is very important for computers and perhaps the primary mathematical theory for computer science. (I am not so sure about category theory yet…)

Mathematical logic grew to become a deep and interesting area of mathematics. It has some but not many connections to other areas of mathematics and not many connections to philosophy any more. (Although the Journal of Symbolic Logic and the Society running it suppose to bridge mathematicians and philosopheres.)

It looks that mathematical logic and category theory are two very different viewpoints on the foundation of mathematics but it is not clear to me what is the basic conceptual difference. Historically, mathematical logic was created as the foundation of mathematics as a whole, and category theory started as laying the foundation of a rather specific issue and then grew and developed immensly.

Posted by: Gina on October 30, 2006 11:22 PM | Permalink | Reply to this

Re: Foundations

For those who understand him, Lawvere has made it very clear that there are much better foundations for mathematics. The main reason mathematicians stick with Zermelo-Fraenkel set theory is laziness.

As an afficionado of both category theory and traditional set-theoretic foundations, I’m inclined to a different view of this issue.

Rather than asserting that CT is a better foundations, I’m more inclined to say that it is a alternative foundations that highlights different aspects of the same phenomena.

In fact, gaining insight into how each approach says the same things (as extensively illustrated in Lawvere/Rosebrugh book) can bring even more illumination to the fundamental ideas and structures of mathematics.

Posted by: Marc Hamann on October 31, 2006 3:25 AM | Permalink | Reply to this

Re: Foundations

I suppose I should be a little more clear. I’m not talking about category theory being better than set theory. I’m talking about structuralism being better than platonism and formalism. When the mathematician tells you about internalization and the philosopher talks about structures and models you can’t help but see how well the two fit together and make a real sort of sense in terms of how we actually do mathematics in a day-to-day sense.

Posted by: John Armstrong on October 31, 2006 4:09 AM | Permalink | Reply to this

Re: Foundations

$MathML-enabled post (click for more details).$

Marc Hamann wrote:

Rather than asserting that CT is a better foundations, I’m more inclined to say that it is an alternative foundations that highlights different aspects of the same phenomena.

In fact, gaining insight into how each approach says the same things (as extensively illustrated in Lawvere/Rosebrugh book) can bring even more illumination to the fundamental ideas and structures of mathematics.

I’ll stand by my claim: category theory provides a better foundations for mathematics than Zermelo-Fraenkel set theory. It doesn’t just provide an alternatve approach to “the same things”. It talks about many new things, and sets the old ones in a vastly expanded context. As Toby explained, it provides a more richly pluralistic approach to foundations.

In other words, it lets us explore and understand a wide variety of mathematical universes, starting from very stripped-down ones (the elementary axioms of a category) to richer ones (the axioms for a cartesian category, or CCC, or star-autonomous category, etc.) to ones suitable for intuitionistic set theory (the axioms for a topos)… to ones just like those of Zermelo-Fraenkel set theory!

But, Zermelo-Fraenkel set theory is not the top of the totem pole. Moving in other directions, we can study universes where the logic is more quantum-mechanical in flavor (compact monoidal categories, symmetric monoidal categories with duals, etc.). Even better, we can adjust the “dimensionality” of our logic by taking any of the concepts I listed and replacing the word “categories” by “ $n$ -categories” for any value of $n$ - though the details are just beginning to be understood here.

In my view, such flexibility is just better than decreeing the shape of the mathematical universe once and for all, as axioms like Zermelo-Fraenkel set theory seek to do.

Of course, traditional foundationalism doesn’t want such a pluralistic approach. But, I think it’s best to admit from the very start that we have a lot of choice about how we’ll set up mathematics. So, we should try to organize a lot of interesting choices in a clear way, with functors zipping around that allow us to relate all these choices.

Posted by: John Baez on October 31, 2006 4:23 PM | Permalink | Reply to this

Re: Foundations

I strongly agree with John. Insisting on a single monolithic edifice like ZFC in which to ensconce all mathematics is something like a late 19th century geometer’s insisting that all geometries be represented within Euclidean geometry. It can be done, in a sense, but it makes much more sense just to accept without bias the various different worlds of geometry, each with its own internal laws, but nevertheless all happily coexisting and interconnected with one another.

Some years back (around 1997, 1998) there were furious debates on the FOM list on categorical foundations, specifically topos-theoretic foundations. One of the arguments invoked by the ZFC side was the presumed difficulty of teaching and using “naive topos theory” at a basic (say undergraduate) level, considering such ground levels as a proper concern or target for “foundations”. From that point of view, various thought experiments were proposed, e.g., if one takes seriously toposes as foundations, how would this then affect the way one teaches, for instance, a first course in real analysis?

I think Saunders Mac Lane was much occupied with similar issues in the last years of his life. Suppose S wanted to teach real analysis, in a spirit of naive topos theory, but standard in the sense of building on the reals as the complete archimedean ordered field. In the background would be a certain type of ambient topos with a natural numbers object; if S wanted to hew close to standard ways of doing things, he might want to throw in axioms of well-pointedness and Choice (hence Booleanness). Given enough pedagogical skill, S could probably effectively teach real analysis using toposes, in a way not that far removed from a standard set-theoretic course. In fact, according to Mac Lane and Moerdijk’s book on topos theory, the topos axioms just mentioned are equiconsistent with “bounded Zermelo set theory with Choice”.

Now: what parts of “core” mathematics can’t one do with these axioms? This is something Saunders really wanted to know, but I don’t think he ever got a simple answer. I was there at a few of the talks he gave on this (at Chicago). There was too much respect and deference toward the old man for any of the logicians present to just shout out, “It’s a very weak system, Saunders,” but I heard mutterings to that effect.

I interpreted the mutterings as having something to do with the absence of the axiom of replacement (or collection), the one that puts the “F” in “ZF”, but I’ve never really grokked why this axiom is considered important, and I’m not sure Saunders did either. It’s true that one cannot build sets like Union_n P^n(N) without it, but I don’t really understand what would be so “bad” about that. Moreover, the possible categorical significance of this axiom is murky to me. (It’s discussed in Joyal and Moerdijk’s Algebraic Set Theory, among other places, but it’s not a particularly simple matter, as far as I can tell.)

Can someone enlighten me on this?

Posted by: Todd Trimble on November 1, 2006 1:07 AM | Permalink | Reply to this

Re: Foundations

The good thing about ZFC is that you do not have to know it. You can pass through undergraduate university just with the basic notions of set theory without ZFC. I suppose most professional mathematicians do not have to know the precise ZFC axioms for their work but just the basic set theory. And the very basic set theory is something you can teach children at elementary school. The slightly more advanced stuff like the different notions of infinity can be explained to high school kids.

Topos are more complicated e.g. judging from the Wikipedia entry devoted to them which I find hard to understand.

So at the end, it is not clear what do you mean here by “foundation”. I can see three possible interpretation of what “foundation” means.

1. If you want to build in the technical sense the foundation of mathematics on topos you probably have to convince the logicians that this is interesting and lead to deep and important new questions. I would be skeptical if topos is a good basis in the technical sense for mathematics like set theory and predicate calculus.

2. If you offer it as the foundation for teaching mathematics it looks quite terrible.

3. But there is a third way. Maybe what you want is to offer topos as the foundation, in terms of “foundational ideas and way-of-thinking” rather than in a technical sense of mathematical logic. (Connecting to David’s informal notion of causality.) Namely, perhaps you want to say that these topos (or category theory as a whole) can be regarded as a foundational idea of large chunk of mathematics which have led to all sort of wonderful stuff. This is not competing with ZFC and related mathematical notions but rather a completely different ball game.

Posted by: Gina on November 1, 2006 2:39 AM | Permalink | Reply to this

Re: Foundations

You’re right: most of us could not state all the axioms of ZFC, in formal precise terms, even if our lives depended on it. You’re also right that as far as actual mathematical practice goes, it doesn’t actually matter: mathematicians get along quite well with what is affectionately known as “naive set theory” – working with sets on an informal and intuitive level. With only a little experience, they even develop a good sense of what could get them into set-theoretic trouble.

This irrelevance of the actual formal details of ZFC to our working lives makes it obvious that we routinely deal with sets not in terms of how they fit in the cumulative hierarchy, but operationally, functionally. In teaching topology or real analysis, we want our students to be able to deal with things like sums, products, direct images, inverse images, etc., in a very fluid hands-on way. If the teacher is armed with the insights of category theory, he or she will be far more effective in showing how these things really work, and in answering questions like: for infinite products, why don’t we use the box topology? Why does the inverse image operation preserve both unions and intersections, but direct image preserves only unions? In proving an equality between two subsets which involves limsups, how can I tell which is the easy direction to prove?

This is what I meant about teaching “naive topos theory”. Contrary to popular opinion, toposes are not that complicated. (And if you think they are, what are you doing hanging out at the n-category café!?) What I meant was get students comfortable with the manipulations which underlie some of the basic insights of topos theory, but do this in a relaxed informal hands-on way. You don’t have to scare them off with the words “topos” or “adjoint functors”! Even a lot of professionals are frightened by those words.

You say that as a “foundation for teaching” this should be “quite terrible”. I think I know better. But then, I wouldn’t expect you to understand that right away, if your sole exposure to topos theory is based on a wikipedia article read just a few hours ago. I do think if you dig a little deeper, you’d find that topos theory is about really basic [i.e., foundational] stuff, about our acquired experience with things that behave in ways that sets do.

As for your comment 1.: some, indeed many logicians are already convinced that toposes are interesting, deep, important, etc. (I think John said something similar to you regarding the status of categories in CS). As for “good basis in the technical sense for mathematics”: yes, that was one of the bones of contention in the FOM [Foundations of Mathematics] debates I mentioned. My main query was about the role of the axiom of replacement in everyday “core” mathematics, because I suspect this is the critical technical point where ZF could possibly have something important to say that toposes don’t, for the most part.

Finally, as for your point 3.: yes, except it’s not about competing. It’s all about understanding.

Posted by: Todd Trimble on November 1, 2006 3:07 PM | Permalink | Reply to this

Re: Foundations

Dear Todd, I suppose my points were rather instinctive and my main trouble is to understand what “foundation of mathematics” really means. (Maybe there are various sorts of foundations.) As for teaching, you may be right that basing mathematics education on naive type theory can work. Perhaps I am simply conservative or biased against too much abstraction in teaching mathematics. Was it tried?

Posted by: Gina on November 2, 2006 12:49 AM | Permalink | Reply to this

Re: Foundations

You’re right, Gina, there are a number of approaches to mathematical foundations, and the debates over their relative merits sometimes brings out emotional reactions (and excuse me if I seemed to be getting a little hot myself). Some people are downright religious in their beliefs, and the arguments sometimes get pretty vicious – the FOM debates are a good case in point.

The book Conceptual Mathematics by Lawvere and Schanuel (both pre-eminent researchers in category theory) is based on undergraduate classroom lectures they gave jointly, to put across the categorical viewpoint, starting from the most basic foundational concepts. My impression is that they were pretty successful in the classroom, and anyway it’s a great book – I encourage you to take a look. A lot of people who appreciate categories, myself included, have tried teaching a categorical understanding of basic concepts, with varying degrees of success of course. But I personally wouldn’t want to do it any other way.

I think you’ve really nailed it on the head when you worry about the dangers of getting too abstract too quickly. One thing I seem to remember about the Lawvere-Schanuel book is its concreteness – very down-to-earth illustrations.

Funny thing about category theory: it has this reputation of being really abstract (with n-category theory being abstraction raised to the nth power), and to be sure this reputation is partly deserved. But that’s not the way I like to look at it. I see the process of categorification, so much discussed on this blog, as a general moving away from abstraction.

For example: natural numbers are an abstraction of finite sets, where we’ve abstracted away everything but the cardinality of a set. To say I have a bag with three apples is more abstract than saying I have this bag, with a Fuji, a MacIntosh, and this Granny Smith which happens to be rotten. In the former case the apples are featureless (like a bag of monochromatic photons: not only are they all exactly alike, I can’t even keep track which is which). In the latter there is a possibility of identity and distinction. So, the set of natural numbers is more abstract than the category of finite sets. For a more sophisticated example, consider the fact that in the old days of algebraic topology, one contemplated the Betti numbers as invariants of a space, until eventually Emmy Noether came along and observed that these were actually abstractions (ranks, or dimensions) of homology groups, which are much more visualizable, much more alive.

Posted by: Todd Trimble on November 2, 2006 2:38 AM | Permalink | Reply to this

Re: Foundations

Gina wrote in part:

As for teaching, you may be right that basing mathematics education on naive type theory can work.

This is what I’ve done when teaching discrete mathematics (as an undergraduate course for mathematics and CS majors at UCR. I take functions as a primitive concept; although the course is not formal enough to have an explicit list of axioms, in effect I use the axiom AC! (that every functional, entire binary relation determines a function).

Of course, given the lack of formality, nobody can really tell that this is what I’m doing.

Posted by: Toby Bartels on November 2, 2006 11:27 PM | Permalink | Reply to this

Re: Foundations

In my view, such flexibility is just better than decreeing the shape of the mathematical universe once and for all, as axioms like Zermelo-Fraenkel set theory seek to do.

ZF is starting to seem like a straw-man here. I wouldn’t take seriously anyone who suggested that ZF (or any equally suitable set of axioms, e.g. NBG) was the end-all and be-all of the mathematical universe.

Let me sketch my own vision of how set theory and category theory work as foundations.

With set theory, you start from the primitive intuition of countable collections of “things”, and from there build more and more complex relationships and structures. Sets beget relations, algebras, topologies, etc.

With category theory, you start with the primitive intuition about relationships between structures, and from there deduce the complex properties of the “things”.

In this sense they are dual to each other: one moves from object to relationship, the other from relationship to object.

As I said before, each approach is going to highlight different aspects of mathematical reality. Someone who privileged one approach and ignored the other is going to miss out on a whole world of possible insight.

Let’s have some real pluralism and pay respect to both approaches.

Posted by: Marc Hamann on November 1, 2006 3:07 AM | Permalink | Reply to this

Re: Foundations

Let’s have some real pluralism and pay respect to both approaches.

Yes, but the question then is ‘What is it to pay respect to a research program?’. Often, it translates to a ‘let’s leave each other alone to carry on with our own business’ attitude. To some extent this works. Programmes come to be seen as flourishing or running out of steam. In the latter case, the young don’t sign up, and the old-timers moan to themselves about the passing of the good old days.

This is better than disrespectful rows, but it quite possibly represents a failure to respect other views properly in order to gain fully from them. The theory of rationality I have taken on from Alasdair MacIntyre charges us (p. 16) to make known our assessment of the state of our own programme, not only its successes, but also its current weaknesses and, hopefully temporary, lack of resources in resolving what it takes to be its central problems. These problems may not be taken as central by an other group, may barely be recognisable by them, but still it is possible that one of their number may learn this new language and come to see that they have resources to help with these problems. And it is possible that someone coming to learn the rival language as a ‘second first language’ may find resources useful to their own programme of origin.

This exposure of the perceived weaknessess of one’s programme is an uncomfortable activity, just as it is in the project which is our life. And it does not accord well with a climate in which we must scream out how well we are doing to secure resources. But in the right conditions it steers us towards the truth more rapidly. Perhaps we should have a session on this blog of reporting what we take to be the current largest weaknesses of n-category theory.

Posted by: David Corfield on November 1, 2006 9:11 AM | Permalink | Reply to this

Re: Foundations

I would *love* to see a discussion of the weaknesses of n-category theory. I used to be fascinated by n-categories, but one morning I woke up and the spark had gone out. It would be nice to have it back. (I still like n-category theorists, though.)

On another note, I would also be interested in some explanation of the role of Grothendieck universes in foundations. Johnstone in his first book says “there is no *real* need to do this”, meaning introduce universes. I’m not sure what, exactly, this means. Where do universes live on the spectrum of “definitely not needed in any sense” to “not needed if you only do ‘elementary’ mathematics” to “needed but everyone knows what you mean when you don’t use them” to “definitely needed and if you don’t use them, you’re talking nonsense”? I have a hard time with this foundational stuff, but I don’t want to write a paper about toposes and embarrass myself.

Posted by: James on November 2, 2006 9:55 AM | Permalink | Reply to this

Re: Foundations

Let’s see if we can get back that lovin’ feelin’. By discussing weaknesses, I mean to include perceptions that less progress has been made than you expected on what you continue to take as important tasks, shortfalls which may be explicable as due to what you conceive as the misdirection of research effort.

Posted by: David Corfield on November 2, 2006 10:43 AM | Permalink | Reply to this

Re: Foundations

$MathML-enabled post (click for more details).$

David writes:

Perhaps we should have a session on this blog of reporting what we take to be the current largest weaknesses of $n$ -category theory.

One big weakness of $n$ -category theory is that we don’t really know what an $n$ -category is!

We have a bunch of definitions which seek to capture the idea, and probably a bunch of them are “right” - but they’re all pretty complicated, and we don’t know how to prove that any of them are equivalent - except for those which differ in very minor ways. So, different people are working with different definitions, and the rate at which theorems are being proved is rather slow. Before proving anything really exciting, there are lots of basic results one would like to have - essentially n-Categories for the Working Mathematician. We are quite far from having them.

(André Joyal’s book will be a start, especially since it interacts synergistically with Lurie’s book on $\infty$ -topoi. But, neither of these treat $\infty$ -categories in general: just those where all $n$ -morphisms for $n > 1$ have inverses.)

These days I’m sidestepping this morass by proving some rigorous results for low $n$ which hint at big patterns that make the subject exciting. This doesn’t really solve the problem - it just avoids it! But I hope it will attract more people to the subject, so that eventually the problem will be solved.

Someday we’ll really figure out what $n$ -categories are. It’ll probably take at least a few decades. I will probably be too old to understand the answer.

That sounds depressing. But, I find it more fun coming in near the beginning, than coming in later when everything is understood. If people really knew what $n$ -categories were, I would probably not find them so interesting. I’d probably work on something else. As Rota put it:

“Mainstream mathematics” is a name given to mathematics that more fittingly belongs on Sunset Boulevard.

Posted by: John Baez on November 3, 2006 6:24 AM | Permalink | Reply to this

Re: Foundations

$MathML-enabled post (click for more details).$

by proving some rigorous results for low $n$ which hint at big patterns that make the subject exciting.

That’s what first got me interested - things like the tangle hypothesis. Has anyone other than you and Jim worked like this?

Another strategy is to show how by placing existing constructions in an $n$ -categorical setting you can extract more information than you otherwise could. By the look of things, Ross Street is doing this with group representation theory. It strikes me that there’s huge scope for this kind of work.

Posted by: David Corfield on November 3, 2006 9:33 AM | Permalink | Reply to this

Re: Foundations

John wrote:

[C]ategory theory provides a better foundations for mathematics than Zermelo-Fraenkel set theory.

Although ultimately I agree with you, John, your argument here is rather unfair to set theory. After all, you could (almost) just as well write:

[S]et theory provides a better foundations for mathematics than the Lawvere–Rosebrugh axioms of a Sets-like topos.

In each case, a general programme (perfectly capable of pluralism) is being contrasted with a specific set of axioms (metaphorically carved in stone).

It’s true that a lot of mathematicians (at least while still in school) are taught that the foundations of mathematics are given by something called “set theory” and that the axioms of ZFC (even if one never sees them) are the axioms of this “set theory”. And this is a Bad Thing, inimical to mathematical pluralism. But actual set theorists know better (even those that aren’t pluralists), and they study different axioms and their interrelationships. Almost all that I know about the consequences of removing and adding various axioms derives ultimately from the researches of set theorists; everybody else is coming late to the game that they began.

Now, I do think that set theory (in the sense of a theory based fundamentally on membership) will ultimately fade away, to be replaced with type theory (for syntax) and category theory (for semantics). But this is for practical, tactical reasons. (Even my personal gladness that this is happening is largely for practical reasons.)

Posted by: Toby Bartels on November 1, 2006 11:53 AM | Permalink | Reply to this

Re: Foundations

Hi there. As my native language is not English, I warn you there could be forthcoming imprecisions.

The consistency of mathematics doesn’t lie in any set of axioms that would be fixed once for all. Paradoxes of set theory were just problems we can compare nowdays with some unsolved conjecture in algebraic geometry. No more, no less. It is also true that this question of foundations is certainly related with a tradition of transcendental philosophy, and this could explain why people got very excited about it (even mathematicians, like Hilbert, who really believed in some transcendental mathematical picture). Thanks to Gödel, this has to remain a belief or to vanish (at least in the setting of set theory). Set theory can of course be useful to other area of mathematics by the same process that makes analysis useful to some features of arithmetics.

And in practice, even if it seems for example that we use the axiom of choice, it doesn’t mean that we really have to use it in the form we all know. There could be a lot of other ways to give sense to what we are talking about. We just pick the easiest version to make us understandable (and easiest can mean simply for example: this the way we learnt to practice all this). Another good example would be to consider the axiom of universes. To my knowledge, it is not really necessary in practice. We could keep our arguments in ZFC just by taking care of some suitable bounds on cardinals: even if we use some strange ways to define things, we always constuct everything from a ‘small’ set of data, so that we never really need to have any small colimits or limits but only those that are indexed by categories bounded by some suitable fixed cardinal. But this would be a heavy way to express ourselves and wouldn’t help anyone to understand our already abstract arguments. Moreover, if we want to communicate, it makes life easier if we don’t go too far from the traditions. Hence we keep formally what our predecessors taught us as ‘foundations’. In conclusions, what is historically called foundations of mathematics is just part of foundations of a tradition to do mathematics nowdays in western countries. I don’t want to throw everything away at all (I am very indebted to these traditions), but they certainly cannot be seen as necessary. Moreover, set theory has never been the whole thing that came as foundations of our tradition. This is where Yuri Manin’s definition of foundations completes the picture.

What happends in a mathematician’s everyday life then? We never think of foundations (unless we want to work specically on them as a mathematical theory). We just do mathematics.

And what does it mean? We interpret arbitrarily some symbols according to some intuitions we have. And we do this with a strange underlying idea: we keep our mind ready to dismiss what we are thinking about at any time. This is where rigour arises, as a constraint and as a freedom. And this surely is something special about mathematics: we can (have to) do this because we don’t speak about something in particular that is necessarily supposed to exist out of our theories and/or mind. And nothing else is the foundation of mathematics. If someone asks me: ‘why is it rightful to define this this way?’ I can always answer with rigour: ‘because I decided so’. We can always argue about the fact what I am doing is interesting or not, but there will be no need for further foundations. The only question that arises after this is: how will I keep both my rigour and my intuition while going on? And also: how can I explain to someone else what I am doing? This is where tradition can come to help me. The knowledge and statecraft I share with other mathematicians will help me to go further (e.g. will feed my intuitions) and will help me to make my work understandable to others, so that other people will recognize more easily that what I am doing is indeed mathematics.

Posted by: Denis-Charles Cisinski on October 31, 2006 1:38 AM | Permalink | Reply to this

Re: Foundations

We see eye to eye. I’m fond of Weyl’s statement:

Mathematics is not the rigid and petrifying schema, as the layman so much likes to view it; with it, we rather stand precisely at the point of intersection of restraint and freedom that makes up the essence of man itself.

(p. 136, ‘The Current Epistemogical Situation in Mathematics’ in Paolo Mancosu (ed.) From Brouwer to Hilbert. The Debate on the Foundations of Mathematics in the 1920s, Oxford University Press, 1998, pp. 123-142).

Of late, I’ve been working on what you address in your final sentences - the relationship between the individual mathematician and his/her tradition. If mathematics as a discipline has weaknesses, they are in the ways in which ‘knowledge and statecraft’ are transmitted. I hope in a small way our blog can help improve this transmission, perhaps by stimulating a chain of similar blogs. I see it as philosophy in action.

Posted by: David Corfield on October 31, 2006 9:41 AM | Permalink | Reply to this

Re: Foundations

After reading over that entire discussion what a pleasure to run across your comments. Here comes the HOWEVER. However, when you say “because I decided so” I think you do a bit of a disservice to your overall message.I believe you are saying: Look at the reality of what mathematicians do! I raised this point when I was a student of Maddy’s. We as mathematicians only decide on the specifics of the manner in which we say the truth. We only “decide” to say a truth according to the manner our inclinations dictate. However, the truth still exists independent of the manner in which we express it. This opinion is an example of Goedelian platonism the likes of which Maddy sought to defend. So you point out that intuition and practice are enough to override foundational arguments. I see a place for both. However, I would suggest that the philosophy majors who spend so much time referring to large cardinal axioms and “ZFC” find an unsolved Diophantine equation and work on it for the next twenty years and see if at the end of that time period whether foundational issues are still paramount. How in the world would the existence of large versions of “I can keep adding one more even when it seems counter intuitive” play any role in solving an equation over the natural numbers. by the way I know there are relationships but how does it play into saying “I have found it and here are solutions”. The Foundation of Mathematics is the art that Mathematicians share!

Posted by: nathan on December 3, 2006 9:27 AM | Permalink | Reply to this

Re: Foundations

We as mathematicians only decide on the specifics of the manner in which we say the truth. We only “decide” to say a truth according to the manner our inclinations dictate. However, the truth still exists independent of the manner in which we express it.

This seems to miss the true power of the contemporary approach to mathematics. The “truth” – in some abstract sense – may be out there independent of us, but we we as mathematicians have freed ourselves from it.

Physicists and philosophers can argue whether the parallel postulate does or does not obtain in the “real world”, but it doesn’t matter at all to the mathematics. There may be “no such thing” as a strongly inaccessible cardinal, but we can see what it would mean if they did anyway. I can pick up the axiom of choice and say I can chop one sphere into two of the same size, and you can put down the axiom of choice and say I’m crazy. Both are true since mathematical truth is localized to the structure under consideration and the arbitrary rules we’ve chosen to play by.

And this is actually a good thing. Imagine for a moment that we thought mathematical truth was really out there and independent of our work. Now Perelman’s work is pretty much vetted, so we accept the Poincaré conjecture (theorem?). But there have been people who have derived results, even their doctoral theses, from the hypothesis that it was false. If we believed that mathematical truth was somehow tied to the real world, then their very hypotheses would be “wrong”, and we should strip them of their degrees and honors right now. No, their positions are safe because what they said was true: in a structure where (among other things) the Poincaré conjecture is false, certain other things must happen.

The upshot is that mathematical truth does not apply to simple predicates. It strictly applies only to derivations. We should not read “2+3=5” to mean that there are some things out there called “2”, “3”, and “5”, as well as “addition” and “equality” and that this statement holds true for those things. The meaning instead is “In any model of Peano arithmetic it can be validly deduced that 2+3=5”.

Posted by: John Armstrong on December 3, 2006 4:48 PM | Permalink | Reply to this

Re: Foundations

I never tire of reminding people, though, that mathematicians, including you yourself do work with a notion of mathematical reality:

Hack at a problem and you can find a hundred little answers leading to a hundred little papers. Bide your time and you get a handful of true insights. Guess which path will get a freshly-minted Ph.D. a job first.

This came after a discussion of carving mathematical reality at its joints. For more on this topic, see here. I refer there to Michael Polanyi’s claims that:

A new mathematical conception may be said to have reality if its assumption leads to a wide range of new interesting ideas. (Personal Knowledge: 116)

…while in the natural sciences the feeling of making contact with reality is an augury of as yet undreamed of future empirical confirmations of an immanent discovery, in mathematics it betokens an indeterminate range of future germinations within mathematics itself. (Personal Knowledge: 189)

As your comment suggests, even if it is not the case that connecting to this mathematical reality gets you more credit than puzzle-solving, it ought to.

Posted by: David Corfield on December 3, 2006 5:14 PM | Permalink | Reply to this

Re: Foundations

I didn’t mean to imply that I don’t believe in mathematical reality or mathematical truth. Look how much I use the terms in my explanation. What I mean is that they’re not “out there” in the same way physical reality is. Mathematicians always have the option of changing the rules, although if they choose their rules badly their games become trivial quickly.

How many times have you seen a mathematical concept introduced because something “should be true”, and so we make it true. Equivalence of varieties makes perfect sense until you notice that “it shouldn’t matter” that there’s a self-intersection there for the purposes of your problem. Oh, but away from those curves it’s all fine and dandy, and we can restrict away by thinking of rational functions instead of polynomials. So now we introduce birational equivalence of varieties because these two “should be the same”. Change the rules, change the game, change the goal. Mathematical truth is an entirely slipperier animal than its physical cousin.

Posted by: John Armstrong on December 4, 2006 4:02 AM | Permalink | Reply to this

Re: Foundations

Slipperier indeed. The question is whether there is still a notion of ‘getting things wrong’. Our predecessors may have had a choice of which way to take a field, and we may now think that they took the wrong path. And we may also expect that a century hence, and perhaps forever more, so long as people act rationally, that mathematicians will agree with us that we’ve corrected that false trail.

That’s a fairly robust notion of reality.

Posted by: David Corfield on December 4, 2006 4:12 PM | Permalink | Reply to this

Re: Foundations

The paths chosen by our predecessors are certainly a strong reality. But I don’t understand how this is linked with the fact these paths are `wrong’ or not. In fact I don’t understand what `wrong’ could mean there (maybe this is because I didn’t understand you, but I would answer I don’t think this is obvious we do better than our predecessors). Do you have an example in mind?
I understand better the question `is this piece of work mathematics?’ than `is this wrong or not?’ And I will certainly agree that the possibility of saying `this is mathematics’ or `this is not’ is part of a notion of reality we can share.
The questions of truth and of reality can be related, but are not the same, are they?
Of course we can say sometimes about an argument and/or a computation `this is correct’ or `this is not’; but in the second case, we just have to work further to make it smooth. In this case, we meet the reality of rigour in mathematics.
Another interesting question is about a definition of a theory to be good or not (indepently of tradition, assuming this could be possible). What we have in mind is an intuition and the desire to write it down as explicitely as possible (and explicitely means here : with full rigour). This is interesting there because we make a claim: `what I will define will talk about this very intuition I have’. If the definition is correct, we will feel very strongly that what we have written down fits very closely with the intuition. Here, we have three very real things: intuition and what has been written and the `perfect’ fit of writing on intuition. But soon rigour will remind ourselves that there must be some very different ways to write down this intuition, or we will discover analogies between two different intuitions and will want to relate them (think for examples of the strange similarities of certain invariants of knots and of prime numbers; e.g. Alexander polynomials and Iwasawa theory). Hence we will feel we may have to dismiss what we have done someday. This possibility is also part of our reality.
I see quite a few realities for working mathematicians: intuition, the permanent possibility to dismiss everything, the wish to write down everything explicitely (our favorite fantasy of perfectness) and the companionship of traditions (that could include some other wishes and desires). All these (and maybe some others I don’t see now) have different flavours, are certainly related, and are fairly used to mean what is good or true etc… This is certainly robust but not that rigid.
The notion of intuition is quite fuzzy (at least in this post) and should maybe deserve a better understanding. For example, it is interesting to ask the relationship between intuition and truth (how do we get our intuitions of truth?). I suppose this is where my lack of philosophical knowledge appears obviously.

Posted by: Denis-Charles Cisinski on December 5, 2006 1:12 AM | Permalink | Reply to this

Re: Foundations

The relationship between intuition and its capture in a formalism is an intriguing one. I’m fond of Yuri Manin’s comment:

…the most fascinating thing about algebra and geometry is the way they struggle to help each other to emerge from the chaos of non-being, from those dark depths of subconscious where all roots of intellectual creativity reside. What one “sees” geometrically must be conveyed to others in words and symbols. If the resulting text can never be a perfect vehicle for the private and personal vision, the vision itself can never achieve maturity without being subject to the test of written speech. The latter is, after all, the basis of the social existence of mathematics.
A skillful use of the interpretative algebraic language possesses also a definite therapeutic quality. It allows one to fight the obsession which often accompanies contemplation of enigmatic Rorschach’s blots of one’s imagination.
When a significant new unit of meaning (technically, a mathematical definition or a mathematical fact) emerges from such a struggle, the mathematical community spends some time elaborating all conceivable implications of this discovery. (As an example, imagine the development of the idea of a continuous function, or a Riemannian metric, or a structure sheaf.) Interiorized, these implications prepare new firm ground for further flights of imagination, and more often than not reveal the limitations of the initial formalization of the geometric intuition. Gradually the discrepancy between the limited scope of this unit of meaning and our newly educated and enhanced geometric vision becomes glaring, and the cycle repeats itself.

Certainly, some philosophical work needs to be done here, as the quotation from Michael Harris at the end of this post indicates. What is it to say two pieces of work contain the same idea?

You write:

I don’t understand what `wrong’ could mean there (maybe this is because I didn’t understand you, but I would answer I don’t think this is obvious we do better than our predecessors). Do you have an example in mind?

Let’s see. I can point to some examples most would agree with:

Bourbaki’s attempt to define what a mathematical structure is.
Neutrosophic groups.
The decision to avoid the use of groupoids, and stick with groups in a host of situations.

And then I could point to disputes about direction:

Arnold’s claim that mid 20th-century mathematics was hijacked by left-brained mathematicians. Ditto for Mandelbrot about ‘Charles Street mathematicians’.
The claim that there’s no point to going beyond 2-categories.
That there is a point to going beyond 2-categories, but that the introduction of tools from homotopy theory, such as model categories, is a mistake.
Rota gives a number of examples of theories that have been subsumed within other larger ones, thereby losing what was special about them.

The claims are not that someone is producing logically incorrect work. Rather the direction of their ideas is wrong.

Posted by: David Corfield on December 5, 2006 10:00 PM | Permalink | Reply to this

Re: Foundations

I really have a problem with using the term “wrong” in these sorts of situations. Maybe I’m being overly relativist, but all of these seem to me to be “valid choices of rule-sets that I wouldn’t particularly care to make”.

I draw the analogy with the physical theories of orbits. The epicycle model is perfectly “right” (within a Newtonian context), but it’s so inefficient that pretty much everybody would prefer to use the elliptic model. On the other hand, if you had a good reason to prefer circles and liked summing a lot of series.. well you can choose to work with the epicycle model.

I don’t think we’re really that far off in our positions, but your choice of term (“wrong”) seems to me to imply an intrinsic value judgement, while I claim the non-existence of a universal sense of value.

Posted by: John Armstrong on December 5, 2006 11:21 PM | Permalink | Reply to this

Re: Foundations

I have the same kind of feeling: using the term `wrong’ can hurt the way I like to see (of course this is very personal).
But let’s go back to some of the example David Corfield gave. The common feature about these `wrong’ positions is that they consist to miss something or to refuse something. Hence they are themselves giving a value. So the obvious way we can answer consists to give a value to these positions as well and may say they are wrong (or not). Then I will agree that some of them are wrong: I think this is silly to forbid ourselves to go somewhere a priori! But instead of saying they are wrong or not we also can criticize some of them. Criticism is not the same as saying something is wrong or not. At least Bourbaki’s attempt to define structures is certainly not wrong and they are a lot of things we can learn from his work (and criticizing will contribute to our knowledge).
I agree that to avoid a priori the use of groupoids or of higher categories is silly and doesn’t even deserve a critic. There are two possibilities: this is wrong in the sense it has nothing to do with mathematics as a craft but with mathematics as a place where politics take place (which can be interesting to study as well); or this could be the expression of ignorance and of lack of thinking: in these two examples, this is the principle of naturality that is ignored (what is wrong is not to ignore this principle but to ignore the possibility that someone could do some nice mathematics with it).
It seems to me that another question arises: what is the place for judgement in mathematics? Of course, we cannot avoid to make judgements. There are judgements we make ourselves, and some others we learn from the tradition, and it doesn’t look that easy to say which of them are good or not in an absolute way (this could depend on the situation…). For example, I believe the principle of naturality is a good one. But I can also imagine someone doing nice mathematics without such an opinion (e.g. Erdös). This is also related with the nature of intuition. Maybe some people have a good intuition of geometric situations using groups and don’t see anything with groupoids. What is wrong is to forbid the use of groupoids or to forbid the use of groups… But people can say `I prefer to work with groups’ and not be wrong, even if I prefer groupoids (and natural constructons in general) myself.

Posted by: Denis-Charles Cisinski on December 6, 2006 1:00 PM | Permalink | Reply to this

Re: Foundations

One of the dangers of blog discussions on topics which require some subtlety is not making the effort to express oneself clearly enough. I think I’ve been guilty of this as I snatch moments between sessions at the conference I’m attending. Denis-Charles’ and John’s misgivings concerning what I say about going ‘wrong’ reflect this.

In this particular snatched moment, let me start out from what I take to be solid ground. Mathematical activity at its highest level is governed by narratives. These narratives represent what their narrators take to be the successes of their field, and may also include accounts of what are considered to be dead-ends. There is more subtlety to be had than being on the right track or wrong track. One can say of work that it hasn’t subsequently contributed much insight, but still recognise it was worth pursuing. To say of some episode that it was absolutely wrong is going to be very unusual. In fact, one might have to resort to a thought experiment to think up a situtation in which you might despair that mathematics was heading in the wrong direction. Perhaps if everyone but you starts trying to fuzzify their field. Or a more extreme example, everyone allows paraconsistent logics.

That snatched moment is over, and I have to leave.

Posted by: David Corfield on December 6, 2006 7:00 PM | Permalink | Reply to this

Read the post A Categorical Manifesto
Weblog: The n-Category Café
Excerpt: Why are categories important in computer science?
Tracked: November 2, 2006 5:02 PM

Read the post The Tasks of Philosophy
Weblog: The n-Category Café
Excerpt: What should philosophy study?
Tracked: November 10, 2006 12:00 PM

Re: Foundations

I just noticed this paper updated tonight on the arXiv: Towards a Hermeneutic Categorical Mathematics or why Category theory goes beyond Mathematical Structuralism. Of course I’m inherently skeptical of any paper whose title includes the phrase “Towards a Hermeneutics”, but I won’t have a chance to look at this at least until Friday. Can any of the philosophers in the peanut gallery say whether it’s worth reading or not?

Posted by: John Armstrong on December 20, 2006 5:38 AM | Permalink | Reply to this

The n-Category Café

Skip to the Main Content

October 30, 2006

Foundations

Posted by David Corfield

Some Related Entries

132 Comments & 2 Trackbacks

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Choice.

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations

Re: Foundations