Swipe to navigate through the chapters of this book
In the last two chapters, we learned quite a lot about propositional and quantificational logic and in particular their relations of logical implication. In this chapter, we look at how simple implications may be put together to make a deductively valid argument or proof. At first glance, this may seem trivial: just string them together! But although it starts like that, it goes well beyond, and is indeed quite subtle.
We begin by looking at the easy process of chaining, which creates elementary derivations, and show how its validity is linked with the Tarski conditions defining consequence relations/operations. We then review several higher-level proof strategies used in everyday mathematics and uncover the logic behind them. These include the strategies traditionally known as conditional proof, disjunctive proof and proof by cases, proof by contradiction and argument to and from an arbitrary instance. Their analysis leads us to distinguish second-level from split-level rules, articulate their recursive structures and explain the informal procedure of flattening a split-level proof into its familiar ‘suppositional’ form.
Please log in to get access to this content
Wikipedia entry on consequence operators. http://en.wikipedia.org/wiki/Consequence_operators
Makinson D (2007) Bridges from classical to nonmonotonic logic. College Publications, London, chapter 1
Wójcicki R (1988) Theory of logical calculi: basic theory of consequence operations. Synthese library, vol 199. Reidel, Dordrecht, chapter 1
The Wikipedia article highlights algebraic and topological connections of the concept, with lots of useful links. The Makinson text also goes on to discuss uncertain inference relations, mainly qualitative but also probabilistic.
The following are two very clear textbook discussions of traditional informal proof strategies in mathematics. Section 2.6 of the Bloch text also contains useful advice on writing proofs in coherent and elegant English:
Bloch ED (2011) Proofs and fundamentals: a first course in abstract mathematics, 2nd edn. Springer, New York, chapter 2
Velleman DJ (2006) How to prove it: a structured approach, 2nd edn. Cambridge University Press, Cambridge/New York, chapter 3
For a formal study of higher-level rules and proof theory, a good entry point would be:
von Plato J The development of proof theory. In: Stanford encyclopedia of philosophy. http://plato.stanford.edu/entries/proof-theory-development
For an aerial view of the jungle of textbook systems of ‘natural deduction’, with also a brief introduction to proof theory, see:
Pelletier J, Hazen A (2012) Natural deduction. In: Gabbay D, Woods J (eds) Handbook of the history of logic. Central concepts, vol 11
- Just Supposing: Proof and Consequence
- Springer London
- Sequence number
- Chapter number