Proof theory · Definition
Logical completeness
logicproofs
Before you start you need to know
Definition
A calculus \(\mathcal{S}\) is complete if every formula \(\varphi\) that is valid under its semantics is provable in \(\mathcal{S}\).
\[\mathcal{S}\models\varphi\Rightarrow\mathcal{S}\vdash\varphi\]
Logical completeness relates semantics with syntax: every formula that is valid under the considered interpretations can be proved through the formal calculus.
It does not mean that the system proves any formula or that it is automatically consistent. It means that it leaves out no valid logical truth of the kind the calculus intends to capture.
That is why completeness and consistency are distinct properties: one asks which truths can be reached and the other which contradictions cannot be proved.
Think about it
What does completeness connect?
The semantic validity of a formula with its formal provability.
Exercises 10
- Completeness relates...
- In a complete calculus, a valid formula can...
- Completeness does not mean that...
- Which expression represents the idea of completeness?
- Completeness is mainly about what the calculus...
- The completeness of a calculus connects...
- If a valid formula is provable in the calculus, we speak of...
- Completeness should not be read as saying that...
- Select consequences of a complete calculus.
- Completeness must be distinguished from consistency because...
References
- Frederic P. Schuller, Lectures on the Geometrical Anatomy of Theoretical Physics · Lecture 1, Introduction / Logic of Propositions and Predicates, YouTube, 2015.