6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ There is a mismatch between the statement in the title and the one in th body of the OP. In the title, $\Delta \subseteq \Gamma$ is required to be unsatisfiabe, in the body of the OP this requirement is dropped. Which of the two statements is to prove or disprove? Moreover, do you know compactness theorem? $\endgroup$ Aug 19 at 6:23
  • $\begingroup$ @Taroccoesbrocco fixed; thanks! $\endgroup$ Aug 19 at 7:06
  • $\begingroup$ I know the compactness theorem, but I don't see how it is related. $\endgroup$ Aug 19 at 7:07
  • $\begingroup$ thanks @bof, fixed $\endgroup$ Aug 19 at 7:20
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Is the fact you use, that $\subseteq$ is well-founded, simple to show? $\endgroup$
    – coffeemath
    Aug 19 at 10:47
  • $\begingroup$ @coffeemath - Sure, because thanks to compactness theorem, we can restrict to consider the finite subsets of $\Gamma$. I edited the proof to make it clearer (I hope). $\endgroup$ Aug 19 at 11:27
  • $\begingroup$ Thanks for clearing that up, and +1. $\endgroup$
    – coffeemath
    Aug 19 at 13:12

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.