Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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