Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Please help with the following proof:

Let $S =$ {$A_1, (A_1\to A_2), (A_2 \to A_3), (A_3 \to A_4), (¬A_4)$}. Show that any proper subset of $S$ is satisfiable.

Just looking at the set S, I can see that the statement is true. The only way I see of proving this is to go case by case. Does anyone see a better way of proving this? Also, please share any general tips for proving this statement for different values of $S$.

share|cite|improve this question
up vote 1 down vote accepted

If $T\subset S$ does not contain $A_1$, then making all $A_i$ false will satisfy all formulas in $T$. If $T\subseteq S$ does not contain $\neg A_4$, then setting all $A_i$ true will satisfy all formulas in $T$. If $A_1$ and $\neg A_4$ are both in $T$, then let $i$ be any integer such that $A_{i}\to A_{i+1}$ is not in $T$; such an $i$ must exist, with $1\leq i\leq 3$. Then setting all $A_k$ with $k\leq i$ true and all $A_k$ with $k\gt i$ false will satisfy all formulas in $T$ (the only formula of $S$ that is false under this assignment is $A_i\to A_{i+1}$, which is not in $T$).

share|cite|improve this answer

Your Answer


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.