Single Idea 15406

[catalogued under 5. Theory of Logic / H. Proof Systems / 1. Proof Systems]

Full Idea

There are atomic formulas, and formulas built from the connectives, and that is all. We show that all formulas have some property, first for the atomics, then the others. This proof is 'induction on complexity'; we also use 'recursion on complexity'.

Gist of Idea

'Induction' and 'recursion' on complexity prove by connecting a formula to its atomic components

Source

John P. Burgess (Philosophical Logic [2009], 1.4)

Book Reference

Burgess,John P.: 'Philosophical Logic' [Princeton 2009], p.4


A Reaction

That is: 'induction on complexity' builds a proof from atomics, via connectives; 'recursion on complexity' breaks down to the atomics, also via the connectives. You prove something by showing it is rooted in simple truths.