Using induction technique in mathematical logic

[Kolmin]

Homework Statement

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

Homework Equations

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.

 

[Kolmin]

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

 

[Mark44]

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

No, this is the right place for homework problems.

 

[Mark44]

Homework Statement

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

Homework Equations

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.

A different way to approach this...
Base case: n = 2
The proposition is A[P₁, P₂], and by assumption v(P₁) = v'(P₁), and v(P₂) = v'(P₂). 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[P₁, P₂, ... , P_k], assume that v(P_i) = v'(P_i) for i = 1, 2, ..., k. Then v*(A) = v'*(A).

Now let n = k + 1, with the proposition now being A[P₁, P₂, ... , P_k, P_k+1], where v(P_i) = v'(P_i) for i = 1, 2, ..., k, k + 1. The proposition can be broken into two parts, with [P₁, P₂, ..., P_k] being one part, and P_k+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.