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?


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).

  • $\begingroup$ I have updated my post and added an additional hypothesis. Is it correct now? I am unsure about that part. $\endgroup$
    – Alexander
    Nov 16 '17 at 18:48
  • $\begingroup$ No, you still have given no explanation whatsoever for your step (3). You need to state an induction hypothesis and then use that induction hypothesis. $\endgroup$ Nov 16 '17 at 18:51
  • $\begingroup$ Thanks a lot for the support! $\endgroup$
    – Alexander
    Nov 16 '17 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.