FOM: Friedman's result

Neil Tennant neilt at
Sun Mar 15 23:43:59 EST 1998

Having taken a few days out to grade a symbolic logic final exam, I
have just returned to reams of email from fom. Their tone seems to be
a symptom of end-of-winter-term malaise, grading stresses, and other
factors that lead to carping and incivility. Ouch, it's like working
in a department riven by factionalisms, tenure disputes etc.! This
erstwhile cyber-retreat from normal institutional vicissitudes has
become a place where people do not so much share their intellectual
bananas, as knock them out of people's hands as soon as they are
revealed as an offering. Even marmosets do better at sharing their

It seems that the big breaking story---our foundational equivalent of a
Monica Lewinsky---is Harvey's strong independence result on finite
trees. Martin Davis, among the distinguished figures on this list, is
gracious enough to praise it highly. But Torkel Franzen, normally very
astute in his observations, inexplicably dismisses the result as not
very exciting. Torkel's dicta make a strange mix. He finds the
combinatorial sentence too difficult, and he can't find a definition
of subtle cardinals on the Web. (Gosh, what has happened to
*libraries* in Sweden, Torkel? I do recall some correspondence in the
Times Literary Supplement last year about the savaging of Sweden's
holdings of hard copies in the interests of electronic efficiency, but
I hadn't realized it had gone that far...)  Later Torkel admonishes
Harvey by saying that one should wait for the result to sink in with
the experts before pronouncing on its significance. But Harvey simply
stated the result, with a clear and sober scientific summary that
helped orient the reader; it was somebody else who offered an opinion
as to the result's significance. Torkel, shouldn't your admonition
apply even more strongly to would-be *detractors* rather than would-be
*proselytizers*?---in other words, to yourself at the time of your
first posting on the matter?

Email is a rather crude medium for the exchange of mathematical
minutiae. Using notations like x_n when an ordinary mathematical text
would have n as a subscript to x, is something we are forced to do
with email, and which obstructs immediate understanding. If a sequence
of definitions is presented (a) really rigorously, and (b) in email
with perforce suboptimal font conventions, then one ought perhaps to
suspend judgment until the material is in more accessible and
conventional form, and there is an intuitive explanation on hand for
what is coded in the definitions. A few diagrams on overheads would
give one the "Aha" Erlebnis with Harvey's definitions that is so
elusive when reading email on the screen.

Moreover, if one has any inkling of what Harvey has been brewing for
the past several years, one should *expect* that the specification of
the set-theoretic axioms *from* which independence is proved will
contain some very recondite notions in large cardinal theory. The
higher one can go in the hierarchy of cardinal existence assumptions,
and still secure independence, the more cracking the result. So one
should perhaps have a copy of Kanamori's book "The Higher Infinite" on
hand for future installments, as independence is proved from cardinals
of even dizzier heights.

The "general intellectual interest and significance" of Harvey's
results in this area do *not* depend on the independent sentence being
immediately intelligible to the average high-school graduate (though
it's steadily tending that way). All that is needed is that the
combinatorial result be one which many expert mathematicians in the
field concerned (namely: combinatorics/graph theory/theory of
algorithms) find accessible, natural, simple and fruitful; and that
the average high-school graduate have some reasonable idea of what
*that* might mean. A Godel sentence for any axiomatized system of
arithmetic, for example, would not attract these labels even from
experts. (I have in mind here the kind of sentence that says of
itself, via the coding, "I am unprovable".)

Nor do the "general intellectual interest and significance" of these
results depend on the average high-school graduate being able to grasp
the details of the set theory from which independence is
established. All that is needed is that the theory in question be one 
that *set theorists* (and mathematicians generally, to the extent that
they care and know enough about formal set theory) would say contains
a striking degree of axiomatic power; and that the average high-school
graduate, again, have some reasonable idea of what *that* might mean.

With these two qualifications in place, the general intellectual
interest and significance of the result can be stated along the
following lines, in just four paragraphs of sound-bite. These
paragraphs ought to be accessible to the average high-school graduate
(if not in the USA, then certainly in Sweden).


"Ever since Euclid's axiomatization of geometry, and the interest in
his postulate of parallels, mathematicians have been fascinated by the
question of the independence of relatively simple mathematical
statements from the other basic axioms of a discipline. Given those
other axioms, can the statement in question be proved or refuted?  In
the late 19th century various famous mathematicians (Gauss, Bolyai,
Lobachevsky, Beltrami, Riemann ...) finally established that the
parallels postulate was *independent* of the other core postulates of
Euclidean geometry. 

As with Euclid's core axioms and the parallels postulate, so too, in
the twentieth century, with the Zermelo-Fraenkel axioms of set theory
plus the axioms of choice, and Cantor's famous continuum hypothesis.
CH was shown to be independent of ZF+AC (Godel, Cohen). This was
particularly interesting because set theory (ZF+AC) can serve as a
foundation for all of mathematics; its axioms have considerable power
and scope. These axioms leave unsettled, however, the question of the
truth or falsity of CH. (Likewise, ZF alone leaves unsettled the
truth-value of AC.)

Godel had also shown, in his famous incompleteness theorem for
arithmetic, that for any formal system of arithmetic there would be an
independent sentence in the language of arithmetic, whose truth could
be established from "outside" the system but which could not be
established *within* the system. Although such a sentence turns out to
be terribly long-winded, it is only about the natural numbers, and
indeed not of great logical complexity (involving as it does only one
generalization about all numbers). Later on, Godel's results were
improved so that the independent sentence had a more natural,
combinatorial flavor (Paris, Harrington). All these independent
arithmetical sentences, however, can be proved within a very weak
fragment of set theory; it is only the formal system of arithmetic,
using arithmetical primitives, which does not have the axiomatic clout
to settle their truth.

Naturally, interest then focused on the 'ultimate' kind of
independence result that one might fashion from the foregoing
materials. Might there be natural, simple, combinatorial statements
**about natural numbers** whose independence could be demonstrated
from **the most powerful extant axiomatizations of set
theory**---extensions of ZFC postulating the existence of various large
cardinals? As it happens, the answer appears to be affirmative ... "

____________ END OF SOUND-BITE

Neil Tennant

More information about the FOM mailing list