Using induction technique in mathematical logic

In summary: Thus, v*(A) = v'*(A) for every proposition A[P_{1}, \dots, P_{n}], where v(P_{i}) = v'(P_{i}) for all i=1, \dots, n.
  • #1
Kolmin
66
0

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. :smile:

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.
 
Physics news on Phys.org
  • #2
To the admins of the site, is this a thread for the "Set, Logic, Probability" section?
 
  • #3
Kolmin said:
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.
 
  • #4
Kolmin said:

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. :smile:

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

FAQ: Using induction technique in mathematical logic

1. What is the induction technique in mathematical logic?

The induction technique is a method used in mathematical logic to prove that a statement holds for all natural numbers. It involves proving a base case, typically the statement is true for the number 0, and then showing that if the statement holds for a particular number, it also holds for the next number.

2. How is the induction technique different from other proof methods?

The induction technique is different from other proof methods because it relies on the assumption that if a statement holds for a particular number, it also holds for the next number. This allows for a proof by infinite descent, instead of having to check every single case individually.

3. What types of statements can be proven using the induction technique?

The induction technique is typically used to prove statements about natural numbers, such as properties of integers, sequences, and series. It can also be used to prove statements about recursive functions and structures.

4. Can the induction technique be used in other areas of mathematics?

Yes, the induction technique can also be applied in other areas of mathematics, such as set theory, group theory, and topology. It can be used to prove theorems and properties in these areas by showing that they hold for a base case and then using the assumption that they also hold for the next case.

5. What are some common mistakes to avoid when using the induction technique?

One common mistake when using the induction technique is assuming that the statement holds for all numbers without actually proving it. It is important to show that the statement holds for the base case and then use the induction hypothesis to prove that it holds for the next case. Another mistake is using the wrong variable or changing the variable being used in the induction hypothesis. It is important to keep track of the variables and ensure they are consistent throughout the proof.

Similar threads

Back
Top