I am having trouble with Problem 1.2.10a, page 28 of Enderton's A Mathematical Introduction to Logic.

Say that a set $\Sigma_1$ of wffs is equivalent to a set $\Sigma_2$ of wffs iff for any wff a, we have $\Sigma_1$ $\models$ a iff $\Sigma_2$ $\models$ a. A set $\Sigma$ is independent iff no member of $\Sigma$ is tautologically implied by the remaining members in $\Sigma$. Show that the following hold: A finite set of wffs has an independent equivalent subset.

After reading around for a while, I have come to understand the method to attack this problem: You basically take out each wff that is tautologically implied by other members of $\Sigma$. Eventually, you get that independent equivalent subset, because the set is finite. However, I have some problems with understanding tiny details in the full proof. Here's one solution I have found online. The part I don't understand is this:

If $\Sigma$ is not independent, let $\alpha$ $\in$ $\Sigma$ be some formula such that $\Sigma$ \ {$\alpha$} $\models$ $\alpha$. Let $\Delta$ = $\Sigma$ \ {$\alpha$}. Then whenever $\Delta$ $\models$ $\beta$, also $\Sigma$ $\models$ $\beta$ since $\Delta$ $\subseteq$ $\Sigma$.

If $\Delta$ $\models$ $\beta$, then every truth assignment for the sentence symbols in $\Delta$ that satisfies every wffs in $\Delta$ must satisfy $\beta$. We know that $\Sigma$ = $\Delta$ $\cup$ {a}. But how can we know that the truth assignment that satisfies $\alpha$ also satisfies $\beta$? Otherwise, I don't see how we can conclude that $\Sigma$ $\models$ $\beta$ simply because $\Delta$ $\subseteq$ $\Sigma$.

That's the question. I hope someone can clear away my confusion.


1 Answer 1


It is a general fact about $\models$ that if $\Delta$ and $\Sigma$ are sets of wffs such that $\Delta \subseteq \Sigma$ and, if $\Delta \models \phi$ for some wff $\phi$, then $\Sigma \models \phi$ (I can say more about this if it doesn't make sense). In the proof you are looking at, you have that $\Sigma = \Delta \cup \{\alpha\}$ and that $\Delta \models \alpha$, so any assignment that satisfies $\Delta$ also satisfies $\alpha$ and hence $\Sigma$. You don't need to worry about assignments that satisfy $\alpha$, but possibly not other wffs in $\Delta$: you are only interested in assignments that satisfy all the wffs in $\Delta$.

  • $\begingroup$ Your answer seems to make sense, but I hope you can explain more about the fact that $\Sigma$ $\models$ $\phi$ because $\Delta$ $\models$ $\phi$. Maybe some examples or proof? $\endgroup$
    – Bedivere
    Aug 12, 2021 at 12:33
  • $\begingroup$ If $I$ is an assignment that satisfies $\Delta$, then $I$ also satisfies $\alpha$ (by definition of the given fact that $\Delta \models \alpha$). So such an $I$ satisfies $\Delta \cup \{\alpha\} = \Sigma$. $\endgroup$
    – Rob Arthan
    Aug 12, 2021 at 12:55
  • $\begingroup$ Okay, I got it. Thanks for the answer. $\endgroup$
    – Bedivere
    Aug 12, 2021 at 13:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .