I am working on a problem to prove, but I do not understand it completely. Where should I use inductive method? What is the base case? And so on. Here is my problem:

A truth assignment $M$ is a function that maps propositional variables to $\{0, 1\}$ ($1$ for true and $0$ for false). We write $M\vDash x$ if $x$ is true under $M$. We define a partial order $\leq$ on truth assignments by $M \le M'$ if $M(p) \le M'(p)$ for every propositional variable $p$.

A propositional formula is positive if it only contains connectives $\wedge$ and $\vee$ (i.e., no negation $\lnot$ or implication $\Rightarrow$).

Use Proof By Induction to show that for any truth assignments $M$ and $M'$ such that $M\le M'$, and any positive propositional formula $x$, if $M \vDash x$, then $M' \vDash x$.

I am really confused. Any help is welcome. Thank you.


Perhaps a more concrete statement of what you need to show is the following:

Let $M \leq M^\prime$ be truth assignments. Then for every positive formula $\varphi$ either $M \not\models \varphi$ or $M^\prime \models \varphi$.

We also note that the family of positive formulas has its own inductive definition, similar to the definition of the family of all formulas:

  • Every propositional variable $p$ is a positive formula.
  • If $\varphi , \psi$ are positive formulas, then so are $\varphi \wedge \psi$ and $\varphi \vee \psi$.
  • (No other formula is positive.)

So to prove the result, we need to show two-and-a-half things: Let $M \leq M^\prime$ be truth assignments, then

  1. if $p$ is a propositional variable, then either $M \not\models p$ or $M^\prime \models p$.
  2. if $\varphi , \psi$ are formulas such that either $M \not\models \varphi$ or $M^\prime \models \varphi$, and similarly for $\psi$, then
    • either $M \not\models \varphi \wedge \psi$ or $M^\prime \models \varphi \wedge \psi$; and
    • either $M \not\models \varphi \vee \psi$ or $M^\prime \models \varphi \vee \psi$.

To leave with a parting

Hint: The definition of the partial order $\leq$ will be very useful in the base case (1), and the definition of $\models$ (for compound formulas) will be very useful in the inductive step (2).


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.