## § Godel completeness theorem

- If a formula is true (holds in every model), then it is derivable from the logic.
- theory is syntactically consistent if one cannot derive both $s$ and $\lnot s$ from the deduction rules.
- Henkin's model existence theorem says that if a theory is syntactically consistent, then it has a model, for a 1st order theory with well orderable language.

#### § Relationship to compactness

- Compactness and completeness are closely related.
- Compactness: If $\phi$ is a logical consequence of at most countably infinite $\Gamma$, then $\phi$ is a logical consequence of some finite subset of gamma.
- Completeness => compactness, since a derivation tree is a finite object, and must thus only use a finite number of rules.
- For compactness => completeness, suppose that
`Γ |= φ`

. We wish to show `Γ |- φ`

. - Compactness implies that
`γ1, γ2, ... γn |= φ`

where `{ γ1, ..., γn } ⊂ Γ`

. - That is the same as proving that
`|= γ1 -> (γ2 -> (... (γn → φ)))`

#### § Henkin model (term model)