compactness of propositional logic
(30 minutes to learn)
Summary
The Compactness Theorem of propositional logic states that if a given set of propositional sentences is contradictory, then there is also some finite subset which is contradictory.
Context
This concept has the prerequisites:
- propositional logic
- countable sets (The proof of the Compactness Theorem makes use of countability.)
Goals
- state the Compactness Theorem of propositional logic
- prove the Compactness Theorem
Core resources (read/watch one of the following)
-Paid-
→ A Mathematical Introduction to Logic
An undergraduate textbook in mathematical logic, with proofs.
Location:
Section 1.7, "Compactness and effectiveness," subsection "Compactness," pages 59-60
Additional dependencies:
- recursion theorem
See also
-No Additional Notes-