0
$\begingroup$

I am reading Herbert Enderton's book "A Mathematical Introduction to Logic". On page 18, the Induction Principle is defined as:

"If S is a set of wff's containing all the sentence symbols and closed under all five formula-building operations, then S is the set of all wff's."

The five formula-building operations are formulated from the sentential connective symbols (negation, or, and, if, iff).

I understand the definition and the proof of this statement. However I am struggling with a few difficulties.

  1. Do we have to assume ZFC in order to construct sentential logic? The proof given from the Induction Principle seems to be based on 'numerical' strong induction to me.

  2. This Induction Principle looks nothing like the type of induction that I am accustomed to (assume p(x) and show p(x+1) ). Is the name misleading or will this 'induction principle' allow us to perform inductive proof in sentential logic? If so, how? The only possible connection I could see is that this principle might have something to do with well ordering?

Thank you for any explanation.

$\endgroup$
4
  • $\begingroup$ In inductive proofs you have a base p(0) and an inductive step p(x) => p(x+1)). Likewise the the Induction Principle has a base "sentence symbols" and the inductive step of applying the connective symbols. $\endgroup$
    – Q the Platypus
    Sep 2, 2016 at 3:43
  • $\begingroup$ So is the definition of the induction principle stating that such a set that you could induct over, exists? $\endgroup$
    – nobody
    Sep 2, 2016 at 3:48
  • $\begingroup$ See Ch.0 : a "certain amount" of "background knowledge" about sets and their properties (in order to "manage" trees and strings) is needed, in order to treat mathematically the properties of formal systems (i.e. the metalogic). $\endgroup$
    – Mauro ALLEGRANZA
    Sep 2, 2016 at 5:57
  • 1
    $\begingroup$ And see Structural induction for the type of induction used on some other math "objects" than numbers. $\endgroup$
    – Mauro ALLEGRANZA
    Sep 2, 2016 at 5:59

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .