2005 : WHAT DO YOU BELIEVE IS TRUE EVEN THOUGH YOU CANNOT PROVE IT?

Most of what I believe I cannot prove, simply for lack of time and energy; truths that I'd claim to know because they have been proved by others. That is how inextricably our beliefs are tied up with labors accomplished by fellow beings. And then there are mathematical truths that we now know are not provable. These phenomena have become favorites with the media but can only be made sense of by a serious scrutiny of the idea of mathematical truth and a specific articulation of a proof-concept,

But running across Esther's contribution I came up with a catchy response:

I believe in the creative power of boredom.

Or, to put it into the form suggested by the Edge question:

I believe that, no matter how relentlessly we overfeed our young with prepackaged interactive entertainments, before long they will break out and invent their own amusements. I know from experience; boredom drove me into mathematics during my preteens. But I cannot prove it, till it actually happens. Probably in less than a generation kids will be amusing themselves and each other in ways that we never dreamt of.

Such is my belief in human nature, in the resilience of its good sense.

Here is an observation from mathematical practice. By now the concept of an algorithm, well- defined, is widely hailed as the way to solve problems, more precisely sequences of problems labeled by a numerical parameter. The implementation of a specific algorithm may be boring, a task best left to a machine, while the construction of the algorithm together with a rigorous proof that it works is a creative and often laborious enterprise.

For illustration consider group theory. A group is defined as a structure consisting of a non-empty set and a binary operation obeying certain laws. The theory of groups consists of all sentences true of all groups; its restriction to the formal "first order" language L determined by the group structure is called the elementary theory TG of groups. Here we have a formal proof procedure, proven complete by Gödel in his PHD thesis the year before his incompleteness proof was published. The elementary theory of groups is axiomatizable: it consists of exactly those sentences that are derivable from the axioms by means of the rules of first order logic. Thus TG is an effectively (recursively) enumerable subset of L; a machine, unlimited in power and time, could eventually come up with a proof of every elementary theorem of group theory. However, a human group theorist would still be needed to select the interesting theorems out of the bulk of the merely true. The development of TG is no mean task, although its language is severely restricted.

The axiomatizability of a theory always raises the question how to recognize the non-theorems. The set FF of those L-sentences that fail in some finite group is recursively enumerable by an enumeration of all finite groups, a simple matter, in principle. But, as all the excitement over the construction of finite simple monsters has amply demonstrated, that again is in reality no simple task.

Neither the theory of finite groups nor the theory of all groups is decidable. The most satisfying proof of this fact shows how to construct to every pair (A, B) of disjoint recursively enumerable sets of L-sentences, where A contains all of TG and B contains FF, a sentence S that belongs neither to A nor to B. This is the deep and sophisticated theorem of effective non-separability proved in the early sixties independently by Mal'cev in the SSSR and Tarski's pupil Cobham.

It follows that constructing infinite counter-examples in group theory is a truly creative enterprise, while the theory of finite groups is not axiomatizable and so, to recognize a truth about finite groups requires deep insight and a creative jump. The concept of finiteness in group theory is not elementary and yet we have a clear idea of what is meant by talking about all finite groups, a marvelously intriguing situation.

To wind up with a specific answer to the 2005 Question:

I do believe that every sentence expressible in the formal language of elementary group theory is either true of all finite groups or else fails for at least one of them.

This statement may at first sight look like a logical triviality. But when you try to prove it honestly you find that you would need a decision procedure, which would, given any sentence of L, yield either a proof that S holds in all finite groups or else a finite group in which S fails. By the inseparability theorem mentioned above, there is no such procedure.

If asked whether I hold the equivalent belief for the theory of all groups I would hesitate because the concept of an infinite counterexample is not as concrete to my mind as that of the totality of all finite groups. These are the areas where personal intuition starts to come into play.