April 25, 2024
Mathematics is concerned only with statements that are either true or false and proofs of such statements. While we all might agree with Shakespeare that “The quality of mercy is not strained. It droppeth as the gentle rain from heaven upon the place beneath” it is doubtful that a rigorous mathematical proof of that is possible.
It may come as a surprise that there are many different logical systems for mathematics that are contradictory. For two millenia Euclid’s Elements were regarded as the basis for rigorous logical reasoning. He invented the notion we can start from axioms that rational people can agree are true and specify how they can be used to rigorously derive more true statements.
“In a plane, given a line and a point not on it, at most one line parallel to the given line can be drawn through the point.” was John Playfair’s restatement of Euclid’s fifth postulate. A prodigious amount of work was exerted over two millenia to prove that was a consequence of Euclids other axioms. It is not. One way to show a statement is not true is to provide a counterexample.
It is possible to have no, or infinitely many, parallel “lines” in a “plane” through a “point” not on a given line where “point”, “line”, and “plane” that satisfy all of Euclids other axioms.
(Bolyai, Lobaschevsky)
Logical systems specify propositions, statements that are either true or false, and rules of inference, ways of combining true propositions to prove other true propositions.
Mathematicians prove theorems. Typically they have the form ‘if P is true then Q is true’ where P and Q are propositions. This is equivalent to ‘if P then Q’ and ‘P implies Q’. Every logical system has axioms: propositions that are assumed to be true. The fundamental rule of inference is modus ponens: if a proof involves the statement ‘P’ and the statement ‘P implies Q’ then the statement ‘Q’ can be included in the proof. Modus ponens means ‘method of placing.’
Inspired by René Descartes’ reduction of geometry to algebra, David Hilbert wanted to express all mathematical proofs as text. Using a ruler and compass to aid in constructing a geometric proofs obscured some implicit assumptions. For example, Euclid neglected to specify when a point was “between” two points on a line. This led to the false proof that all triangles are isosceles. According to Hilbert, “One must be able to say at all times - instead of points, straight lines, and planes - tables, chairs, and beer mugs.”
A proof of ‘A implies Z’ consists of a sequence of statements starting with A. The subsequent statements are either axioms or a statement using rules of inference applied to previous statements. If the last statement is Z then the theorem is proved, QED: “quod erat demonstrandum”, meaning “what was to be shown”. The difficulty with proofs is figuring out which axioms to use and when to apply the rules of inference.
Gerhard Gentzen formalized this technique as natural deduction but ran into the problem of how to avoid unnecessary detours. He had to invent a different way to reason about proofs to solve this.
!!! Sequent calculus, cut elimination.
The propositional calculus is based on the common English usage of the words, ‘not’, ‘and’, ‘or’, and ‘implies’. These are represented by logical connectives \neg, \wedge, \vee, and \supset.
Note that if P is false then P\supset Q is true no matter if Q is true or false. If you think it is peculiar that ‘false implies true’ is a true statement then you and I agree on that.
Exercise. Show \neg(\neg P) always has the same truth value as P.If P is true then \neg P is false so \neg(\neg P) is true. If P is false then \neg P is true so \neg(\neg P) is false.
If P is true then P\vee\neg P is true. If P is false then P\vee\neg P is true.
A tautology is a proposition that is true for all truth values of the propositions it contain. This leads to another connective.
The exercises show \neg(\neg P)\equiv P and P\vee\neg P is a tautology.
Exercise. Show P\equiv Q is equivalent to (P\wedge Q)\vee(\neg P\wedge\neg Q).
Exercise. Show P\supset Q and \neg P\vee Q are equivalent.
If P is false then P\supset Q is true, as we’ve just seen. Since \neg P is true in this case \neg P\vee Q is true. If P is true and Q is false then P\supset Q is false and so is \neg P\vee Q since both \neg P and Q are false. If P is true and Q is true then P\supset Q is true and so is \neg P\vee Q since Q is true.
We can reduce the amount of prose by using truth tables. The first columns of the table contain all possible truth values for the variables occuring in the statements to be evaluated in the remaining columns. Here is the truth table for ‘and’, ‘or’, and ‘implies’
| P | Q | P\wedge Q | P\vee Q | P\supset Q |
|---|---|---|---|---|
| F | F | F | F | T |
| F | T | F | T | T |
| T | F | F | T | F |
| T | T | T | T | T |
Binary connectives are functions from \{F,T\}^2 to \{F,T\}. The third column above for ‘and’ indicates F\wedge F = \wedge(F,F) = F, \wedge(F,T) = F, \wedge(T,F) = F, and \wedge(T,T) = T. ore generally, any proposition corresponds to a function \{F,T\}^n\to\{F,T\} where n is the number of variables in the proposition. A proposition is a tautology if and only if the range of its corresponding function is \{T\}.
The truth table for P\supset(Q\supset P) is
| P | Q | Q\supset P | P\supset(Q\supset P) |
|---|---|---|---|
| F | F | T | T |
| F | T | F | T |
| T | F | T | T |
| T | T | T | T |
where we have added a column for the subexpression Q\supset P to facilitate the evaluation. This shows P\supset(Q\supset P) is a tautology.
As the number of variables in a proposition increase, the number of cases to evaluate increases exponentially. If there are n variables, then there are 2^n cases to consider.
A more compact way of determining if a proposition is a tautology is to start from a small set of tautologies and apply modus ponens: if the propositions P\supset Q and P are tautologies then Q is a tautology.
that can be used to deduce any tautology, assuming that is possible. A proof of a tautology is a sequence of propositions that are either axioms or a result
For example, we can use P\supset(Q\supset P) to deduce P\supset P.
We will soon see that this is indeed possible using the axioms P\supset (Q\supset P) (P\supset(Q\supset R))\supset
Every well-formed proposition can be built up from propositional variables, P, Q, …, and connectives. The grammar of propositional calculus is \mathit{Prop}\to\mathit{Var} \mid(\neg\mathit{Prop}) \mid(\mathit{Prop}\wedge\mathit{Prop}) \mid(\mathit{Prop}\vee\mathit{Prop}) \mid(\mathit{Prop}\supset\mathit{Prop}) This is a production rule indicating how to generate all well-formed propostions from atoms and other well-formed propositions. The vertical bar ‘\mid’ indicates alternative rules and is not part of the grammar. Parentheses ‘()’ are used to indicate the order in which rules are applied. These are part of the grammar.
The first rule is that every atomic proposition is a well-formed proposition. If we apply the second rule twice to the atomic propostion P we get (\neg(\neg P)). The step-by-step production is P\to(\neg P)\to(\neg(\neg P)). More explicitly
| Prop | Rule |
|---|---|
| P | \mathit{Prop}\to\mathit{Var} |
| (\neg P) | \mathit{Prop}\to(\neg\mathit{Prop}) |
| (\neg(\neg P)) | \mathit{Prop}\to(\neg\mathit{Prop}) |
Although lost in prehistory, the imputus for logic must have been liars. The earliest evidence we have indicates primative societies always had a special class people who survived by making up stories in order to deceive others into providing them with the fruits of their labor. One way to get rid of these freeloaders was to find plausible arguments to demonstrate their stories were a sham.
Euclid was the first person (if he existed) to document this type of reasoning and the books he wrote are the second best sellers in history next to the bible. Devine truth only requires belief, mathematical truth requires considerable intellectual effort to comprehend.
While Euclid only considered geometry, Aristotle applied these methods to speech (logos)
(323–283 BC). euc 384–322 BC) aris
One early example of different logical systems involves Euclid’s fifth postulate: “There is at most one line that can be drawn parallel to a given line in a plane through an external point.” An astounding amount of intellectual effort was expendend over a 2000 year period to prove this from Euclid’s first four postulates until Carl Gauss found examples in 1810 of geometries that satisfied the first four postulates but not the fifth. In 1829 Nicolai Lobachevsky published examples of non-Euclidian geometries where there were no parallel lines and geometries where there were an infinite number of “parallel” lines with no intersection.
This was also an early example of how complicated mathematics can become if you just follow your nose while trying to think rigourously.
In 1854 George Boole published The Laws of Thought where he showed how to reduce Aristotle’s logical reasoning to a calculation. He introduced algebraic axioms that propositions and their logicial connectives must satisfy.