Philosophy 3340
Symbolic Logic II

The Project
Fall, 2011

This page contains information on the final project. This will most likely be a paper, but there are a variety of different approaches you could take to the paper, which could explore the philosophical implications of a metalogical result; explain and interpret a metalogical theorem other than the ones we are covering in class; or do additional research on a theorem we will cover, and give a different proof or an explanation from a different angle. I am also open to the idea of a "literate programming" project, integrating a program with a paper describing its motivations and significance. If you did such a project, however, the "paper" part of the project should still be approximately 10-15 pages, either as a separate paper or as comments integrated into the code. (As intriguing as the idea of integrating the two is, it's probably safer to write the paper separately.) Why would you want to do a programming project if you need to write a substantial paper anyway? Well, you might not want to, but one reason would be that the paper should be easier to write if you're explaining and discussing the significance of a program you've written.

Most of the suggestions below are in the "philosophical implications" category.

Format:

3000 - 4500 words (approximately 10-15 pages).

The paper must be turned in electronically (simply attaching it to an email is the simplest way).

The paper should strive for the following virtues: clarity at every level (sentence, paragraph, section, paper as a whole); argumentative rigor.

The paper must be on a topic closely related to our class, and should make use of class readings in addition to outside research.

Due:

A proposal is due no later than Monday, October 24. The project itself is due Wednesday, November 30.

Possible Topics:

1. Does Gödel's incompleteness theorem show that Artificial Intelligence cannot match human reasoning abilities? You would want to read selections from Penrose, Shadows of the Mind, and an online discussion of this book by various philosophers with a reply by Penrose. I can offer references to many further resources if you're interested.

2. Does the Löwenheim-Skolem theorem show that metaphysical realism is false, and that words in a natural language cannot refer to metaphysically real entities? You would want to read Putnam's essay "Models and Reality," and perhaps his less technical presentation of similar ideas in his book Reason, Truth, and History along with responses to Putnam's arguments, e.g. David Lewis's excellent "Putnam's Paradox" (Australasian Journal of Philosophy 62 (1984), pp 221-36). Again, lots of other possible sources; I can give a more complete list to anyone who's interested.

3. Logicians like to start proofs by saying things like "Let a be any arbitrary element of set A . . ." (sound familiar?). This is usually interpreted along the lines of boxing a constant for use in Universal Introduction in Barwise and Etchemendy's system. But Kit Fine has suggested that it would be better to simply accept the idea that there are strange objects that are "arbitrary" -- for instance an object that does have the property of being an element of A but does not have the property of being identical with any particular element of A. Might be interesting to explain and evaluate this idea. See Fine's book Reasoning with Arbitrary Objects (Oxford: Basil Blackwell, 1985). There is a shorter article that preceded the book: "Symposium: a defence of arbitrary objects: I," Proceedings of the Aristotelian Society Supplementary volume 57: 55-77 (1983).

4. Time permitting, we may discuss Turing Machines as an abstract model of computation. It is an interesting and surprisingly difficult issue exactly how these abstract models (and other models of computation) relate to the real world: when should we say that a physical process is an implementation of an abstractly defined computation? John Searle (in The Rediscovery of the Mind) and Hilary Putnam (in Representation and Reality) have suggested that any sufficiently complex physical system implements pretty much every abstractly defined computation. (Searle's famous example is that the wall behind him implements the Wordstar program.) David Chalmers has proposed an interesting account of implementation that seems to avoid this conclusion. (See the first two papers at http://www.u.arizona.edu/~chalmers/ai-papers.html, or the discussion in his book The Conscious Mind.) You could defend or criticize an account of implementation. (I have lots more references if you'd like them.)

5. If you wanted to do some sort of programming project (with a paper describing the project and its significance), there are a lot of possibilities. Examples: write functions to encode formulas as Gödel numbers and decode Gödel numbers into formulas; then use these functions to write more complex functions such as bool Term(int n) which would return true if n is the Gödel number of a term, and false otherwise. (The encoding/decoding part is pretty trivial and should be knocked off early in the process; the interesting part would be things like the Term function.)

Another idea along these lines would be to implement a Turing machine (fairly trivial) and then write Turing machines that implement the basic building blocks of recursive function theory (more interesting).

Another project might be to implement a first-order language and its semantics. In particular you could do something like an implementation of Q or Peano Arithmetic. You could implement the semantics: construct a data type that represents structures, which should include a domain and assignments of interpretations to constants, predicates, and function symbols, and then implement a function which uses a structure to interpret an arbitrary sentence of the language. You could use this to illustrate some points about e.g. Q: for instance, to show that there is a nonstandard model of Q on which it's false that Ax (0 + x = x). (See Smith pp. 56-57.)

6. Some possible sources of ideas for other topics:  (1) Torkel Franzen, Gödel's Theorem: An Incomplete Guide to Its Use and Abuse. Very nice (and quite accessible) book which includes both good discussion of the theorem and a critique of a lot of loose and fuzzy (or just plain wrong) attempts to apply it to various areas. (2) John Etchemendy, The Concept of Logical Consequence. Etchemendy's a very clear writer, and this book raises interesting philosophical issues about the idea of logical consequence. (Yes, this is the Etchemendy from Barwise and Etchemendy.) (3) Mark Sainsbury, Logical Forms: An Introduction to Philosophical Logic. Mostly involves philosophical issues about the attempt to use logical machinery to understand natural language. (4) Paul Benacerraf and Hilary Putnam, eds., Philosophy of Mathematics: Selected Readings. Includes articles on the ontology of mathematical objects, the concept of set, and the idea of mathematical truth. The book was published in 1983, so it's not exactly up to the minute, but it's still a very useful resource. (5) Jean van Heijenoort, From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931. The giants in their own words: papers by Frege, Peano, Hilbert, Skolem, Gödel, and others.