§ 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)

• References