Proving by induction on the length of a propositional formula?

Question

I'm having a little trouble understanding the following proof question because I'm unsure what defines the 'length' of a propositional formula, I've seen multiple definitions whether it's the number of variables, connectives etc..

Statement: Let $\mathcal A$ be the propositional formula which uses only the connectives ∨ and ∧ and only the propositional variables $p$. Prove using induction on the length of A such that $p ⇒ \mathcal A$.

Secondly I don't quite understand the statement I'm trying to prove as it asks to prove $p \Rightarrow \mathcal A$ where $p $ is the propositional variables in $\mathcal A$, do I have to show that every variable in $\mathcal A$ logically implies $\mathcal A$?

Answer 1

It is not clear from your statement whether the proof is to strictly use induction on some variable such as the number of characters or some more general kind of induction.

Here is how I would do it. The definition of a well formed formula (wff) is almost always defined recursively. Your problem statement apparently uses something like this definition:

1. All propositional variables (such as $p$, $p1$, $p2$, etc.) are wffs.
2. If $\mathcal A$ is a wff then so is $(\mathcal A)$.
3. If $\mathcal A$ and $\mathcal B$ are wffs then so are $\mathcal A\land\mathcal B$ and $\mathcal A\lor\mathcal B$.
4. A statement is a wff if and only if it can be determined to be so by means of rules 1, 2, and 3.

(Note that a complete definition of wff would also include $\lnot\mathcal A$, $\mathcal A\implies\mathcal B$, and $\mathcal A\equiv\mathcal B$, and perhaps some others depending on your particular logical structure, but these are excluded in your problem.)

Then use induction on this (or the actual) definition. First show your problem is true for all propositional variables, then for wffs in parentheses, then for conjunctions and disjunctions.

If you need an actual variable to do induction on, note that each of those rules in the definition of a wff adds to the number of characters in the formula. You can then do induction on the number of characters in the formula. Use the induction

1. Show the statement is true for $n=1$ (statement letters).
2. Show that if the statement is true for all $k<n$ then it is true for $n$ (using definition rules 2 and 3).

In my first version, you could say $n$ is the number of applications of the rules for a wff. There are multiple ways to do the induction: pick the one that works best for you and the details of your class.

Is this clear?