Introduction to Mathematical Logic

Introduction to Mathematical Logic Mathematical logic is the study of formal languages and reasoning methods that mathematicians use to express ideas with absolute precision. At its core, mathematical logic answers two fundamental questions: How can we write mathematical statements without any ambiguity? and How can we be certain that conclusions drawn from those statements are correct? The discipline divides into two closely related parts: propositional logic, which deals with simple statements and their combinations, and predicate logic (also called first-order logic), which allows us to make statements about objects and their properties. Understanding both is essential for rigorous mathematical thinking. Propositional Logic What Is a Proposition? A proposition is a declarative statement that is definitively either true or false. Examples include "$2$ is even" (true) and "$3 > 5$" (false). The key requirement is that there is no ambiguity—a proposition cannot be both true and false, or neither. Notice that "$x > 0$" can also be a proposition if we're talking about a specific value of $x$. However, propositional logic alone cannot easily handle statements like "for all $x$, $x > 0$"—this is where predicate logic becomes necessary. Logical Connectives In propositional logic, we combine simple propositions into more complex ones using logical connectives. The five fundamental connectives are: ¬ (negation or "not"): $¬P$ is true when $P$ is false, and false when $P$ is true. ∧ (conjunction or "and"): $P ∧ Q$ is true only when both $P$ and $Q$ are true. ∨ (disjunction or "or"): $P ∨ Q$ is true when at least one of $P$ or $Q$ is true. → (implication or "if...then"): $P → Q$ is false only when $P$ is true and $Q$ is false. (This captures the idea: if the hypothesis holds, the conclusion must hold.) ↔ (biconditional or "if and only if"): $P ↔ Q$ is true when $P$ and $Q$ have the same truth value. These connectives allow us to build increasingly complex formulas from atomic propositions. For example, starting with propositions $P$ and $Q$, we can form $(P ∧ Q) → ¬R$. Syntax: Well-Formed Formulas Syntax is the set of rules that tell us which combinations of symbols are valid formulas. Not every string of symbols is a valid formula—for instance, "$∧ ¬ P$" is not properly formed, but "$P ∧ ¬Q$" is. The basic syntax rules are: Any atomic proposition (like $P$, $Q$, $R$) is a formula. If $φ$ is a formula, then $¬φ$ is a formula. If $φ$ and $ψ$ are formulas, then $(φ ∧ ψ)$, $(φ ∨ ψ)$, $(φ → ψ)$, and $(φ ↔ ψ)$ are formulas. Parentheses are crucial for avoiding ambiguity. For example, $P ∧ Q ∨ R$ could mean either $(P ∧ Q) ∨ R$ or $P ∧ (Q ∨ R)$, which have different truth values. Semantics: Truth Values and Truth Tables Semantics is the study of what formulas mean—specifically, how to assign truth values to them. The key idea is straightforward: we start by assigning true or false to each atomic proposition, then use truth tables to determine the truth value of compound formulas based on their connectives. Here are the truth tables for the basic connectives: For negation: $¬P$ is true when $P$ is false $¬P$ is false when $P$ is true For conjunction ($P ∧ Q$): True only when both $P$ and $Q$ are true False in all other cases For disjunction ($P ∨ Q$): False only when both $P$ and $Q$ are false True in all other cases For implication ($P → Q$): False only when $P$ is true and $Q$ is false True in all other cases (including when $P$ is false) For biconditional ($P ↔ Q$): True when $P$ and $Q$ have the same truth value False when they differ A particularly important concept is tautology: a formula that is true under every possible assignment of truth values to its atomic propositions. For example, $P ∨ ¬P$ (the law of excluded middle) is always true—either $P$ holds or its negation holds. Conversely, a formula that is always false is called a contradiction. Proof Systems: Deriving Formulas A proof system is a formal method for deriving conclusions from premises using explicit rules. Rather than just checking truth tables, a proof system lets us apply syntactic rules to derive new formulas from existing ones. Two main approaches are: Natural deduction: Uses intuitive rules like "from $P$ and $P → Q$, conclude $Q$" (this rule is called modus ponens). Hilbert-style systems: Use a small set of axioms (formulas always assumed true) and simple inference rules. The crucial property of a good proof system is that it should only allow us to derive formulas that are actually true (the system is sound), and it should allow us to derive all formulas that are always true (the system is complete—more on this below). The Completeness Theorem for Propositional Logic Here's a profound result: If a formula is true under every possible assignment of truth values, then there exists a formal proof of that formula using the rules of propositional logic. In other words, the semantic notion of truth (using truth tables) and the syntactic notion of derivability (using proof rules) are equivalent. This means we can confidently use formal proof systems—anything we can't derive is genuinely not a tautology. This theorem assures us that formal logic is both sound and complete as a tool for propositional reasoning. Predicate Logic Why We Need Predicate Logic Propositional logic is powerful, but it has a significant limitation: it cannot express statements like "every integer is either even or odd" or "there exists a real number $x$ such that $x^2 = 2$." These statements are about all objects with a certain property or some object with a property—concepts that propositional logic simply cannot capture. Predicate logic extends propositional logic by introducing quantifiers and predicates, allowing us to make general claims about collections of objects. Quantifiers and Variables Predicate logic introduces two quantifiers: Universal quantifier ($∀$): The statement $∀x \, P(x)$ means "for every object $x$, the property $P$ holds." For example, $∀x \, (x \text{ is even} ∨ x \text{ is odd})$ asserts that every integer is either even or odd. Existential quantifier ($∃$): The statement $∃x \, P(x)$ means "there exists at least one object $x$ such that $P$ holds." For example, $∃x \, (x^2 = 2)$ asserts that at least one real number has the property that its square equals $2$. Variables like $x$, $y$, and $z$ act as placeholders for objects. The scope of a quantifier is important: $∀x \, P(x)$ means the variable $x$ is bound by the quantifier throughout the formula. A variable that is not bound by any quantifier is called free. Predicates and Functions A predicate is a symbol that expresses a property of objects or a relation between objects. For example: $E(x)$ might mean "$x$ is even" $\text{GreaterThan}(x, y)$ might mean "$x > y$" Predicates are the basic building blocks of atomic formulas in predicate logic. We write $P(t1, t2, \ldots, tn)$ where $P$ is an $n$-ary predicate and $t1, \ldots, tn$ are terms (variables or constants). A function maps objects to objects. For example, $s(x) = x + 1$ is a function. Functions can appear inside predicates: $E(s(x))$ means "the successor of $x$ is even," which is a meaningful statement. The interplay between predicates, functions, and quantifiers gives predicate logic tremendous expressive power. For instance, we can write: $$∀x \, ∃y \, (y = s(x))$$ which says "for every object $x$, there exists an object $y$ such that $y$ is the successor of $x$." Semantics of Predicate Logic To assign truth values to predicate logic formulas, we need an interpretation, which consists of: A domain: a non-empty set of objects we're reasoning about (e.g., the integers, the real numbers, or any other collection). An assignment of meanings to each predicate symbol: for an $n$-ary predicate $P$, we specify which $n$-tuples of objects satisfy $P$. An assignment of meanings to each function symbol: specifying which object each function maps its inputs to. Once we have an interpretation and we've assigned values to any free variables, we can evaluate whether a formula is true or false. Example: Suppose our domain is the integers, $E(x)$ means "$x$ is even," and $s(x) = x + 1$. Then: $E(2)$ is true (2 is even) $E(3)$ is false (3 is not even) $E(s(2))$ is $E(3)$, which is false Interpretation and Model An interpretation is simply a choice of domain and meaning for all symbols, as described above. A model is an interpretation that makes a particular set of sentences true. If we're given a set of premises and we want to know whether a conclusion follows, we look for models of the premises and check whether the conclusion is true in all of them. For example, if our premises are "$∀x \, (x \text{ is even} ∨ x \text{ is odd})$" and "$∃x \, (x > 0)$", then a model would be any interpretation (like the integers) where both premises are true. Validity and Logical Consequence A sentence is valid if it is true in every possible interpretation. This is predicate logic's version of a tautology. For instance, $∀x \, P(x) → ∀x \, P(x)$ is valid—no matter what domain we choose or what $P$ means, this formula is always true. A sentence is a logical consequence of a set of premises if it is true in every model (interpretation) of those premises. In other words, whenever the premises are all true, the conclusion must be true. This is how we formalize valid reasoning: an argument is valid if its conclusion is a logical consequence of its premises. The Completeness Theorem for First-Order Logic Gödel's completeness theorem is one of the most important results in mathematical logic: If a sentence is true in all models (semantically valid), then there exists a formal proof of that sentence using the rules of first-order predicate logic. This remarkable theorem tells us that the notion of semantic truth (truth in all interpretations) coincides with syntactic derivability (formal provability). It assures us that a well-designed proof system for predicate logic is both sound and complete, capturing exactly the valid sentences. The Compactness Theorem for First-Order Logic The compactness theorem states: If every finite subset of a (possibly infinite) set of first-order sentences has a model, then the entire set has a model. This theorem is subtle but powerful. It tells us that if we have an infinite collection of sentences and we can verify that every finite subset is satisfiable (has a model where all sentences in that subset are true), then we can conclude that all the sentences together are satisfiable. This is useful for proving that certain infinite sets of constraints can all be satisfied simultaneously. Why Formal Logic Matters The ultimate value of formalizing mathematical reasoning is clarity. When we translate informal arguments into formal logical language, hidden assumptions become visible, logical gaps are exposed, and fallacies are prevented. This formalization ensures that mathematical reasoning is rigorous and trustworthy. While propositional and predicate logic may seem mechanical and rigid, they are the bedrock on which all of rigorous mathematics is built.