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