[FOM] First- Vs Second-Order Logic: Origins of the Distinction?

Tue May 24 00:18:03 EDT 2016

It seems to me that you are placing too much emphasis on deduction and not enough on definition. If part of being "logical" is being "deducible from nothing" then set-theoretic semantics does run into the issue that many of the statements we would like to know the validity of are equivalent to undecidable mathematical propositions. But in actuality any version of logic that you define will need a deductive calculus in order to derive validities, and you don't get a deductive calculus for free, an algorithm must be given. So this is not a difference of kind but a difference of degree, unless you also require that a "purely logical" deductive system must have a recursively enumerable set of validities.

If you relax the "r.e. set of validities" requirement, then I can adopt set-theoretic semantics and say that many statements of mathematical interest are equivalent to statements of logic, which don't happen to be derivable in the deductive calculi we use. This doesn't make the statements any less "logical".

I prefer to think about it this way: those statements which are equivalent to statements of SOL with set-theoretic semantics are statements about which there is a "fact of the matter", even if it is beyond our ken, while statements which cannot be shown equivalent to SOL statements in this way may be regarded as undetermined. This is as far as logicism can be taken. You can argue about axioms for deduction (and certainly any logical statement which, under set-theoretic semantics, is equivalent to a theorem of ZFC, is a fair candidate for inclusion as an axiom), without denying the logical nature of the statements. What's so bad about "entangling logic with mathematics", anyway? The point of logicism is that most mathematics is just logic, and to deny that logic is mathematics seems silly because the concept of a deductive calculus requires mathematical investigation in order to explicate it properly and understand its properties. 

If you are going to require logical validities to form a recursively enumerable set in order for a system to qualify as a "logic", then you are committed to saying that certain statements of a very simple form (such as "this multivariate polynomial equation has no solution in integers") can be truths that are not equivalent to logical truths, while admitting that the nonexistence of integral solutions to other polynomial equations follow from pure logic because their proofs use extremely rudimentary principles.

If you disagree, then please demarcate a line somewhere between "no integer square is twice a different integer square" and GCH and that you think represents a reasonable boundary for the statements of mathematics which are equivalent to logical propositions.

-- JS

-----Original Message-----
From: josef <josef at us.es>
To: fom <fom at cs.nyu.edu>
Sent: Mon, May 23, 2016 11:23 pm
Subject: Re: [FOM] First- Vs Second-Order Logic: Origins of the Distinction?

Dear Joe Shipman:
I'm happy to elaborate a bit, but I'll keep it short because I fear most of the arguments are already known. A paper of mine on this topic, which is about to come out, can be found here:
https://www.academia.edu/25511815/On_the_Semantics_of_Higher-order_Logic
So, let me briefly try to summarize the main point.
1. Notice something important: I don't say that SOL is not a logical system, as you seem to suggest -- quite the contrary! I was talking only about "full" SOL. What I find to be a remnant of logicism is the idea that full SOL is the standard semantics for SOL. And you're right, I was also intimating that I find something objectionable there.
2. The question with SO quantification is -- given a domain D of individuals, what is the totality of predicates over D? (Let's reduce the question to this, for simplicity, letting relations aside.) Notice that in practice, when we work with actual mathematical theories, the predicates and relations we consider are certain concretely given ones, plus of course anything that can be defined from those. An example is Hilbert, Foundations of Geometry.
3. There's nothing objectionable in moving from predicates to their extensions (sets), but it's not obvious that we can define predicates simply to be the correlates of sets! The situation may not be symmetric. One must take carefully into account that, in set theory, we work with arbitrary infinite sets.
In particular, when the domain of individuals is infinite, for any random collection of individuals, full SOL decrees the existence of a predicate applying exactly to them (i.e., to that arbitrary collection of individuals). This is awkward. It runs against the guiding ideas that logical principles ought to be neutral concerning questions of existence, and topic neutral.
4. The main point is simply that arbitrary sets are a topic for set theory to study -- and a topic that is far from clear. It is natural to expand quantification to predicates and relations. There's no reason to insist on FOL as the only logical system. So far, so good; but then comes the 'logicistic' addition, an extra ingredient from pure mathematics: That natural idea of going second-order is  mixed with the notion of a full powerset of the domain, taken from set theory -- the quasi-combinatorial idea of arbitrary set.
5. The main issue, as I see it, is not a technical one. The main issue concerns the philosophy of logic and the kinds of epistemological implications people (sometimes) want to extract from logical results.
I propose that we should stop calling the full semantics "standard". Call it anything else, e.g. the set-theoretic semantics. (This is not merely a matter of words, since the word "standard" brings with it a normative connotation.) Henkin semantics is closer to being standard.
Of course one may consider full SOL for certain particular purposes, e.g. for doing work on model theory, but one should be clear that this is not a system of pure logic.
Notice however that my position is not Quinean. It seems that Quine was still too imbued in the ways of thinking of logicism, so that he unduly identified SOL with its full set-theoretic version. This is a mistake. 
Best wishes,
Jose

 ----------------------------------------------------------------------

 Message: 1
 Date: Sat, 21 May 2016 19:18:48 -0400
 From: Joseph Shipman <JoeShipman at aol.com>
 To: Foundations of Mathematics <fom at cs.nyu.edu>
 Subject: Re: [FOM] First- Vs Second-Order Logic: Origins of the
     Distinction?
 Message-ID: <897FB754-081D-48A7-B6EE-06339A8A1BCC at aol.com>
 Content-Type: text/plain; charset="utf-8"

 I agree that an important motivation for SOL is logicism, but your use of the connotationally loaded descriptors "insist" and "remnant" suggests that you think there is something wrong with this much logicism; please elaborate.

 -- JS

 Sent from my iPhone

On May 21, 2016, at 7:57 AM, josef at us.es wrote:

 Dear Richard:

 the question how first-order logic became the paradigm logical system was the main topic of a paper of mine, 'The road to modern logic -- an interpretation' (BSL 2001), see http://www.math.ucla.edu/~asl/bsl/07-toc.htm. I argued that simple type theory was taken to be the main logical system by 1930, and I analyzed the main reasons for the move to FOL.

 Also relevant to this is another old paper, 'Notes on types, sets and logicism, 1930-1950' (Theoria 1997), which I can send you if you'd like. Here the main issue was to analyze reasons for the abandonment of logicism in the 1940s.

 Concerning second-order logic, let me also indicate my current view, which you may find provocative. I'm convinced that insistence on full SOL is the last remnant of logicism in foundational debates. I have argued for this in several places, a consequence being that we should stop calling "standard" the full powerset semantics.

 Best wishes,

 Jose

_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160524/652cc6e8/attachment-0001.html>