# Thread: induction problem on set of propositions

1. ## induction problem on set of propositions

hi

Here is a problem I am trying to do from Kenneth Rosen's
"Discrete mathematics..."

Show that

$\displaystyle [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_{n-1}\to p_n)]\\ \to [(p_1\wedge p_2\wedge\cdots\wedge p_{n-1})\to p_n]$

is a tautology whenever $\displaystyle p_1,p_2,\cdots ,p_n$ are propositions, whenever
$\displaystyle n\ge 2$

Here is the proof I attempted.

Base Case: $\displaystyle n=2$

let $\displaystyle p_1,p_2$ be arbitrary propositions.Now consider

$\displaystyle (p_1\to p_2)\to (p_1\to p_2)$

To prove this, we assume antecedent and since the antecedent is same
as consequent, it proves the above compound proposition . So
$\displaystyle P(2)$.

Induction case: Let $\displaystyle n\ge 2$ be arbitrary. Also suppose
$\displaystyle P(n)$. To prove $\displaystyle P(n+1)$, take arbitrary
propositions $\displaystyle p_1,p_2,\cdots,p_n,p_{n+1}$. We have to prove
that

$\displaystyle [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_n\to p_{n+1})]\\ \to [(p_1\wedge p_2\wedge\cdots\wedge p_n)\to p_{n+1}]$

is a tautology. In other words, we have to prove it. Since its an implication,
we suppose

$\displaystyle [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_n\to p_{n+1})]$

and we also suppose that

$\displaystyle (p_1\wedge p_2\wedge\cdots\wedge p_n)$

It follows that, in particular,

$\displaystyle p_n$

and

$\displaystyle p_n\to p_{n+1}$

So by modus ponens, we have

$\displaystyle p_{n+1}$

which proves $\displaystyle P(n+1)$

Since n is arbitrary, result holds generally.

Is it correct reasoning ?

Thanks

2. ## Re: induction problem on set of propositions

Originally Posted by issacnewton
Show that

$\displaystyle [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_{n-1}\to p_n)]\\ \to [(p_1\wedge p_2\wedge\cdots\wedge p_{n-1})\to p_n]$

is a tautology whenever $\displaystyle p_1,p_2,\cdots ,p_n$ are propositions, whenever
$\displaystyle n\ge 2$
This is quite an understatement because already

$\displaystyle [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_{n-1}\to p_n)]\to [p_1\to p_n]$

is a tautology. Indeed, given $\displaystyle p_1$, we conclude $\displaystyle p_2,\dots,p_{n-1},p_n$ in turn using implications.

Originally Posted by issacnewton
We have to prove
that

$\displaystyle [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_n\to p_{n+1})]\\ \to [(p_1\wedge p_2\wedge\cdots\wedge p_n)\to p_{n+1}]$

is a tautology. In other words, we have to prove it. Since its an implication,
we suppose

$\displaystyle [(p_1\to p_2)\wedge(p_2\to p_3)\wedge\cdots\wedge(p_n\to p_{n+1})]$

and we also suppose that

$\displaystyle (p_1\wedge p_2\wedge\cdots\wedge p_n)$
There is a subtle difference between proving that if 2 > 0, then 2 > 0 and showing that p -> p is a tautology. In the first case, you assume 2 > 0 and (trivially) show the conclusion. In the second case, you need to prove that the truth value of p -> p is T in every interpretation. You consider an interpretation I. It follows from the truth table for implication that for any formulas A and B, I(A -> B) = T iff I(A) = T implies I(B) = T. So, you assume that I(p) = T and (trivially) show that I(p) = T.

We have a mixture of two languages here. One is a metalanguage, where we say "2 > 0 implies 2 > 0." In proving such statement, we can say, "assume that 2 > 0." The second is an object language, which consists of propositional formulas like p -> p. In proving that p -> p is a tautology, we can't assume p because p is not a metalanguage proposition. However, object language propositions can be mapped to the metalanguage, e.g., p -> q becomes "(in some interpretation,) if p = T, then q = T." The truth tables of propositional connectives are designed so that p is a tautology iff p is mapped into a true statement of the metalanguage. Therefore, instead of showing that a formula of the object language is a tautology by considering interpretations and truth tables, we can prove its conversion to the metalanguage instead. This is called "reasoning inside propositional logic," and that's what you have done in your proof.

In general, it's useful to signal this transition between the two languages to the reader by saying "assume that p = T" or "assume that p is true" instead of just "assume p." One can also say, "reasoning inside propositional logic, ...".

Otherwise, you proof is fine.

3. ## Re: induction problem on set of propositions

Hi makarov

Thanks for response in detail. I am not sure I understand everything. When we prove
theorems in mathematics , are we not proving that those theorems , which are
propositions , are tautologies ? Thats why they are called theorems. They are supposed to be true no matter what.

So in my proof, instead of saying , "assume p" , I should have said "assume p is true",
is that correct ? So , is the proof offered correct or not ? I was confused by your
post a bit.

4. ## Re: induction problem on set of propositions

makarov, can you please comment on my post ?

thanks

5. ## Re: induction problem on set of propositions

The important thing to understand is that there is the ordinary language of mathematics, and then there is a set of words in the alphabet {(, ), ∧, ∨,→, ¬, p1, p2, ...}. The words of the alphabet are meaningless until you design the rules to assign them T or F in a given interpretation (a mapping from variables to {T, F}) using truth tables. Even then, these words remain just strings of symbols. In Rosen, a "tautology" is a special kind of these strings that are assigned T in every interpretation. Proven mathematical statements, like 1 + ... + n = n(n + 1) / 2 are not tautologies in this sense; they even use a different alphabet.

Edit: And yes, your proof is correct.