Provide an example of a use of “If . . . then . . . ” in English that no one would recommend analyzing with the material conditional.

In this paper, you are required to answer the questions that carry the following points:

• the inversion theorem

• the concepts of CPC and IPC

• theorem 1, 2, and 3 and their relationship 

Instructions 

Provide a thorough but concise answer to each question. Consult your own notes and memory but no other sources of information. Submit your answers to me the day you write them through e-mail as a PDF file.

1.

(a) Provide an example of a use of “If . . . then . . . ” in English that no one would recommend analyzing with the material conditional.

(b) Why might one have misgivings about analyzing any English “If . . . then . . . ” construction with the material conditional? Do these grounds foster similar misgivings about the intuitionistic conditional/implication construction?

(c) Suppose one accepts the natural deduction elimination and introduction rules for the propositional connectives ∨, ∧, ¬, and ⊃ as well as the validity of the law of excluded middle. Why might one be wrong in that case to harbor misgivings about the material conditional?

2.

(a) Explain how the inversion theorem is used in the proof of the completeness of the classical, propositional sequent calculus?

(b) Does inversion play a similar role in the proof of the completeness of intuitionistic propositional logic with respect to Kripke frames? Explain.

3. Logical inference is sometimes described as valid in case it is truth preserving. Why is this not a reasonable way to think of inferential validity in the setting of intuitionism? What, if not truth, is intuitionistic inference tracking? Does minimal logic track the same thing or something yet different?

4.

In some of his early writing, while railing against classical logic and specifically the law of excluded middle, L.E.J. Brouwer proposed that we stop thinking of “logical principles” as “a priori laws governing fetish-like concepts and their linkages.” Think of them instead, he suggested, as “practically reliable” means of transitioning from one verifiable statement to another. Such principles, he suggested, are validated a posteriori by observing that [w]hen one applied these principles purely linguistically, i.e. derived linguistic expressions from other linguistic expressions with their help, without thinking about the mathematical contemplations indicated by these statements, it turned out that the principles proved themselves, i.e. it was found that every statement obtained in this way was capable of triggering an actual mathematical contemplation which turned out to be practically. “identical” for all linguistically raised men . . . .

Building on this idea, Brouwer further suggested that the body of valid logical principles be considered unfixed and ever evolving: Any time you notice that a principle is a reliable way to obtain, starting with established truths, statements that turn out also to be true, you should accept it as a principle of logic as valid as any other. Why might this theoretical attitude make the attribution of intuitionistic logic to Brouwer particularly problematic?

5.

In 1931 Godel announced the most often discussed result in 20th Century logic: the ¨ incompleteness of first-order arithmetic. The result says that given any recursive set S of first-order formulas, there will be a true first-order sentence in the language of arithmetic that is not first-order derivable from S. But Godel’s 1929 completeness theorem says that from any set ¨ S of first-order formulas it is possible to derive all first-order logical consequences of those formulas. Why do these results not contradict one another?

6.

At the height of 20th Century nominalism, several luminaries, including Henri Poincare and ´ David Hilbert, advanced an austere doctrine of being. Hilbert is a particularly interesting case. In step with Poincare and others he declared that mathematical existence amounts to ´ nothing more than the consistency of a system of axioms: “If the arbitrarily given axioms do not contradict one another,” he wrote to Frege, “then they are true, and the things defined by the axioms exist.” At the same time Hilbert was the only person who seemed to recognize that the completeness of quantification theory was an interesting and open question. In his 1917 lectures he wrote: “whether [the first-order predicate calculus] is complete in the sense that from it all logical formulas that are correct for each domain of individuals can be derived is still an unsolved question.” What is the relationship between these declarations?

7.

(a) Explain a sense in which CPC is stronger than IPC.

(b) Explain a sense in which IPC is stronger than CPC. 8. Theorem III of Gentzen’s 1932 paper states: “If a nontrivial sentence q is provable from the sentences p1, . . . , pv, then there exists a normal proof of q from p1, . . . , pv.” Gentzen’s comments about this normalization result are interesting: This follows at once from theorems I and II together. The theorem can also be obtained directly without reference to the notion of consequence by taking an arbitrary proof and transforming it step by step into a normal proof. The reason for the approach chosen in this paper [i.e., proving III from I and II] is that it involves little extra effort and yet provides us with important additional results, viz., the correctness and completeness of our forms of inference. (p. 38)

(a) How does Theorem III follow from Theorems I and II?

(b) How could one devise a simple proof of cut-elimination for LK following this paradigm?

(c) Why do you suppose Gentzen did not follow this paradigm when he proved cut-elimination, opting for a radically complicated step by step proof transformation of the sort that he earlier expressed distaste for?

(d) Why would the simple route to cut-elimination necessarily fail to provide numerical bounds on the size of the cut-free proofs?