[FOM] First- Vs Second-Order Logic: Origins of the Distinction?
josef at us.es
josef at us.es
Wed May 25 13:34:11 EDT 2016
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
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.
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the FOM