1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Using induction technique in mathematical logic

  1. Oct 15, 2012 #1
    1. The problem statement, all variables and given/known data

    Prove the following LEMMA:
    For every proposition [itex]A[P_{1}, \dots, P_{n}][/itex] and any two interpretations [itex]v[/itex] and [itex]v'[/itex], if [itex]v(P_{i})=v'(P_{i})[/itex] for all [itex]i=1, \dots,n[/itex], then [itex]v^{*}(A)=v'^{*}(A)[/itex].

    2. Relevant equations

    3. The attempt at a solution

    Sure this is obviously an incredibly easy lemma to prove, but still I have problems with mathematical induction and I am not use to actually write proofs, so I would like to know if the following works and is decently written. So I am looking forward to your reply and... be nasty, thanks. :smile:

    The proof works on induction on the length of [itex]A[/itex].
    - Basis Step: In the case [itex]i=1[/itex] we have that [itex]A[/itex] is equal to [itex]P_{1}[/itex] and we have [itex]v(P_{1})=v'(P_{1})[/itex]. Hence, we have [itex]v^{*}(A)=v'^{*}(A)[/itex] and the lemma is proved for [itex]i=1[/itex].
    - Inductive Step: We assume that, if [itex]v(P_{i})=v'(P_{i})[/itex] for all [itex]i=1, \dots, k[/itex] with [itex]k<n[/itex], then [itex]v^{*}(A)=v'^{*}(A)[/itex]. Now, for [itex]n[/itex] we have either [itex]v(P_{n})=v'(P_{n})[/itex] or [itex]v(P_{n}) \neq v'(P_{n})[/itex]. In particular, if [itex]v(P_{n})=v'(P_{n})[/itex], then [itex]v^{*}(A)=v'^{*}(A)[/itex] for the inductive step.
  2. jcsd
  3. Oct 16, 2012 #2
    To the admins of the site, is this a thread for the "Set, Logic, Probability" section?
  4. Oct 16, 2012 #3


    Staff: Mentor

    No, this is the right place for homework problems.
  5. Oct 16, 2012 #4


    Staff: Mentor

    A different way to approach this...
    Base case: n = 2
    The proposition is A[P1, P2], and by assumption v(P1) = v'(P1), and v(P2) = v'(P2). Then for this proposition, v*(A) = v'*(A).
    Induction hypothesis: Suppose that the statement is true for n = k. In other words, for the proposition A[P1, P2, ... , Pk], assume that v(Pi) = v'(Pi) for i = 1, 2, ..., k. Then v*(A) = v'*(A).

    Now let n = k + 1, with the proposition now being A[P1, P2, ... , Pk, Pk+1], where v(Pi) = v'(Pi) for i = 1, 2, ..., k, k + 1. The proposition can be broken into two parts, with [P1, P2, ..., Pk] being one part, and Pk+1 being the other. Use the induction hypothesis to show that for the first proposition here, v*(A) = v'*(A). Then use the base case (n = 2) to show that v*(A) = v'*(A) for the larger proposition.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook