Logic Foundations and Theorems

Overview

This lecture explores the foundations of formal logic, focusing on axiomatic systems, propositional and predicate logic, semantics, paradoxes, the arithmetization of logic via Gödel numbering, and culminates in Gödel's incompleteness theorems and their impact on mathematics.

Introduction to Formal Logic

• Formal logic studies the structure (form) of arguments, not their content.
• Logic seeks to formalize reasoning into abstract symbol manipulation.
• Pure mathematics deals with abstract concepts with limited direct real-world application, but underpins much applied math and science.

Axiomatic Systems & Early Logic

• An axiom is a foundational statement assumed true to derive further truths.
• Euclid's geometry is an early example of an axiomatic system.
• Changing or removing axioms (e.g., Euclid’s fifth postulate) leads to different logical systems, such as non-Euclidean geometries.

Propositional Logic

• Propositional logic uses propositional symbols (A, B, C, …) representing indivisible statements.
• Connectives include AND (∧), OR (∨), IMPLIES (→), IF AND ONLY IF (↔), and NOT (¬).
• Well-formed formulae (wffs or “woofs”) are rules for combining symbols.
• Inference rules (e.g., modus ponens) define valid argument forms.
• Consistency: a theory is consistent if it cannot derive both a statement and its negation.

Predicate (First-Order) Logic

• Predicate logic extends propositional logic by allowing variables and predicates.
• A predicate represents a property or relation, with “arity” indicating the number of arguments.
• Quantifiers: "for all" (∀) and "there exists" (∃) allow statements about all or some members of a domain.
• Constants and function symbols can represent specific elements or structures.
• Enables formalizing more sophisticated arguments, e.g., “All men are mortal. Socrates is a man. Therefore Socrates is mortal.”

Syntax and Semantics

• Syntax: the formal rules for constructing valid statements.
• Semantics: the assignment of meaning/truth values in a structure or model.
• A model consists of a domain and interpretations for predicates, functions, and constants.
• Truth tables determine the truth values of propositional statements; quantifiers are evaluated over the domain.

Soundness and Completeness

• A theory is sound if all its provable statements are true in all its models.
• Semantic completeness: if a statement is true in all models, it is provable.
• Syntactic completeness: for every statement, either it or its negation is provable.
• Both propositional and first-order predicate logic are sound and semantically complete, but not generally syntactically complete.

Paradoxes in Logic

• Logical paradoxes (e.g., the liar paradox, Russell’s paradox, Quine’s paradox) arise from self-reference and lead to inconsistency.
• Some paradoxes (like Richard’s paradox) point to the distinction between arithmetic properties and meta-mathematical properties.

Gödel Numbering and Arithmetization

• Gödel numbering assigns unique numbers to logical symbols and formulae, allowing syntactic properties to be recast as arithmetic properties.
• This enables expressing properties about proofs and provability within arithmetic itself.
• Self-reference becomes possible by constructing sentences about their own provability.

Gödel’s Incompleteness Theorems

• If a formal system (e.g., Peano Arithmetic) is consistent and recursively enumerable, there are true statements it cannot prove (incompleteness).
• It is not possible to prove the consistency of such a system using only its axioms.
• The proof involves constructing a statement that effectively says "this statement is not provable within this system."

Misconceptions and Impact

• Gödel’s theorems do not mean mathematics as a whole is doomed or "cancelled."
• They don’t directly prove limits of human cognition or computers but reveal limits of formal, algorithmic systems.
• Many other areas of mathematics remain formally consistent and useful.

Key Terms & Definitions

• Axiom — a statement assumed true for deriving further truths.
• Well-formed formula (wff) — a syntactically valid expression in logic.
• Predicate — a logical statement with variables representing properties or relations.
• Quantifier — symbols (∀, ∃) indicating "for all" or "there exists."
• Model — an interpretation assigning meaning and truth to logical statements.
• Soundness — all provable statements are true in a theory’s models.
• Completeness — all true statements (semantic) or all statements (syntactic) can be proved.
• Gödel numbering — encoding symbols/statements as unique numbers.
• Peano Arithmetic — an axiomatic system for natural numbers and arithmetic.
• Incompleteness — the property that some true statements cannot be proved within a consistent, formal, recursive system.

Action Items / Next Steps

• Review and familiarize yourself with propositional and predicate logic notation and examples.
• Practice constructing and interpreting truth tables and well-formed formulae.
• Recommended reading: Alec Fisher’s "Formal Number Theory and Computability" for deeper exploration.
• Reflect on the philosophical implications of incompleteness in mathematics.