2
$\begingroup$

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

1 Answers 1

2

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