FOM: On finite combinatorial statements
Neil Tennant
neilt at mercutio.cohums.ohio-state.edu
Wed Aug 19 16:32:57 EDT 1998
I believe one can understand Con(ZFC) without knowing anything about
Zermelo-Fraenkel set theory. Here's how (imagining that I am the
experimental subject who begins with no knowledge of set theory):
Someone explains to me the notion of a well-formed formula of the
first-order language containing a binary predicate as its only
non-logical expression. Here the talk is about concatenations of
symbols. Such talk need not be understood set-theoretically at
all. This language, of course, is going to be the language of set
theory; but my interlocutor need not reveal that to me. Its binary
predicate is the predicate of set-membership, but that too is kept a
secret from me. So: I attain a grasp of the concept "grammatical
formula" (of this language) without needing any set theory.
My interlocutor then distinguishes for me certain sentences in this
language. Some are simply written down; others are to be obtained by
taking substitution instances of (finitely many) schemata. These
schemata can also be written down. Without my knowing it, one thereby
obtains all the axioms of ZFC. I simply see them as formal sentences,
devoid of any meaning. I can say *what* those sentences are; I can
effectively decide, of any given finite string of symbols *whether* it
is in this distinguished list of special sentences that my
interlocutor has given me; but I do not understand those sentences as
making claims *about* anything in particular. Of course, knowing the
bare minimum that these are sentences from a first-order language, I
might be tempted to *cast about in my own mind* for an interpretation
that makes true exactly the sentences on the distinguished list; but I
*need not* do that. And even if I do, I might never even tumble to the
fact that the sentences can be interpreted as being "about sets".
So: I can recognize members of a class of sentences, this class
happening to consist of exactly the axioms of ZFC, without having to
understand these sentences as making claims about sets.
My interlocutor then proceeds to state for me the inference rules of a
suitable sound and complete system of proof for first-order
logic. I'll assume that this is a set of rules for, say, a natural
deduction system with # as its absurdity symbol. I become expert in
generally recognizing whether a given (finite) construction is or is
not a proof of a given sentence (which might be #) from a given
(finite) collection of premises. The only ability involved here is my
ability to recognize *patterns* of symbols on a (large enough) page. In
fact, I do not even have to know, or understand that, the idea is that
the "steps" within the proofs preserve truth! All I have to be able
to recognize is that any given step conforms, in shape, to one of the
prescribed permitted forms for proof-building. So: I am now in a
position to say that I could, in such a situation, claim a reasonable
grasp of the statement
"There is no proof ending with # all of whose undischarged
assumptions come from the distinguished list of sentences
first described to you."
All that is needed for an understanding of *this* claim is a
conception of the abstract structural possibilities for proofs
themselves---arrays of symbol-strings on a (large enough) page. I can
have a "synthetic" understanding of this matter, without recourse to
anything set-theoretic.
The quoted sentence above is of course none other than Con(ZFC). I
understand *what it says*. I grasp its *truth-conditions*. BUT I need
not know anything at all about sets, or about set theory, in order
thus to grasp it.
Well, maybe not, the objector might say. It's not quite Con(ZFC) just
yet, because it quantifies directly over proofs and sentences
understood as finite strings of symbols and finite arrays of such
strings. Isn't the statement that is usually called Con(ZFC) one in
which the quantifications involved are over G"odel numbers for such
strings and arrays? The point is well taken. Let us, then, simply
G"odelize the symbols involved. We can do this in *arithmetic*, with
no need of any set theory. Then we can state Con(ZFC) in its usual
mathematically sanitized form. (Note, however, that this is just a
surrogate for the first version of Con(ZFC) above, which speaks
directly of sentences and proofs.)
So: our grasp of Con(ZFC) *does not require or presuppose* any
understanding of sets or of set theory. It is a different matter, of
course, when one asks
"Could there be a proof of Con(ZFC) from any of those sentences
that you first distinguished for me, without telling me what they
were really about?"
Note that the ingenuous questioner still doesn't twig that the
distinguished sentences were the axioms for ZFC! The questions can be
understood without any need for an understanding of ZFC.
Of course, it is unlikely that the correct (negative) answer to the
question could be established to the questioner's satisfaction without
at some point getting him/her to grasp some (informal) set theory.
But we are now talking about the *statement of independence of
Con(ZFC) from ZFC*, not about Con(ZFC) itself. And since the *latter*
statement was the bone of contention between Steve and Joe (and
between Steve and Martin), I thought it worth sticking this
philosophical oar in at this stage.
It seems that the foregoing reflections establish that Con(ZFC) is a
finite combinatorial statement, requiring no set theory for its
grasp. It is a very complicated, ungainly monster of a statement (in
whatever "primitive" terms---symbols or G"odel numbers) but it is a
finite combinatorial statement nonetheless.
That people became interested in it and its provability or
non-provability within ZFC *only because of its importance for set
theory* is beside the point. That is just historical and psychological
gloss. The intrinsic semantics of the statement itself succeeds,
ironically, in insulating it from all "set-theoretic" influence or
content.
Having said all that, compare it now to Harvey's various finite
independence statements. I don't know how to *formalize* the
difference, but it is one that is palpably there. Harvey's independent
statements are a lot more immediate and intuitive. One can grant this
even while insisting that Con(ZFC) itself is still a finite
combinatorial statement.
Perhaps the matter should be expressed this way:
Con(ZFC) (like all the other "conjectures of Goldbach type" that
G"odel had in mind) is a finite combinatorial statement that *becomes
interesting and important* only once one appreciates the meaning and
importance of ZFC itself. By contrast, Harvey's finite combinatorial
statements seem (veridically) interesting and important *as
conjectures of ordinary mathematical practice as soon as one
understands them in their own terms*. Indeed, that is why Harvey
himself is so concerned to have these statements catch the imagination
of graph theorists, combinatorists, computer scientists etc. He wants
them to acknowledge the new independent statements as interesting
mathematical conjectures in their own right, with immediate and
intuitive mathematical content, *before* letting on to these
mathematical informants that settling the truth of these
innocuous-looking claims requires exceptional strengthenings of the
usual set theory in which virtually all of ordinary mathematics is
conducted.
Moreover, that Con(ZFC) turns out to be independent of ZFC is not all
that surprising to anyone familiar with *philosophical* problems
concerning self-validation. But that Harvey's simple finite
combinatorial statements turn out to be independent of *amazingly
strong* extensions of ZFC is very surprising indeed.
Torkel once described Harvey's independent statements as inducing
"slack-jawed wonder". But I think the slack-jawed wonder is perhaps
more appropriately directed at the discovery of their *independence
from very strong systems of set theory*, given their intuitive
mathematical content.
Neil Tennant
More information about the FOM
mailing list