1
$\begingroup$

Can someone suggest references to understand the more general/abstract concept of induction?

Specifically, I am trying to justify to myself what is called induction on the "complexity of a formula" found in introductory logic texts. I'm reading Chiswell and Hodges and CH Leary.

It seems to me that proving something using induction on complexity of a formula will only work if we know for sure that all formulas are built from propositional symbols from the bottom. But it is not clear to me that the definition of a formula necessitates this. But I thought if formulas are restricted to be finite strings from a language $LP(\sigma)$ then since each formula can be represented on a tree (a modified concept borrowed from Graph Theory in the first of two books I mentioned) then each must be of finite "height" and must have a propositional symbol as a leaf.

But either way I am not all that comfortable with it and would like to read more. I read the section on Induction and Recursion in the book on logic by Enderton which seems to explain it but it looks like I would have to read that book too from the beginning because there are references to earlier sections. Either way wondering if there is a more comprehensive exposition.

Any help would be appreciated.

$\endgroup$
6
  • $\begingroup$ You are asking for references, but you don't like the reference that you have (Enderton) because you'd have to read it? $\endgroup$
    – Carl Mummert
    Commented Aug 17, 2014 at 4:55
  • $\begingroup$ @Carl Mummert: I'm asking for references on the subject. Enderton has a passing comment on the subject. I don't know where to look to be honest. Set Theory books? If I started reading Enderton cover to cover that would be my 4th book on the subject (I would have read and not skimmed). Plus I'm guessing that's not the best place to look. Guess my wording is misleading though. Corrected. $\endgroup$
    – Ishfaaq
    Commented Aug 17, 2014 at 6:23
  • $\begingroup$ Section 1.4 of Enderton's book is devoted to exploring this topic in detail. $\endgroup$
    – Carl Mummert
    Commented Aug 17, 2014 at 11:47
  • $\begingroup$ You can see also this post for some comments regarding Enderton's exposition $\endgroup$
    – Mauro ALLEGRANZA
    Commented Aug 17, 2014 at 17:43
  • $\begingroup$ A step-by-step discussion (with comments) is in sect. 1.2 INDUCTION ON THE COMPLEXITY OF WFF of George Tourlakis, Mathematical Logic (2008), page 17-on. $\endgroup$
    – Mauro ALLEGRANZA
    Commented Aug 17, 2014 at 17:51

1 Answer 1

Reset to default
1
$\begingroup$

Perhaps [1] could be of use. However, see [2] if you want a very abstract approach (an approach that is related to topics in the links I gave in my comment here).

[1] Handbook of Mathematical Induction by David S. Gunderson (over 900 pages)

[2] Elementary Induction on Abstract Structures by Yiannis N. Moschovakis

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .