Structural induction: Every propositional formula without negation is true under interpretation

Question

I have to proof the following statement.

Let $L$ be a language of propositional logic where formulas are built only from atomic formulas using the primitive connectives $¬$, $∧$, $∨$, $→$, and $↔$.

Let $A$ be a formula of $L$ containing no occurrence of $¬$ and $I$ an interpretation assigning to all atomic formulas of $A$ the truth value $1$.

Then, $A$ is true under $I$.

I wanted to archieve this using structural induction and I would like somebody to review it.

Let $P ⊆ L$ be a set containing propositional letters. The set $F$ of (propositional logic) formulas over $P$ without occurrence of $¬$ is defined recursively by:

(1) If $p ∈ P$, then $p$ is a formula over $F$.

(2) If $β$ and $γ$ are formulas over $F$, then so are:

• ($β ∧ γ$)
• ($β ∨ γ$)
• ($β → γ$)
• ($β ↔ γ$)

Suppose there is an interpretation $I$ such that for every propositional letter $α ∈ P$ that $I(α) = 1$.

Then the following holds:

(1) If $p ∈ P$, then $I(p) = 1$.

(2) Assume $β, γ ∈ F$ and $I(β) = I(γ) = 1$. Therefore the following applies for $β, γ ∈ F$.

• $I(β ∧ γ) = 1$
• $I(β ∨ γ) = 1$
• $I(β → γ) = 1$
• $I(β ↔ γ) = 1$

Therefore $A ∈ F$ is true under $I$.

Is this correct?

Answer 1

You seem rather confused about how structural induction works. If you want to prove a statement $S(\alpha)$ is true for any $\alpha\in F$, you need to do the following two steps.

First, you need to prove that $S(\alpha)$ is true if $\alpha\in P$. This is the "base case" of the induction, if you like.

Second, you need to prove that if $\alpha$ has the form $\beta\wedge\gamma$, $\beta\vee\gamma$, $\beta\rightarrow\gamma$, or $\beta\leftrightarrow\gamma$ where $\beta,\gamma\in F$ and $S(\beta)$ and $S(\gamma)$ are true, then $S(\alpha)$ is true. The assumption that $S(\beta)$ and $S(\gamma)$ are true is the induction hypothesis: you are assuming the result already holds for the formulas in $F$ you have built up "so far", and using that to conclude that it also holds for your new formula $\alpha$.

In your case, the statement $S(\alpha)$ is "$I(\alpha)=1$". The first step is what you did in your step (1). But you have not done the second step yet! You asserted that $I(\beta\wedge\gamma)=1$, $I(\beta\vee\gamma)=1$, and so on are true for $\beta,\gamma\in F$, but you never gave any proof of these assertions. To complete the second step, you need to assume the induction hypothesis that $\beta,\gamma\in F$ and $I(\beta)=I(\gamma)=1$, and then use that to prove that $I(\beta\vee\gamma)=1$ and so on. In your step (2), you did that in the special case that $\beta$ and $\gamma$ are in $P$, but you need to do it for arbitrary elements of $F$ (given the induction hypothesis).