Mathematical Logic

Propositional logic is a formal system dealing with propositions (true/false) and logical connectives (AND, OR, NOT, etc.).

Predicate logic (first-order logic) extends propositional logic with variables, quantifiers (∀, ∃), and predicates. It can express mathematical statements precisely.

Mathematical proof is the process of deriving conclusions logically from axioms and proven theorems. Methods include direct proof, contradiction, and induction.

Mathematical induction proves statements about natural numbers. It consists of base case (n=1) and inductive step (n=k → n=k+1).

Gödel's incompleteness theorems show that in any sufficiently powerful mathematical system, there exist true statements that cannot be proved or disproved.

Sufficiently powerful formal systems contain true but unprovable statements (first theorem) and cannot prove their own consistency (second theorem).

Studies the relationship between formal languages and mathematical structures (models) interpreting them. Completeness, compactness, and Löwenheim-Skolem are key results.

Studies formal proofs as mathematical objects. Natural deduction, sequent calculus, cut elimination, and proof normalization are key topics.

Studies the limits of what can be computed algorithmically. Turing machines, halting problem, undecidability, and Turing degrees are key concepts.

A logical system dealing with necessity (□) and possibility (◇). Interpreted through possible worlds in Kripke semantics.

A formal system classifying mathematical objects by types. Through the Curry-Howard correspondence, proofs correspond to programs.

A technique used to prove independence results in set theory. Used by Cohen to prove the independence of the continuum hypothesis.

Hierarchically classifies the complexity of sets of reals. The hierarchies of Borel, analytic, and projective sets are central.