Second-order logic and Gödel’s first incompleteness theorem (Frances)

That’s a very impressive title for a blog entry, but I promise that things will not get very complicated in what follows. For I am no logician. I’m not even a philosopher of logic. So, I don’t know much about logic. But I know just enough to be confused about something having to do with second-order logic and Gödel’s first incompleteness theorem.

Let L be the formal first-order language with a name for zero and function symbols for the successor function, addition, and multiplication (and no other non-logical symbols). So L is a pretty simple formal language. Let N be the interpretation of L that has as its domain the set of natural numbers {0, 1, 2, …} and assigns zero to the name ‘0’, addition to the function symbol ‘+’, etc. So N is the natural way to interpret L. Arithmetic is the set of sentences of L that are true under N. So, arithmetic is a set of sentences of a formal language, where each sentence is most naturally interpreted as an arithmetic truth. This will be an infinite set.

Arithmetic counts as a theory of L because it is “closed under logical consequence”, which means that any sentence of L that is entailed by the sentences in arithmetic is in arithmetic. Arithmetic contains all its logical consequences; that’s what makes it a “theory”.

Now a theory T in language L is decidable when there is an algorithm for deciding whether any given sentence of L is a theorem (member) of the theory. So a theory T in L is decidable when there is some algorithm that when fed a sentence S of L will tell you in a finite number of steps whether or not S is in T.

Roughly put, a theory T is axiomatizable just in case everything in T is a logical consequence of some nice subset of T. The nice subset of T generates, so to speak, everything in T (just like how the central Euclidean claims generate all the truths of plane geometry). The member sentences of the nice subset are axioms of T.

The subset could be infinite! But even so it has to be nice. That means: there has to be an algorithm that when fed a sentence of L will tell you in a finite number of steps whether or not the sentence is one of the axioms. That is, the set of axioms has to be decidable.

The famous consequence of Gödel’s first incompleteness theorem is that arithmetic isn’t axiomatizable. This is surprising! You’d think it wouldn’t be that hard to write down a nice set of axioms (say, the Peano axioms) for generating all the truths of arithmetic. But it can’t be done.

Now suppose we add second-order quantifiers and variables to L. Now let arithmetic* be the set of first-order and second-order sentences of L that are true under N. Arithmetic* contains everything in arithmetic plus some more arithmetic truths (the second-order ones).

The cool thing, in my opinion, is that arithmetic* is axiomatizable. You can write down one long sentence that generates, through logical consequence, everything in arithmetic*. So when you hear someone say ‘Gödel famously showed that arithmetic isn’t axiomatizable’, you should say to them ‘Wait a damn minute buddy. First-order arithmetic isn’t axiomatizable, but second-order arithmetic is’. So you can write down just one relatively simple sentence that generates all the (first-order) truths of arithmetic—-but it will generate a whole bunch of other arithmetic truths as well, the second-order ones.

I take it that not that many non-logicians and non-philosophers of logic are aware of that result. Hopefully I’m right about it and as a consequence this blog entry is worthwhile.

But now we come to my question: why is it thought to be such a big honking deal that arithmetic isn’t axiomatizable? I take it that people who know about these things think the second-order axiomatization is not terribly significant. But why?

I guess some people are allergic to second-order logic, but I don’t know anything about that issue. What if you think second-order logic is a-okay?

Is the problem connected to this: whereas there is an algorithm that when fed a first-order sentence S of L that’s logically true, will tell you in a finite number of steps that S is indeed logically true, but there is no algorithm that when fed a second-order sentence S of L that’s logically true, will tell you in a finite number of steps that S is indeed logically true? If so, why does that matter so much?

Reasoner 1(3)

The third issue of the Reasoner just hit the e-stands. Here's the TOC:

"Pierre May be Ignorant but He's Not Irrational"
Jesse Steinberg (UC-Riverside)

"Free Will and Lucky Decisions"
Gerald Harrison (University of Bath)

"United States v. Shonubi: Statistical Evidence and 'The Same Course of Conduct' Rule"
Amit Pundik (Law, University of Oxford)

"Williamson on Counterpossibles"
Brit Brogaard (University of Missouri)
Joe Salerno (St Louis University)

"Mathematical Blogging"
David Cornfield (Max Planck Institute, Tübingen)

"Does Direct Inference Require Pollock's Principle of Agreement?"
Stephen Fogdall (Schnader Harrison Segal and Lewis LLP)

"The Pirahã Language, the Language Template, and the Mind"
William Abler (Geology, The Field Museum)

Williamson on Counterpossibles

Lewis/Stalnaker semantics has it that all counterpossibles are vacuously true. Non-vacuism, by contrast, says that the truth-values of counterpossibles are affected by the truth-values of the consequents. Williamson, in his Hempel Lectures, objects to non-vacuism. He asks us to consider someone who answered `11' to `What is 5 + 7?' but who mistakenly believes that he answered `13'. For the non-vacuist, (1) is false, (2) true:

(1) If 5 + 7 were 13, x would have got that sum right
(2) If 5 + 7 were 13, x would have got that sum wrong

Williamson is not persuaded by the initial intuitiveness of such examples:

... they tend to fall apart when thought through. For example, if 5 + 7 were 13 then 5 + 6 would be 12, and so (by another eleven steps) 0 would be 1, so if the number of right answers I gave were 0, the number of right answers I gave would be 1. (Lecture 3)

That's the whole argument. It isn't initially clear what the full argument is, but Brogaard and I commented on our abbreviated version of it in "Why Counterpossibles are Non-Trivial" (The Reasoner v.1, no. 1). Alan Baker's critique (The Reasoner v.1, no. 2) of our paper has prompted us to say more. Here's what we think.

Williamson's conclusion is this:

(3) If the number of right answers I gave were 0, then the number of right answers I gave would be 1.

The implicit reductio must be this: If (3) is true, then (1) and (2) are true --- contrary to what the non-vacuist supposes. For if I gave 0 right answers (in close worlds where 0=1), then I also gave 1 right answer (in those worlds). Hence, I got the sum right and wrong (in those worlds).

Williamson's abbreviated eleven-plus-one steps must be these:

(i) If 5 + 7 were 13, then 5 + 6 would be 12
(ii) If 5 + 7 were 13, then 5 + 5 would be 11
...
(xi) If 5 + 7 were 13, then 5 + -4 would be 2.
(xii) If 5 + 7 were 13, then 5 + -5 would be 1.

Getting to (3) from here, however, is trickier than Williamson supposes. The argument must be that any world where 5 + -5 = 1 is one where 0 = 1, substituting `0' for `5 + -5'. Hence,

(xiii) If 5+7 were 13 then 0 would be 1.

Therefore, if 5+7 were 13 (and I gave 0 right answers), then (since 0 would be 1) the number of right answers I gave would be 1.

The argument is unsuccessful. First, substituting `0' for `5+5' is illicit, since as Williamson himself notes the non-vacuous counterfactual is hyperintensional. Hyperintensional operators do not permit substitutions of co-referring terms salva veritate.

Incidentally, Williamson takes the hyperintensionality to be a mark against non-vacuism, because substitution is valid in more ordinary counterfactual contexts. However, we need not throw out the baby with the logically ill-behaved bath water. This sort of substitution preserves truth at every world on every standard model. Only the counterpossible context (i.e., the counterfactual context whose accessibility relation invokes impossible worlds) are hyperintensional. Our logical principles can be restricted accordingly.

A second problem for Williamson emerges in steps (i) through (xiii). These conclusions hold, if the game is to evaluate the consequent of each at deductively closed worlds where 5+7 = 13. But if there are non-trivial counterpossibles, the relevant worlds of evaluation must not be deductively closed---lest they collapse into the trivial world where everything is true.

Once we deny deductive closure, Williamson's reasoning fails. Let the following world, (W), be non-deductively closed:

(W) {5 + 7 = 13, the number of right answers I gave wasn't 1, the number of right answers I gave was 0, ... }

In contexts where W-worlds are closest, (2) is true and (1) false, as the non-vacuist predicts. For Williamson's argument to succeed, the relevant impossible worlds in which I gave 0 right answers and 1 right answer must always be closer than the relevant impossible W-worlds. This hasn't been shown. Indeed, (W) is closer to the actual world than Williamson's envisaged impossible worlds, since (W) is constituted by fewer explicit contradictions.

UPDATE: changed 'explicit' to 'implicit'

New Essays on Knowability

I just updated the page for the volume that i'm editing, New Essays on the Knowability Paradox. The introduction and bibliography have been substantially revised. A contributor list and contents page has been added. I also included a link to the Appendix to Alonzo Church's "Referee Reports on Fitch's 'A Definition of Value'", which i put together with Julien Murzi. Updated my own contribution as well (Essay 3). There are links to other contributions by authors who have made their papers electronically available. Will be glad when this thing is finally published.

Philosophy and Common Sense (Frances)

Not every philosophy professor takes philosophy seriously in the sense that she thinks that some purely philosophical theories that go against common sense have a good chance to be true. These philosophers respect anti-commonsensical theories, in that they admit such theories are very important in the pursuit of philosophical understanding. But they also think that there is no real chance that they are true. If you have a valid argument based not on scientific but purely philosophical reasoning, and that argument concludes with something against cross-cultural and timeless common sense, then at least one of the premises isn’t true, or so they say. It might be tremendously difficult to identify the mistaken premise, but we can start our investigation off assuming that our assumption that the conclusion is false is safe. These philosophers take philosophising seriously, of course, but they don’t take seriously the idea that purely philosophical (so not empirical, not mathematical) theories have a good chance at overthrowing parts of common sense. Here is a good sample of anti-commonsensical philosophical theories.

1. 2 + 2 doesn't equal 4. (No positive mathematical truth.)
2. No vague claims are true. (Sider and Braun 2007.)
3. There are no people. (Peter Unger.)
4. Thermometers have beliefs. (Certain information-fanatic philosophers.)
5. There are no chairs. (No non-living composite physical objects exist.)
6. Stones are not solid objects. (Inspired by Sir Arthur Eddington.)
7. No one has ever had a dream. (Norman Malcolm at one point.)
8. Cats don’t feel any pain when their paws are cut off. (Descartes.)
9. The world could not have turned out even a bit better than it actually is. (Leibnizians.)
10. It isn’t wrong to torture young children purely for fun. (No moral truths.)
11. Kant didn’t live after Descartes died. Alternatively: Nothing ever happened in the past. (Time doesn’t exist; isn’t “real”.)
12. No one has ever done anything because they wanted to do it. (Various reasons.)
13. Rocks have mental characteristics. (Idealists.)
14. There could be two wholly physical objects that during their entire existence occupied the very same space and were composed of the very same particles in the very same manner. (Some contemporary metaphysicians.)
15. Other statue-clay claims.
16. Supervaluationism stuff about true disjunctions without true disjuncts.
17. Dialethicism; true contradictions.
18. Taking one cent from a rich person can make them no longer rich. (Epistemic theory of vagueness.)
19. No one is free to do anything. (No one is free, period.)
20. No one knows anything, or much of anything. (Radical sceptics.)

I hate that attitude. I wonder: what percentage of contemporary philosophers are allergic to anti-commonsensical theories?