display all the ideas for this combination of texts
20 ideas
| 13801 | An 'informal proof' is in no particular system, and uses obvious steps and some ordinary English [Bostock] |
| Full Idea: An 'informal proof' is not in any particular proof system. One may use any rule of proof that is 'sufficiently obvious', and there is quite a lot of ordinary English in the proof, explaining what is going on at each step. | |
| From: David Bostock (Intermediate Logic [1997], 8.1) |
| 13619 | Quantification adds two axiom-schemas and a new rule [Bostock] |
| Full Idea: New axiom-schemas for quantifiers: (A4) |-∀ξφ → φ(α/ξ), (A5) |-∀ξ(ψ→φ) → (ψ→∀ξφ), plus the rule GEN: If |-φ the |-∀ξφ(ξ/α). | |
| From: David Bostock (Intermediate Logic [1997], 5.6) | |
| A reaction: This follows on from Idea 13610, where he laid out his three axioms and one rule for propositional (truth-functional) logic. This Idea plus 13610 make Bostock's proposed axiomatisation of first-order logic. |
| 13622 | Axiom systems from Frege, Russell, Church, Lukasiewicz, Tarski, Nicod, Kleene, Quine... [Bostock] |
| Full Idea: Notably axiomatisations of first-order logic are by Frege (1879), Russell and Whitehead (1910), Church (1956), Lukasiewicz and Tarski (1930), Lukasiewicz (1936), Nicod (1917), Kleene (1952) and Quine (1951). Also Bostock (1997). | |
| From: David Bostock (Intermediate Logic [1997], 5.8) | |
| A reaction: My summary, from Bostock's appendix 5.8, which gives details of all of these nine systems. This nicely illustrates the status and nature of axiom systems, which have lost the absolute status they seemed to have in Euclid. |
| 13615 | 'Conditonalised' inferences point to the Deduction Theorem: If Γ,φ|-ψ then Γ|-φ→ψ [Bostock] |
| Full Idea: If a group of formulae prove a conclusion, we can 'conditionalize' this into a chain of separate inferences, which leads to the Deduction Theorem (or Conditional Proof), that 'If Γ,φ|-ψ then Γ|-φ→ψ'. | |
| From: David Bostock (Intermediate Logic [1997], 5.3) | |
| A reaction: This is the rule CP (Conditional Proof) which can be found in the rules for propositional logic I transcribed from Lemmon's book. |
| 13620 | Proof by Assumptions can always be reduced to Proof by Axioms, using the Deduction Theorem [Bostock] |
| Full Idea: By repeated transformations using the Deduction Theorem, any proof from assumptions can be transformed into a fully conditionalized proof, which is then an axiomatic proof. | |
| From: David Bostock (Intermediate Logic [1997], 5.6) | |
| A reaction: Since proof using assumptions is perhaps the most standard proof system (e.g. used in Lemmon, for many years the standard book at Oxford University), the Deduction Theorem is crucial for giving it solid foundations. |
| 13621 | The Deduction Theorem and Reductio can 'discharge' assumptions - they aren't needed for the new truth [Bostock] |
| Full Idea: Like the Deduction Theorem, one form of Reductio ad Absurdum (If Γ,φ|-[absurdity] then Γ|-¬φ) 'discharges' an assumption. Assume φ and obtain a contradiction, then we know ¬&phi, without assuming φ. | |
| From: David Bostock (Intermediate Logic [1997], 5.7) | |
| A reaction: Thus proofs from assumption either arrive at conditional truths, or at truths that are true irrespective of what was initially assumed. |
| 13616 | The Deduction Theorem greatly simplifies the search for proof [Bostock] |
| Full Idea: Use of the Deduction Theorem greatly simplifies the search for proof (or more strictly, the task of showing that there is a proof). | |
| From: David Bostock (Intermediate Logic [1997], 5.3) | |
| A reaction: See 13615 for details of the Deduction Theorem. Bostock is referring to axiomatic proof, where it can be quite hard to decide which axioms are relevant. The Deduction Theorem enables the making of assumptions. |
| 13753 | Natural deduction takes proof from assumptions (with its rules) as basic, and axioms play no part [Bostock] |
| Full Idea: Natural deduction takes the notion of proof from assumptions as a basic notion, ...so it will use rules for use in proofs from assumptions, and axioms (as traditionally understood) will have no role to play. | |
| From: David Bostock (Intermediate Logic [1997], 6.1) | |
| A reaction: The main rules are those for introduction and elimination of truth functors. |
| 13755 | Excluded middle is an introduction rule for negation, and ex falso quodlibet will eliminate it [Bostock] |
| Full Idea: Many books take RAA (reductio) and DNE (double neg) as the natural deduction introduction- and elimination-rules for negation, but RAA is not a natural introduction rule. I prefer TND (tertium) and EFQ (ex falso) for ¬-introduction and -elimination. | |
| From: David Bostock (Intermediate Logic [1997], 6.2) |
| 13758 | In natural deduction we work from the premisses and the conclusion, hoping to meet in the middle [Bostock] |
| Full Idea: When looking for a proof of a sequent, the best we can do in natural deduction is to work simultaneously in both directions, forward from the premisses, and back from the conclusion, and hope they will meet in the middle. | |
| From: David Bostock (Intermediate Logic [1997], 6.5) |
| 13754 | Natural deduction rules for → are the Deduction Theorem (→I) and Modus Ponens (→E) [Bostock] |
| Full Idea: Natural deduction adopts for → as rules the Deduction Theorem and Modus Ponens, here called →I and →E. If ψ follows φ in the proof, we can write φ→ψ (→I). φ and φ→ψ permit ψ (→E). | |
| From: David Bostock (Intermediate Logic [1997], 6.2) | |
| A reaction: Natural deduction has this neat and appealing way of formally introducing or eliminating each connective, so that you know where you are, and you know what each one means. |
| 13611 | Tableau proofs use reduction - seeking an impossible consequence from an assumption [Bostock] |
| Full Idea: A tableau proof is a proof by reduction ad absurdum. One begins with an assumption, and one develops the consequences of that assumption, seeking to derive an impossible consequence. | |
| From: David Bostock (Intermediate Logic [1997], 4.1) |
| 13613 | A completed open branch gives an interpretation which verifies those formulae [Bostock] |
| Full Idea: An open branch in a completed tableau will always yield an interpretation that verifies every formula on the branch. | |
| From: David Bostock (Intermediate Logic [1997], 4.7) | |
| A reaction: In other words the open branch shows a model which seems to work (on the available information). Similarly a closed branch gives a model which won't work - a counterexample. |
| 13612 | Non-branching rules add lines, and branching rules need a split; a branch with a contradiction is 'closed' [Bostock] |
| Full Idea: Rules for semantic tableaus are of two kinds - non-branching rules and branching rules. The first allow the addition of further lines, and the second requires splitting the branch. A branch which assigns contradictory values to a formula is 'closed'. | |
| From: David Bostock (Intermediate Logic [1997], 4.1) | |
| A reaction: [compressed] Thus 'and' stays on one branch, asserting both formulae, but 'or' splits, checking first one and then the other. A proof succeeds when all the branches are closed, showing that the initial assumption leads only to contradictions. |
| 13761 | In a tableau proof no sequence is established until the final branch is closed; hypotheses are explored [Bostock] |
| Full Idea: In a tableau system no sequent is established until the final step of the proof, when the last branch closes, and until then we are simply exploring a hypothesis. | |
| From: David Bostock (Intermediate Logic [1997], 7.3) | |
| A reaction: This compares sharply with a sequence calculus, where every single step is a conclusive proof of something. So use tableaux for exploring proofs, and then sequence calculi for writing them up? |
| 13756 | A tree proof becomes too broad if its only rule is Modus Ponens [Bostock] |
| Full Idea: When the only rule of inference is Modus Ponens, the branches of a tree proof soon spread too wide for comfort. | |
| From: David Bostock (Intermediate Logic [1997], 6.4) |
| 13762 | Tableau rules are all elimination rules, gradually shortening formulae [Bostock] |
| Full Idea: In their original setting, all the tableau rules are elimination rules, allowing us to replace a longer formula by its shorter components. | |
| From: David Bostock (Intermediate Logic [1997], 7.3) |
| 13757 | Unlike natural deduction, semantic tableaux have recipes for proving things [Bostock] |
| Full Idea: With semantic tableaux there are recipes for proof-construction that we can operate, whereas with natural deduction there are not. | |
| From: David Bostock (Intermediate Logic [1997], 6.5) |
| 13760 | A sequent calculus is good for comparing proof systems [Bostock] |
| Full Idea: A sequent calculus is a useful tool for comparing two systems that at first look utterly different (such as natural deduction and semantic tableaux). | |
| From: David Bostock (Intermediate Logic [1997], 7.2) |
| 13759 | Each line of a sequent calculus is a conclusion of previous lines, each one explicitly recorded [Bostock] |
| Full Idea: A sequent calculus keeps an explicit record of just what sequent is established at each point in a proof. Every line is itself the sequent proved at that point. It is not a linear sequence or array of formulae, but a matching array of whole sequents. | |
| From: David Bostock (Intermediate Logic [1997], 7.1) |