[FOM] second-order logic once again

Kevin Watkins kevin.watkins at gmail.com
Tue Sep 4 14:48:50 EDT 2012


Robert,

Let me try to answer your question from my own point of view.  (I am
not really an expert, but I might learn something from how the experts
on this list, including yourself, react to my answer.)

I would describe the situation as follows:

1. The model theory of second-order logic should be investigated
within the background theory (meta-theory, if you like) of ZFC.  This
is because the consensus among mathematicians is that any mathematical
object whatsoever should be investigated within the background theory
of ZFC.

2. There is no difficulty in defining in ZFC what is meant by a
(standard) second-order model, and whether a second-order sentence is
satisfied by a second-order model.

3. There is no difficulty in defining in ZFC what is meant by a valid
second-order sentence--it is a sentence satisfied in any model.  The
legitimacy of "any model" is supplied by the giving of a definition,
in ZFC, of "model" (point 2).

4. So a first-orderist would say that the set of second-order
validities is in fact "determinate" in the sense that there is a ZFC
definition of second-order validity.

5. The incompleteness theorem says that for any sound and effective
deductive system for second-order logic, some validities are not
deduced.

ZFC itself is indeterminate in the sense that it can't say everything
there is to be said about sets, or even about the natural numbers.
But this is no obstacle to using it to characterize second-order
(standard) validity or state or prove the incompleteness theorem.  The
incompleteness theorem is true on any understanding of sets that
validates ZFC.  The fact that there are multiple such understandings
(e.g. CH true, CH false) is no impediment.  And if it were (on your
understanding), wouldn't the whole enterprise based on first-order ZFC
would be doomed much sooner, even before we got past arithmetic? There
would be no reason to go as far afield as the model theory of
second-order logic to demonstrate it.

So to the extent that there is disagreement between most
first-orderists and second-orderists, I would be surprised if the
disagreement is centered around the legitimacy of the notion of
second-order validity or the way the incompleteness theorem should be
stated and proved.

Best,
Kevin

On Mon, Sep 3, 2012 at 5:27 PM, Robert Black <mongre at gmx.de> wrote:
> As everyone on this list knows, the completeness theorem fails for
> second-order logic.
>
> Those of us who, like myself, are card-carrying second-orderists can say
> what this means: the set of second-order validities, *a perfectly
> well-determined set of formulae*, is not r.e. (indeed not even remotely:
> it's not definable in nth-order arithmetic for any n and so on and so on).
>
> But suppose you're not a card-carrying second-orderist, so you don't think
> there's a perfectly determinate 'set of second-order validities'. (Perhaps
> you balk at the consequence that CH must have a truth-value.) How do you
> state the incompleteness theorem?
>
> Of course any r.e. set is determinate, so if the set of second-order
> validities isn't determinate, it can't be r.e.. But surely that's not what
> the incompleteness theorem says.
>
> So what does it say? (In your answer, don't use expressions like "any model"
> unless you're sure they aren't presupposing the determinacy of second-order
> logic).
>
> Robert
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom


More information about the FOM mailing list