prove or disprove: every non satisfiable set of WFF has a non satisfiable sub set such every proper subset of it is satisfiable

231 Views Asked by At

Let $\Gamma$ be a non-satisfiable set of well-formed formulas (wff).

prove or disprove:

$\Gamma$ has a non-satisfiable subset $\Delta\subseteq\Gamma$ such that for every $\phi\subsetneq\Delta$ is satisfiable.

I believe this is wrong, because there are wffs that if I join them I'll get a contradiction, but I wasn't able to find a concrete example.

1

There are 1 best solutions below

3
On BEST ANSWER

The statement essentially says that if a set of formulas in unsatisfiable, then there is a minimal subset of it that is unsatisfiable. The statement is true.

Indeed, consider the two following general facts.

  1. Given a set $\Gamma$ of formulas, by compactness theorem, if $\Gamma$ is unsatisfiable then there is a finite $\Delta \subseteq \Gamma$ that is unsatisfiable.

  2. Given a set $\Gamma$, the relation $\subsetneq$ is well-founded on the finite powerset $\mathcal{P}_\text{fin}(\Gamma)$ of $\Gamma$ (see the footnote below).

As $\Gamma$ is unsatisfiable by hypothesis, the set $\{\Delta \subseteq \Gamma \mid \Delta \text{ is finite and unsatisfiable}\}$ is not empty by Point 1, and so it has a minimal element $\Delta_\min$ (with respect to $\subsetneq$) by Point 2, that is, $\Delta_\min \subseteq \Gamma$ is finite and unsatisfiable, but every $\Phi \subsetneq \Delta$ is satisfiable.

Note that we have proved something stronger than the statement, because we are claiming that such a minimal unsatisfiable $\Delta \subseteq \Gamma$ must be finite. We can also claim that $\Delta \neq \emptyset$, because $\emptyset \subseteq \Gamma$ is trivially satisfiable.


Footnote: Saying that the relation $\subsetneq$ is well-founded on $\mathcal{P}_\text{fin}(\Gamma)$ means that every non-empty set of finite subsets of $\Gamma$ has a minimal element with respect to $\subsetneq$. This essentially amounts to say that it is impossible to build an infinite descending chain $\Delta_0 \supsetneq \Delta_1 \supsetneq \Delta_2 \supsetneq \dots$ of finite $\Delta_i \subseteq \Gamma$. The fact that the $\Delta_i$'s have to be finite is crucial. Indeed, if $\Delta_0$ has a finite cardinality $n \in \mathbb{N}$, then $\Delta_1$ has cardinality at most $n-1$, and $\Delta_2$ has cardinality at most $n-2$, and so on, thus it is impossible to build an infinite descending chain. Luckily, in your case the compactness theorem allows us to consider only finite subsets of $\Gamma$.