Back to the on-screen lesson ·
The two relations a formal system has, the theorem that says everything derivable is entailed, how it is proved rule by rule, and what it does not say.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to state the difference between derivability and entailment, state the soundness theorem, say what follows from it and what does not, use its contrapositive to rule out a derivation from a countermodel, order the stages of its proof, and recognise when its hypothesis has not been met.
You can test an argument with a table and you can derive a conclusion with rules. Those are two different activities that have so far agreed with each other. This unit is about why they agree, and about what is proved when one says they do.
$\Gamma \vdash \phi$ — derivability — says a derivation exists. $\Gamma \models \phi$ — entailment — says no valuation satisfies $\Gamma$ with $\phi$ false. A system is sound when $\vdash$ implies $\models$ and complete when $\models$ implies $\vdash$. Note that sound said of a single argument means something else: valid with true premises.
A formal system has two relations between a set of formulas and a formula, and they are defined in completely different terms. $\Gamma \vdash \phi$ is syntactic: there is a finite list of lines, each a premise or the result of a rule applied to lines above it, ending on $\phi$. Checking it requires no tables and no meanings — only that each line fits its rule. $\Gamma \models \phi$ is semantic: no valuation satisfies every member of $\Gamma$ and makes $\phi$ false. Checking it requires no rules. The soundness theorem says that the first implies the second: anything derivable is entailed. It is proved by induction on the length of a derivation — a premise line is entailed because it is a member of $\Gamma$, and each rule is checked once to see that it takes entailed lines to entailed lines. Two things follow at once. A derivation is a certificate of entailment, which is what makes proofs worth writing. And a countermodel shows that no derivation exists, because a derivation would have made the argument valid.
Another way: steps
Another way: example
From $P \to Q$ and $Q$, there is no derivation of $P$ in a sound system: the valuation making $P$ false and $Q$ true satisfies both premises and refutes the conclusion, so the entailment fails, so by the contrapositive of soundness no derivation exists.
The first error is reading a derivation as establishing its conclusion outright: it establishes a conditional claim about valuations, and says nothing about whether any premise is true. The second is using soundness in the direction it does not run — from a failed search to the failure of an entailment — which is completeness, and a separate theorem. The third is confusing the two uses of sound: an argument is sound when it is valid with true premises, and a system is sound when everything it derives is entailed.
A derivation of $R$ from $P \to Q$, $Q \to R$ and $P$ exists: two detachments.
The hypothesis is met.
Soundness gives $\{P \to Q, Q \to R, P\} \models R$.
Apply the theorem.
Eight rows would have shown the same thing. Five lines showed it instead, and would have done so for twenty atoms.
This is what the theorem buys.
Does $P$ follow from $P \to Q$ and $Q$? The valuation with $P$ false and $Q$ true satisfies both premises.
Find a countermodel.
So the entailment fails. By the contrapositive of soundness, no derivation of $P$ from those premises exists.
Contrapositive, not converse.
That is stronger than saying nobody has found one: it says nobody will.
A search is not a proof.
Soundness gives that the empty set entails $\phi$: no valuation whatever makes $\phi$ false.
That is exactly what it is for $\phi$ to be a tautology. With a non-empty set the conclusion would have been weaker.
Match each notation or phrase to what it says.
| There is a derivation of the formula from the set, using the rules | Every valuation satisfying the set satisfies the formula | Whenever there is a derivation, the entailment holds as well | Whenever the entailment holds, there is a derivation as well | |
|---|---|---|---|---|
| $\Gamma \vdash \phi$ | ||||
| $\Gamma \models \phi$ | ||||
| The system is sound | ||||
| The system is complete |
Take the soundness theorem as stated: whenever $\Gamma \vdash \phi$, also $\Gamma \models \phi$. You have written a derivation of $\phi$ from $\Gamma$. What does the theorem let you conclude?
Take this as the only thing you are given: whenever $\Gamma \vdash \phi$, also $\Gamma \models \phi$. Mark every statement that follows from it.
This task has no paper form; do it on a device.
Premises: P -> Q and Q. Conclusion: P. Does the conclusion follow? If it does not, give a row that breaks it.
P -> Q
Q
∴ P
valid invalid — countermodel:
Put the four stages of the soundness proof into the order they are done in.
Number the steps in order (write the number in the box):
The system is sound: whenever $\Gamma \vdash \phi$, also $\Gamma \models \phi$. You have looked hard for a derivation of $\phi$ from $\Gamma$ and have not found one. What does soundness entitle you to conclude about whether $\Gamma \models \phi$?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
From the premises Q -> R, R -> S and Q, derive S. Give one line at a time, with the rule and the lines it uses.
Q -> R
R -> S
Q
∴ S
| # | Formula | Rule | Lines |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 | |||
| 6 |
You can state the soundness theorem and apply it in both the forward and the contrapositive direction. Say in your own words why a countermodel shows that no derivation exists.
8. Your turn: a sound system derives $\phi$ from the empty set. What follows?, step 2