Using induction technique in mathematical logic

[Kolmin]

Homework Statement

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

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

 

[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 [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].

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

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.