more from this thinker     |     more from this text

Single Idea 13690

[filed under theme 5. Theory of Logic / H. Proof Systems / 3. Proof from Assumptions ]

Full Idea

The style of proof called 'induction on formula construction' (or 'on the number of connectives', or 'on the length of the formula') rest on the fact that all formulas are built up from atomic formulas according to strict rules.

Gist of Idea

Proof by induction 'on the length of the formula' deconstructs a formula into its accepted atoms

Source

Theodore Sider (Logic for Philosophy [2010], 2.7)

Book Ref

Sider,Theodore: 'Logic for Philosophy' [OUP 2010], p.52

A Reaction

Hence the proof deconstructs the formula, and takes it back to a set of atomic formulas have already been established.

The 7 ideas with the same theme [proofs which add assumptions to axioms and rules]:

13616 The Deduction Theorem greatly simplifies the search for proof [Bostock]
13615 'Conditonalised' inferences point to the Deduction Theorem: If Γ,φ|-ψ then Γ|-φ→ψ [Bostock]
13620 Proof by Assumptions can always be reduced to Proof by Axioms, using the Deduction Theorem [Bostock]
13621 The Deduction Theorem and Reductio can 'discharge' assumptions - they aren't needed for the new truth [Bostock]
13690 Proof by induction 'on the length of the formula' deconstructs a formula into its accepted atoms [Sider]
13691 Induction has a 'base case', then an 'inductive hypothesis', and then the 'inductive step' [Sider]
10703 Supposing axioms (rather than accepting them) give truths, but they are conditional [Potter]