# Using induction technique in mathematical logic

1. Oct 15, 2012

### Kolmin

1. The problem statement, all variables and given/known data

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

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.

PROOF:
The proof works on induction on the length of $A$.
- Basis Step: In the case $i=1$ we have that $A$ is equal to $P_{1}$ and we have $v(P_{1})=v'(P_{1})$. Hence, we have $v^{*}(A)=v'^{*}(A)$ and the lemma is proved for $i=1$.
- Inductive Step: We assume that, if $v(P_{i})=v'(P_{i})$ for all $i=1, \dots, k$ with $k<n$, then $v^{*}(A)=v'^{*}(A)$. Now, for $n$ we have either $v(P_{n})=v'(P_{n})$ or $v(P_{n}) \neq v'(P_{n})$. In particular, if $v(P_{n})=v'(P_{n})$, then $v^{*}(A)=v'^{*}(A)$ for the inductive step.

2. Oct 16, 2012

### Kolmin

To the admins of the site, is this a thread for the "Set, Logic, Probability" section?

3. Oct 16, 2012

### Staff: Mentor

No, this is the right place for homework problems.

4. Oct 16, 2012

### 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.