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

[Joseph Shipman]

I won't argue with your historical account, but I ask for explication not of the the "FOL vs SOL" distinction, but of the "logical vs mathematical" distinction. 

The point of Logicism is that many statements which are regarded as "logical truths" can be shown to imply other statements which are regarded as "mathematical", and those mathematical theorems which can be so derived are appropriately regarded as "following from logic" and thus on a stronger epistemological footing.

The question then becomes "how much mathematics may be obtained in this way". That depends on what counts as "logical", and the two attitudes one may take on this are that a statement is logical by virtue of its form, or by virtue of being derivable in some deductive calculus. 

I claim that before 1929, the former was generally held, because there was a notion of semantic entailment distinct from deductibility, so that soundness and completeness were clearly distinct properties of logical deductive calculi (soundness meaning that only validities were derivable, where a validity is an open statement whose universalized form is true in all models or interpretations, and completeness meaning that all validities are derivable).

Godel's Completeness Theorem in 1929 showed FOL to have such useful and desirable properties that they became a desideratum for a system to be "logical", and emphasis was decisively shifted from entailment to deductibility. After his Incompleteness Theorems in 1930 SOL was therefore deprecated because the unknowability of the validity of some statements (not just CH, but those true AE arithmetical statements which inevitably escape any given recursively enumerable set of axioms for a deductive calculus), but this consignment of semantic entailment to irrelevance would have been unjustifiable to the original Logicists.

The result is that Logicism has been so broadly dismissed that what Dedekind, Peano, Frege, Russell, et al thought they were accomplishing is no longer comprehended and they are made to look foolish.

If we take the broader attitude that logic is allowed to include statements which are valid despite their validity being a consequence of semantic entailment so that none of our current deductive calculi allow us to know them to be valid, then Logicism becomes much more acceptable, because Logic Itself is regarded as an open-ended subject just like mathematics, in which new and more powerful axioms and deductive systems may be investigated and eventually accepted, and the distinction between logic and mathematics is less sharp. 

On this view, statements are logical by virtue of their form, but may imply mathematical propositions without themselves being knowable as validities, and mathematics may be used to justify logical calculi (thus we may regard any SOL statement which under set-theoretic semantics is implied by a theorem of ZFC to be a validity, and this is an acceptable "logical deductive calculus").

Those who disagree with my account here must give their own explanation of what exactly they consider Logicism to have accomplished, and may only deny the Logicist dictum that "most mathematics is derivable from logic" by demarcating a boundary within which lie all the mathematics which they accept as being derivable from logic and all the things that they regard the logicists as having actually accomplished, and outside of which lies "most mathematics".

Some possible positions that could be taken are, in order of increasing Logicism:

(0) even Euclid's theorem on the existence of arbitrarily large primes does not follow from "logical considerations alone" and the Logicists' work was mathematically trivial, all the more advanced theorems they reached depended on assumptions that they called "logical" but which we now know are "mathematical"

(1)  logic gets us PA but no further because the existence of an infinite set is a mathematical postulate that no acceptable form of 'logic' can give us, or 

(2) SOL with set-theoretic semantics allows us regard a great many mathematical propositions, such as CH or any arithmetical statement, as equivalent to logical statements, but I only accept as "derivable from logic" those mathematical propositions which follow from [insert a deductive calculus for SOL here that is weaker than ZFC but stronger than PA], or

(3) any theorem of ZFC which can be shown (in weaker-than-ZFC system X) to be a consequence of (SOL proposition Y) may be regarded as "following from logic".

(4) The axioms of ZFC, properly viewed, are really logical rather than mathematical and Logicism is completely correct.

I hope this crude list is not exhaustive and that some of you will have more nuanced positions that you are willing to explain here.

-- JS

Sent from my iPhone

> On May 25, 2016, at 1:34 PM, josef at us.es wrote:
> 
> I don't think I'm placing emphasis on deduction, and of course issues of definability are central to the whole matter. It's just that I place emphasis on logic being intimately related with inferential principles, with the analysis of explicit inference in our theoretical developments.
> 
> Talking about historical origins, I'm convinced that no logician in the 19th century (including Frege and Peirce) would have accepted as predicates those 'arbitrary predicates' which are essential to full SOL. The notion of arbitrary set can be tied historically and conceptually to the real numbers (e.g. as given by infinite decimal expansions) but it is unrelated to logical systems as conceived up to 1900 and even later.
> 
> As a matter of fact, even the early set theorists were very slow in isolating the idea of the powerset axiom -- Cantor only formulated it in 1897, and he had doubts about it! while you find it clearly formulated and accepted only with Zermelo and Russell around 1903. It is also a matter of historical fact that arbitrary sets were rejected by first-rate mathematicians like Borel, Baire, etc. (i.e. they denied that it was an acceptable notion in mathematics, not to mention logic!).
> 
> Zermelo was the first to resort to SOL in a substantial way, in his 1930 paper 'On boundary numbers and domains of sets', and this was mainly a defensive reaction against what he called Skolemism. Namely, the negative effects --to his goals-- of limitative results, the Skolem paradox.
> 
> The whole historical development from 1870 to 1930 suggests that the notion of arbitrary set came into the field purely from the side of analysis and the theory of real numbers. I conclude that the notion of a full powerset is a matter of mathematical content, not of the inferential relations that are relevant even to mathematics. (To use a way of speaking that I don't like so much, there was no basis for full SOL in our logical intuitions -- by reflection on predicates and relations and the ways they are employed inferentially, no one would have arrived at the full semantics.)
> 
> The situation changed with Tarski's introduction of set theory into metamathematics. This happened from around 1930, and there is evidence that Tarski himself may have been influenced by logicism (at least, his 1940 textbook often reads as if he were a logicist; see my paper 'Notes on types, sets, and logicism' mentioned before). Later on, model theory became increasingly successful and logicians increasingly came to train their intuitions on the basis of set theory and model theory. This in many cases --though of course by no means all-- has led them to the view that the full semantics is very natural.
> 
> Yet, if you introduce SOL as your basic logic, there is no way you can enforce the full semantics. See e.g. the very itneresting paper by Väänänen ('Second-order logic and foundations of mathematics' Bull. Symb. Logic, 7:504–520, 2001) where he writes, "If second order logic is construed as our primitive logic, one cannot say whether it has full semantics or Henkin semantics, nor can we say whether it axiomatizes categorically N and R." 
> 
> In this sense, the idea that there is substantial advance in issues of definition with full SOL turns out to be illusory. On the other hand, it is worrisome that according to the full semantics there is a predicate that determines a set of reals of cardinality Alef_1 and yet no one has a clue how to define such a set (i.e. how to define such a predicate). This kind of opaqueness and lack of explicit definability seems to argue against the system.
> 
> Another problematic symptom is this. Some people argue for full SOL but then say that, if you have doubts about AC, you may not employ it as a principle. This in effect is to deny the fundamental nature of the full semantics -- for if you're serious about it, you must then insist that AC is a logical principle. This is related to some your remarks.
> 
> Having said all of that, of course one can employ hybrid systems, mixing logic and set theory. My only claim is that full SOL is not to be regarded as the standard semantics for SOL.
> 
>  
> Best, Jose
> 
>  
> 
>> ------------------------------
>> 
>> Message: 2
>> Date: Tue, 24 May 2016 00:18:03 -0400
>> From: joeshipman at aol.com
>> 
>> 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
> _______________________________________________
> 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/20160527/310e06e8/attachment-0001.html>