SB logo
miley
en's Homepage

Is Second Order Logic Logic?

First-order predicate calculus, a logician might argue, is an effective way of symbolically representing those aspects of sentences in natural language pertinent to their use in arguments and related to the preservation of truth value when considered together. By first-order predicate calculus I mean that logical system involving the standard connectives - &, v, , --> - name letters - a, b, c, etc. - and quantifiers - for all and there is an. There is of course some debate as to whether identity - = - is to be included in first-order logic, but that is the subject for another debate, and I shall simply assume that it can be included, but that this assumption does not have a vast effect on the current discussion1.

I shall argue, however, that it is clear that there are groups of sentences which first-order logic is unable to correctly represent, and we use them quite happily in natural language. I shall go on to discuss whether extending our logic, allowing quantification of predicates as well as name variables, in order to allow ourselves to formally represent these sentence is worthwhile, or whether the various losses in doing so - moving to a logic which is incomplete and involving arguments which cannot be systematically assessed for validity - outweigh the gains, and whether we should, as Quine asserts, deny that these higher-order logics are logic at all.

In his article 'To be is to be a value of a variable (or to be some values of some variables)' Boolos discusses a number of these sentences. He focuses in various examples on terms like 'some', 'most' and 'the same number as' - showing that these sorts of 'mathematical' terms cannot be fully represented using simply first-order logic. Whilst in first-order logic it is possible to allude to specific numbers of objects having a property (for example 'There are two chickens') :

there is an x there is a y for all z ( Cx & Cy  & x = y & ( Cz --> z = x v z = y ) )

but it is not possible to make more general claims about the numbers of the objects, such as that there are the same (unspecified) number of one kind as another, or that there are more of one than the other. To do this would require not just a discussion of the objects belonging to the group, but a discussion of the group itself. This should be fairly clear - the number of objects belonging to a group must be  a property of the group, and not the objects themselves.

Perhaps the most famous sentence for logicians that cannot be expressed in first order logic is about that group with just one member - namely Leibniz's law - which states:

for allx for ally ( for all F ( Fx & Fy ) --> x = y )

If x and y share all properties, x is y.

It would seem an attractive prospect, therefore, to allow quantified predicates into our logical system, so that we are able to encapsulate these sorts of sentences. Particularly appealing is the idea that, if in discussing groups we can compare their size as well as simply their members, we might be able to capture the whole of mathematics in a second-order system.

In spite of the great advantages looming if we accept quantified predicates into the logical fold, Quine argues that we should not do so. We have already seen that one of the powers of second-order logic comes from its ability to discuss groups of objects together - and in fact this can reasonably be seen as being just what quantified variables do: to say ' there is an F Fx' is to say '...there is a characteristic defining a group which...'; to say 'for all F Fx' is to say '...every characteristic defines a group which...' - allowing us to discuss the sections of our domain which characteristics mark out. Therein, however, Quine argues, lies the rub - for in making claims about groups of objects we presuppose that such groupings exist. To discuss quantified predicates, Quine suggests, is to discuss sets, assuming them to be real and existent, and this is to multiply entities beyond necessity, at least for logic, which should presuppose nothing, relying rather on a priori definitions of its terms for the validity of its claims2.

Furthermore, Quine argues, logic is supposed to be topic-neutral, so the claim 'A; A --> B' then 'B' is as valid for sentences about rabbits running away from foxes as it is for sentences discussing paracetemol and headaches. Clearly, however, if second order logic is about sets, it isn't topic neutral - it's about, well, sets. We can't hope to substitute, say, people for sets in every sentence of second-order logic in a validity preserving way.

The mistake, says Quine, is to claim that 'Fx' can be unpacked as 'x has the property F', as if there are such things as 'attributes' which are what give some object that property. Surely, though, anyone who believes in Universals will agree that this is what 'Fx' really means, and would even claim to have good reasons why this is the only position one could hold (for example because their opponents would have no way to compare objects if there were not common, universal properties that the two objects either shared or did not). We should, however, be wary of an account that commits us to something as metaphysically heavy as Universals, and the supporter of second-order logic as logic should prefer to argue their case without resorting to such baggage-laden theses if at all possible.

Quine does, however, see a way out of the problems caused by interpreting second-order logic as discussing sets: namely to take it non-literally. He sets about constructing 'pseudo-sets' which follow the rules and positions of real sets, but are not to be interpreted as discussing something 'really out there in the world'. He defines a symbol 'Î' corresponding to the notion of membership (but not indicating membership of any actual set), and shows that the other set theoretic connectives can be defined simply in terms of this symbol, in combination with the standard connectives of first-order logic. By this method he argues that we should avoid the ontological excesses of set-theory, and use only 'pseudo-set-theory' which can be counted as true logic.

Boolos, in his article 'On second-order logic' argues, quite sensibly in my mind, that the actual question being asked, of whether second-order logic is logic, is simply a 'quasi-terminological' question, and that 'It is of little significance whether second-order logic may bear the (honorific) label 'logic' or must bear 'set theory''. He is also quite right, in my mind, to dismiss Quine's objection that quantified variables can only stand in the places where a name might stand, and thus that we should not quantify predicates. Clearly first-order quantified variables stand in the places where names might stand, but this is precisely because in first-order logic only names (or perhaps rather the things to which the names refer) are quantified. In second-order logic, where we allow quantified predicates, clearly we are going to have quantifiers appearing in positions where previously they could not. Surely we should allow this, going with the natural language example which is perfectly able to establish where these new quantifiers may appear, and what they would mean in these positions, rather than following Quine's example and denying them outright, simply because when we extend our language to include new sets of symbols, the language involves unfamiliar sets of symbols.

The meat of Quine's argument, therefore, seem to be in his claim that second-order logic presupposes sets. Boolos takes issue with this claim - suggesting that whilst it may seem that second-order logic alone is guilty of forcing sets upon us, there are implicit assumptions even within first-order logic which require at least a number of sets exist. If we take for allx ( x = x ) to mean 'Everything is identical with itself' and believe it to be valid (i.e. true on every interpretation) we must be assuming a non-empty domain. Boolos himself, however, accepts that if we unpack for allx ( x = x ) more cautiously, as 'Everything in the domain is identical with itself' we have a valid sentence which does not assume there is anything in the domain. He asserts also that, since the truth of a sentence even in first-order logic invariably depends on the domain, we should subscript our quantifiers to state to which domain they allude - and yet it seems to me this assumes just what he is trying to prove: most logicians would take issue with the claim that all logical truths are dependent on the domain, and it is certainly the hope of logic that it is able to assert truths, such as modus ponens for example, which are true regardless of the domain in which we are debating. Furthermore, it is all very well claiming that truth-value depends on the domain of discourse, but what Quine is objecting to is that it seems to be the case with second-order logic that meaningfulness depends on the domain - namely that sentences of second-order logic don't have any meaning in domains of anything but sets.

Boolos does, however, take issue with this claim that second-order logic's lack of topic-neutrality is a shortcoming, again by suggesting that this is the case even with first-order logic. First-order logic, he claims, is not topic-neutral because it is about the notions of '&', 'v', '', '-->, 'for all', and 'there is an'. Whilst this might initially seem a tempting line to take, I don't think that realistically it is a terribly profitable one, in that I don't think it's true. Whilst validity and truth may be defined in terms of, and discussed using these symbols, it is the intention of logic that they are the means and not the end - it is the sentences and truths expressed that are the interest of all but the meta-logician. It might seem initially to be a claim like Quine's about variables in second-order logic occurring in the wrong positions, but I think this is not so, to suggest that whilst first-order logic may involve connectives and quantifiers, it is not at that level that the work of logic is done, instead truths are expressed in the places taken up by sentences. Whilst we might slot entities in around connectives to discuss them, they themselves are not the topic of discussion, and since they are simply symbols, defined in a particular way, they do not seem to have ontological weight, and thus are a vehicle for expression of truth, rather than expressing truths simply by being used, as Quine would assert the use of second-order logic does.

Is this whole problem to be escaped then, simply by taking Quine's line, and using pseudo-set-theory rather than the genuine article? I don't think so, and I am somewhat confused as to why Quine might think so. If indeed second-order logic can be interpreted pseudo-set-theoretically it isn't clear how Quine's claim that it commits us to set-theory in the first place can stand up. It seems to be a total about turn for him to claim that there is an interpretation of second-order logic free of the ontological claims of set-theory, since then there is no reason for him to have ever asserted that these ontological claims would be a burden for second-order logic.

Overall, therefore, must I agree with Quine's assertion that second-order logic is not logic? Well, no. As Boolos argued as soon as he entered this argument, the way the claim is phrased seems to make it simply a trivial terminological dispute - one side can say that the word logic should include higher-order logics, the other side may want to use the word simply to refer to first-order logic, and there can be no serious argument which should decide how a word can be used. The second-order logician (evidently open to new experiences!) should be perfectly willing simply to coin a new term - say 'bogic' - to refer to his system, and the argument could be settled that way. The issues, however, of why we might decide to accept or refuse second-order logic's entrance into logic is an interesting one, focusing more on value-laden judgments of whether we should, effectively, taint our perfect, complete logic with this new-fangled, somehow less rigorous kind - and it is this debate with which Boolos engages.

In the end, however, I think Boolos comes to the right conclusion. He points out that Quine's intuitions seem in the end to come down to an unwillingness to accept second-order logic as logic because of its incompleteness, and that, whilst this is an important consideration, it isn't clear why we should draw the line here. We have already sacrificed total decidability in order to have a fuller, more abundant logic than monadic logic in our commitment to first-order logic, and this seems to be as great a loss as that of completeness would be. Obviously a large part of it comes down to how much we get back in return for this further loss - and yet it seems very plausible that the gains are enormous, and that the wealth of sentences that can be formulated using second-order logic is great enough as to justify these setbacks.

~~~~~~~~~~~~~~~~

1If the question of whether identity is part of first-order logic does enter the debate it is presumably only as a matter of degree. Whilst first-order logic is even more severely limited if identity is not allowed, the matter of the serious inconveniences which Quine highlights will still only appear upon the introduction of quantified predicates.

2Perhaps a more than contentious claim, and yet it seems fair to argue that a great advantage of logic is that it never appears to appeal to things beyond itself, rather laying its own foundations and then walking on them.

17/11/2001