Back to the on-screen lesson ·
The converse of soundness, what it makes derivability and entailment amount to, and the finiteness result that follows because every derivation is finite.
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 completeness theorem and distinguish it from soundness, say what follows from it and what does not, fill in the derivability and entailment columns of a sound and complete system, count the subsets a compactness hypothesis covers, order the steps that get compactness from completeness, and apply compactness to a set built for the purpose.
Soundness says that a derivation never misleads: everything derivable is entailed. It leaves the other direction open, and a system could be sound and still miss most of what its semantics supports. This lesson is about the theorem that closes it.
A set is consistent in the syntactic sense when no contradiction is derivable from it, and satisfiable when some valuation makes every member true. A set is finitely satisfiable when every finite subset of it is satisfiable. A countable language is one whose symbols can be listed.
The completeness theorem is the converse of soundness: whenever $\Gamma \models \phi$, also $\Gamma \vdash \phi$. It is a stronger and harder result, and it is usually proved in a different-looking form — every set from which no contradiction is derivable has a model — from which the statement above follows. With soundness, it makes $\vdash$ and $\models$ coincide, so that a question about proofs and a question about valuations have the same answer. Compactness follows: if every finite subset of a set has a model, so does the set. The reason is short. If the whole set had no model it would entail a contradiction; completeness would turn that into a derivation; and a derivation is a finite object, so it cites only finitely many members — giving a finite subset with no model. Everything here is about a formal system: what its rules derive and what its structures satisfy, and nothing else.
Another way: steps
Another way: example
A set of sentences with models of every finite size: add sentences saying there are at least $n$ objects for every $n$. Each finite subset is satisfied by a large enough finite model, so compactness gives the whole enlarged set a model, and that model is infinite.
The first error is treating completeness and soundness as one result; they are converses, proved separately, and each rules out a different mismatch. The second is reading completeness as a method: it says a derivation exists and offers no way of finding it quickly. The third is over-reading a compactness conclusion — the theorem produces one model, and the models a set already had are not removed by it.
Does $P \to R$ follow from $P \to Q$ and $Q \to R$? A table says yes.
Settle the semantics.
Completeness then says a derivation exists, so the search will succeed.
Entailment to derivation.
Had the table said no, soundness would have said no derivation exists. Either way the proof system is settled by the table.
The two directions between them.
An infinite set with no model entails a contradiction.
Start from the failure.
Completeness gives a derivation of one, and a derivation has finitely many lines.
The derivation is finite.
So finitely many members were enough to go wrong, which is compactness in its contrapositive form.
A finite subset carries the fault.
A set with no model entails every formula, and in particular entails a contradiction.
So completeness supplies a derivation of a contradiction from it — which is why consistent and satisfiable coincide in a sound and complete system.
Match each result to what it states.
| Everything derivable from a set is entailed by it | Everything entailed by a set is derivable from it | If every finite subset of a set has a model, the whole set has one | A set with a formula added entails a second formula exactly when the set entails the conditional between them | |
|---|---|---|---|---|
| Soundness | ||||
| Completeness | ||||
| Compactness | ||||
| The deduction theorem |
Take this as the only thing you are given: whenever $\Gamma \models \phi$, also $\Gamma \vdash \phi$. Mark every statement that follows from it.
This task has no paper form; do it on a device.
The system is sound and complete. For each argument, write T or F in both columns: whether a derivation of the conclusion from the premises exists, and whether the premises entail the conclusion.
| A derivation exists? | The premises entail it? | |
|---|---|---|
| $P \to Q$, $P$; therefore $Q$ | ||
| $P \to Q$, $Q$; therefore $P$ | ||
| $P \vee Q$, $\neg P$; therefore $Q$ | ||
| $P \to Q$, $\neg P$; therefore $\neg Q$ |
Compactness says: if every finite subset of a set of sentences has a model, the whole set has one. A set has $3$ sentences in it. How many subsets does its hypothesis ask about?
Answer:
Compactness can be derived from completeness. Put the four steps of that argument into order.
Number the steps in order (write the number in the box):
Take compactness as stated: if every finite subset of a set of sentences has a model, the whole set has a model. A set $\Sigma$ of first-order sentences has models with arbitrarily large finite domains. What follows?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Premises: P -> Q and Q -> R. Conclusion: P -> R. Does the conclusion follow? If it does not, give a row that breaks it.
P -> Q
Q -> R
∴ P -> R
valid invalid — countermodel:
You can state completeness and compactness and say what each is used for. Say in your own words why the finiteness of a derivation is what makes compactness available.
8. Your turn: a set has no model. What does completeness say is derivable from it?, step 2