# Induction on logic formula

The term $((\bigvee_{i=1}^{n} p_i) \wedge (\bigwedge_{i=1}^{n} (p_i \to p)) \to p$ should be proven through induction. I'm relatively new to it, but I started with:

basis: $p(1): (p_1 \wedge (p_1 \to p)) \to p$ is true (modus ponens)

induction step: $((p_1 \vee p_2 \vee ... p_n) \wedge (p_1 \wedge p_2 \wedge ... p_{n-1} (p_n \to p)) \to p$

But I don't know how to go further from this or how to solve it, it would be nice if I could get a clue how to compute it to the end.

-

Your "induction step" is not stated correctly. The correct assumption on the induction step is $$\Bigl( \bigl(p_1\lor\cdots\lor p_n\bigr) \land \bigl( (p_1\to p)\land (p_2\to p)\land\cdots\land (p_n\to p)\bigr)\Bigr) \to p.$$

From this, you want to show that $$\Bigl( \bigl(p_1\lor\cdots\lor p_n\lor p_{n+1}\bigr) \land \bigl( (p_1\to p)\land (p_2\to p)\land\cdots\land (p_n\to p)\land (p_{n+1}\to p)\bigr)\Bigr) \to p$$ also holds.

One possibility is to distribute the $\land$: you have \begin{align*} &\Bigl( \bigl(p_1\lor\cdots\lor p_n\lor p_{n+1}\bigr) \land \bigl( (p_1\to p)\land (p_2\to p)\land\cdots\land (p_n\to p)\land (p_{n+1}\to p)\bigr)\Bigr) \to p\\ &\equiv \Bigl(\bigl(p_1\lor\cdots \lor p_n\bigr)\land\bigl( \bigwedge_{i=1}^{n+1}(p_i\to p)\bigr) \lor \bigl( p_{n+1}\land\bigl(\bigwedge_{i=1}^{n+1}p_i\to p)\bigr)\Bigr) \to p\\ &\equiv \Biggl(\Bigl(\bigl( p_1\lor\cdots \lor p_n\bigr)\land \bigwedge_{i=1}^{n+1}(p_i\to p)\land (p_{n+1}\to p)\Bigr)\\ &\qquad\lor\Bigl(\bigl(p_{n+1}\land (p_{n+1}\to p)\bigr)\land \bigwedge_{i=1}^{n}(p_i\to p)\bigr)\Bigr)\Biggr)\to p \end{align*}

Now, this expression has the form $$\Bigl( \bigl((A\land B)\land C\bigr) \lor \bigl(D\land C)\Bigr)\to p.$$ From the induction hypothesis, you know that $(A\land B)\to p$ and from the $n=1$ case you know that $D\land C\to p$. Hence $(A\land B\land C)\to p$ and $D\land C\to p$.

-

First understand why the statement holds:

$$((\bigvee_{i=1}^{n} p_i) \wedge (\bigwedge_{i=1}^{n} (p_i \to p)) \to p$$

A concrete example,

$$((A \lor B \lor C) \land ((A \to p) \land (B \to p) \land (C \to p)))\to p$$

In the hypothesis at least one of $A,B,C$ is true, suppose that $B$ is true.. then we could simplify down to

$$(B \land ((A \to p) \land (B \to p) \land (C \to p)))\to p$$

and proving can be done by proving the stronger statement

$$(B \land (B \to p)) \to p$$

and this is modus ponens.

One wishes to use "induction" to make this type of reasoning "rigorous". In that case we must understand our assumptions and prove they hold in all cases.

1. In a disjunction $\bigvee_{i=1}^{n} p_i$ "at least one" $p_i$ holds. Formally, you may state this as $\bigvee_{i=1}^{n} p_i \to \exists j, p_j$.

2. Removing a conjunction from a hypothesis is strengthening. Informally we are saying proving $(X_i \land X_j \land \cdots) \to B$ also proves $(Y \land (X_i \land X_j \land \cdots)) \to B$, and this is a theorem you can prove without induction. The only difference was that our $Y$ was in a different location (between $X_i$ and $X_{i+1}$), if you have not shown that logical statements may be viewed equal (iff is an equivalence relation) up to permutation then that can also be proved by a simple induction argument.

Those two steps are essentially all of the argument (that applying these two steps always produces a "modus ponens" situation is evident) I will show how to prove (1) by induction:

• The base case ($n=0$): An empty disjunction is "False" (that is the identity of the $\lor$ moniod) so $\text{False} \to \exists j, p_j$ is trivial by ex falso quodlibet.

• The recursive step ($n \to n+1$): We are given the hypothesis $(\bigvee_{i=1}^{n} p_i) \to \exists j, p_j$ and wish to prove $((\bigvee_{i=1}^{n} p_i) \lor p_{n+1}) \to \exists j, p_j$. This is a simple proof by cases, if $p_{n+1}$ holds then put $j=n+1$ as our witness, if not then $\bigvee_{i=1}^{n} p_i$ holds so we may use our hypothesis to get a proof of $\exists j, p_j$.

-

Try to understand what this formula says. It says that if (i) one of the $p_i$ is true, (ii) each of the $p_i$ implies $p$, then (iii) $p$ must be true.

Here's how your induction proof goes. For $n=1$ it's easy, as you said. Now let's show that the statement for $n$ implies the statement for $n+1$. We are given that (i) one of $p_1,\ldots,p_{n+1}$ is true, (ii) each of the $p_i$ implies $p$. There are two cases. Case A: one of $p_1,\ldots,p_n$ is true. The induction hypothesis implies that $p$ is true. Case B: $p_{n+1}$ is true. Now it's like the base case.

You can formulate exactly this argument in formal logic. It's, as they say, "just a formality". I'll leave that to you.

-