# Mathematical Logic

**Type:** Concept  
**Domain:** Foundations & Logic  
**Codex URL:** /mathematics/foundations-logic/mathematical-logic/  
**Entry status:** Live — v1.0 (2026-05-27)

## Summary
Studies formal reasoning itself — precise rules of valid inference underlying every proof.

## Branches
Propositional logic, predicate (first-order) logic, proof theory, model theory, set theory, computability theory.

## Entscheidungsproblem (Hilbert, 1928)
Does a general mechanical procedure exist to determine provability of any statement? Church (1936) and Turing (1936) independently proved: no.

## Halting problem
Undecidable — no algorithm can determine, for all programs, whether they halt. Proven via self-referential argument akin to Gödel's and Cantor's.

## Church-Turing thesis
Turing machines capture the complete, correct notion of mechanical computability — a foundational thesis, not a provable theorem.

## Legacy in computer science
Turing machines → computer architecture; formal logic → programming languages; computability theory → complexity theory (Big-O, P vs NP).

## Sources
### Tier 1
- Turing, A.M. (1936). Proceedings of the London Mathematical Society.
- Enderton, H.B. (2001). A Mathematical Introduction to Logic. 2nd ed.
### Tier 2
- Church, A. (1936). American Journal of Mathematics.

---
*Mathematics Codex entry v1.0 — added 2026-05-27 — thecodex.expert/mathematics/*