Chapter 2 - Math. Reasoning, Proofs, and a First Approach to Logic

2.1 Mathematical Statements

TLDR: This section defines mathematical statements as unambiguous sentences that are definitively true or false. It explains how simpler statements can be combined into more complex ones using logical connectives, and highlights how these statements are crucial in computer science for describing properties of programs and systems.

2.1.1 The Concept of a Mathematical Statement

A mathematical statement (also called a proposition) is distinct from everyday statements because it must be unequivocally true or false based on the rules of mathematics. It’s free from subjectivity and ambiguity.

• Example: “71 is a prime number.” This is a mathematical statement because it’s objectively true (71 is only divisible by 1 and itself).

• Example: “Birds can fly.” This is not a mathematical statement. While generally true, there are exceptions (e.g., penguins, ostriches). It lacks the precise truth or falsity required in mathematics.

• Example: “Roger Federer is the best tennis player.” This is subjective and not a mathematical statement. The criteria for “best” aren’t mathematically defined.

• Theorem, Lemma, Corollary: A proven true mathematical statement is often called a theorem (particularly significant results), a lemma (intermediate, often technical results), or a corollary (a direct consequence of a theorem or lemma).

• Conjecture: A statement believed to be true or false but lacking a proof is a conjecture.

• Assumption: In a line of reasoning, we might assume a statement to be true, even if we don’t know for sure ; this is an assumption.

2.1.2 Composition of Mathematical Statements

We can create complex mathematical statements from simpler ones using logical connectives:

• Negation ($\neg$): The negation of a statement $S$ is true if and only if $S$ is false. For example, if $S$ is “4 is even,” then $\neg S$ is “4 is not even” (or “4 is odd”), which is false.

• Conjunction ($\wedge$): A conjunction of two statements $S$ and $T$ (written $S\wedge T$) is true if and only if both $S$ and $T$ are true. For example, “4 is even $\wedge$ 71 is prime” is true. However, “5 is even $\wedge$ 71 is prime” is false because “5 is even” is false.

• Disjunction ($\vee$): A disjunction of two statements $S$ and $T$ (written $S\vee T$) is true if and only if at least one of $S$ and $T$ is true. So “5 is even $\vee$ 71 is prime” is true because “71 is prime” is true.

• Implication ($\Rightarrow$): An implication $S\Rightarrow T$ is true in all cases except when $S$ is true and $T$ is false. It does not imply causality. For example, “4 is even $\Rightarrow$ 71 is prime” is true. Also, “5 is even $\Rightarrow$ 71 is prime” is true (because $S$ is false). Critically, “4 is even $\Rightarrow$ 70 is prime” is false (because $S$ is true and $T$ is false).

• Two-sided implication ($\iff$): $S\iff T$ is true if and only if both $S$ and $T$ have the same truth value (both true or both false). It’s equivalent to $(S\Rightarrow T)\wedge (T\Rightarrow S)$.

2.1.3 Mathematical Statements in Computer Science

In computer science, mathematical statements precisely capture properties of programs, systems, and algorithms. Proving these statements allows us to guarantee correctness, performance, and security.

• Example: “Program $P$ terminates for all inputs.” This is a mathematical statement we’d aim to prove to ensure a program doesn’t enter an infinite loop.
• Example: “Algorithm $A$ solves problem $B$ with accuracy $ϵ$.” This quantifies algorithm performance, a common goal in algorithm design and analysis.
• Example: “Encryption scheme $E$ is secure.” Security properties are formalized as mathematical statements, and their proofs are critical for confidence in security systems. Note: “secure” itself must be mathematically defined.

2.2 The Concept of a Proof

TLDR: This section delves into the nature of mathematical proofs, differentiating between formal and informal approaches. It provides various proof techniques (direct proof, proof by contradiction, proof by induction, etc.), illustrates common pitfalls with examples of false proofs, and emphasizes the role of logic in establishing rigorous mathematical arguments.

2.2.1 Examples of Proofs

A proof rigorously demonstrates the truth of a mathematical statement through a chain of logical steps. Let’s look at some methods:

Example 2.2: Proof by Simple Calculation

Claim: The number $n=2^{11}-1=2047$ is not prime.

Proof: A simple calculation shows that $2047=23\times 89$. Since 2047 has factors other than 1 and itself, it’s not a prime number.

Example 2.2 (Alternative): Proof by Generalization

Claim: If $n$ is not prime, then $2^n-1$ is not prime.

Proof: If $n$ is not prime, then $n=ab$ for some integers $a,b>1$. We can factor $2^n-1$ as follows:

$2^n-1=2^{ab}-1=(2^a{)}^b-1=(2^a-1)((2^a{)}^{b-1}+(2^a{)}^{b-2}+...+2^a+1)$.

Since $a>1$, $2^a-1>1$. And since $b>1$, the second term is also greater than 1. Therefore, $2^n-1$ is a product of two integers larger than 1, meaning it’s composite (not prime). This proves the claim. This is a direct proof which shows the statement is true without resorting to contradiction.

Example 2.3: Proof Using Definitions and Algebraic Properties

Claim: If $a$ and $b$ are perfect squares, then $ab$ is also a perfect square.

Proof:

1. Definition: A number $x$ is a perfect square if there exists an integer $m$ such that $x=m^2$.

2. Assumption: $a$ and $b$ are perfect squares. This means there exist integers $u$ and $v$ such that $a=u^2$ and $b=v^2$.

3. Derivation: $ab=u^2{v}^2=(uv{)}^2$.

4. Conclusion: Since $(uv)$ is an integer, $ab$ is a perfect square by definition.

Example 2.4 (INCORRECT): A Flawed Proof by Induction

Claim: Any $n$ lines in the plane (no two parallel, no three concurrent) intersect at a single point.

Flawed Proof (by induction):

• Base case (n=2): Two non-parallel lines intersect at one point.
• Inductive step: Assume that $n$ lines intersect at a single point. Consider $n+1$ lines. The first $n$ intersect at a point $P$. The last line intersects the first $n$ lines at points $Q_1,...,Q_n$. Since these must all be $P$, they all intersect at $P$.

Flaw: The inductive step is incorrect. While any two lines intersect at a point, there’s no guarantee those intersection points are identical. The problem shows that intuition can be misleading even in simple problems. A correct proof would require different mathematical tools.

Example 2.5 (INCORRECT): A Proof Leading to a False Conclusion

1. Let $a=b$.
2. Multiply both sides by $a$: $a^2=ab$.
3. Subtract $b^2$ from both sides: $a^2-b^2=ab-b^2$.
4. Factor both sides: $(a+b)(a-b)=b(a-b)$.
5. Divide both sides by $(a-b)$: $a+b=b$.
6. Since $a=b$, substitute $a$ for $b$: $a+a=a$, which simplifies to $2a=a$.
7. Divide both sides by $a$: $2=1$.

The Mistake:

The error lies in step 5. We divided both sides of the equation by $(a-b)$. However, since we started with the assumption that $a=b$, then $(a-b)=0$. Division by zero is undefined and invalidates the entire proof. The other steps are mathematically sound but are rendered irrelevant and meaningless because of this initial error. Any result derived from an invalid operation is itself invalid.

In short: The proof manipulates a mathematically true statement ($a=b$) to obtain a false one ($2=1$). This is possible only because the proof relies on an illegal algebraic step—division by zero. This highlights the importance of ensuring that every step in a mathematical proof is valid and does not rely on any undefined operations or logically inconsistent assumptions.

2.2.2 Examples of False Proofs

False proofs appear correct at first glance due to subtle logical errors. They highlight the critical need for rigorous arguments and careful attention to detail. (Example 2.4 and 2.5 are examples of this).

2.2.3 Two Meanings of the Symbol $\Rightarrow$

The symbol $\Rightarrow$ has two distinct but related meanings:

1. Implication: In propositional logic, $P\Rightarrow Q$ is a formula representing the statement “If $P$ is true, then $Q$ is true.” Its truth table is:

P	Q	$P\Rightarrow Q$
True	True	True
True	False	False
False	True	True
False	False	True

2. Logical Consequence: In the context of a proof, $P\models Q$ indicates a derivation. It means that from the truth of $P$, the truth of $Q$ logically follows. This is a semantic concept, relating statements’ truth values, while implication is a syntactic tool for building formulas.

2.2.4 Proofs Using Several Implications

A proof might involve a chain of implications, demonstrating a progression of logical steps. To prove $P\Rightarrow S$, we may show $P\Rightarrow Q$, $Q\Rightarrow R$, $R\Rightarrow S$. Each implication is a separate, proven step.

2.2.5 An Informal Understanding of the Proof Concept

Informally, a proof is a persuasive argument that establishes a statement’s truth. It’s a sequence of clear, easily verifiable steps starting from known facts or axioms, progressing through logical deductions, and arriving at the desired conclusion.

2.2.6 Informal vs. Formal Proofs

• Informal Proofs: Use natural language, making the logical connections implicit rather than explicitly formalizing them in a logical system. They’re easier to understand and communicate, but they can be less precise and may contain hidden assumptions.

• Formal Proofs: Explicity state every step within a formal system, using well-defined rules. The axioms, rules, and logical steps are all explicitly defined, leaving no room for ambiguity or hidden assumptions. This guarantees precision but may be less intuitive.

2.2.7 The Role of Logic

Logic is the foundation of rigorous mathematical reasoning. It provides the formal language and rules for constructing sound and complete proofs. Formal logic helps prevent errors, allows for automatic verification of proofs (by computer), and ensures a deeper understanding of the underlying mathematical relationships.

2.2.8 Proofs in this Course

The course uses primarily informal proofs, balancing mathematical rigor with intuitive accessibility. While formal proofs are referenced for completeness and precision, the emphasis is on clear, understandable reasoning.

2.3 A First Introduction to Propositional Logic

TLDR: This section introduces propositional logic, a formal system for reasoning about truth values. It defines logical constants, operators, and formulas, shows how formulas can be viewed as functions, explores logical equivalence and basic laws, and discusses concepts like logical consequence, tautologies, and satisfiability. The section also briefly touches on the representation of propositional logic using logical circuits.

2.3.1 Logical Constants, Operators, and Formulas

Propositional logic uses symbols to represent statements and their relationships.

Logical Constants:

• True ($T$ or 1): Represents a statement that is always true.
• False ($\perp$ or 0): Represents a statement that is always false.

Logical Operators:

These symbols combine simpler statements into more complex ones:

• Negation ($\neg$): Reverses the truth value of a statement. $\neg P$ is true if $P$ is false, and false if $P$ is true.

• Conjunction ($\wedge$): Represents “and.” $P\wedge Q$ is true if and only if both $P$ and $Q$ are true.

• Disjunction ($\vee$): Represents “or” (inclusive or). $P\vee Q$ is true if and only if at least one of $P$ and $Q$ is true.

• Implication ($\Rightarrow$): Represents “if…then.” $P\Rightarrow Q$ is false only when $P$ is true and $Q$ is false ; otherwise, it’s true. It doesn’t express causality.

• Equivalence ($\iff$): Represents “if and only if.” $P\iff Q$ is true if and only if $P$ and $Q$ have the same truth value (both true or both false).

Formulas:

Formulas are well-formed expressions built from logical constants, variables (representing simple statements), and logical operators. Parentheses control the order of operations, as in standard algebra.

2.3.2 Formulas as Functions

A formula with $n$ variables can be seen as a Boolean function that maps each of the $2^n$ possible combinations of truth values for those variables to a single truth value (True or False).

Example 2.16:

Consider the formula $(A\wedge \neg A)\wedge (B\vee C)$. Regardless of the truth values of $A$, $B$, and $C$, the formula is always false. It represents a function that always outputs 0 (False).

2.3.3 Logical Equivalence and some Basic Laws

Logical Equivalence:

Two formulas are logically equivalent if they have identical truth values for all possible truth assignments to their variables. We denote equivalence by $\equiv$ or $=$.

Basic Laws of Propositional Logic:

These laws describe relationships between formulas:

1. Idempotency: $P\wedge P\equiv P$, $P\vee P\equiv P$. (Repeating a statement has no effect on its truth value).

2. Commutativity: $P\wedge Q\equiv Q\wedge P$, $P\vee Q\equiv Q\vee P$. (Order doesn’t matter for conjunction and disjunction).

3. Associativity: $(P\wedge Q)\wedge R\equiv P\wedge (Q\wedge R)$, $(P\vee Q)\vee R\equiv P\vee (Q\vee R)$. (Grouping in conjunctions and disjunctions doesn’t matter).

4. Distributivity: $P\wedge (Q\vee R)\equiv (P\wedge Q)\vee (P\wedge R)$, $P\vee (Q\wedge R)\equiv (P\vee Q)\wedge (P\vee R)$. (Conjunction distributes over disjunction, and vice versa).

5. Absorption: $P\wedge (P\vee Q)\equiv P$, $P\vee (P\wedge Q)\equiv P$. (Redundant terms can be eliminated).

6. Double Negation: $\neg \neg P\equiv P$. (Negating a negation returns the original statement).

7. De Morgan’s Laws: $\neg (P\wedge Q)\equiv \neg P\vee \neg Q$, $\neg (P\vee Q)\equiv \neg P\wedge \neg Q$. (Negating a conjunction is equivalent to the disjunction of negations, and vice versa).

8. Tautology Laws: $P\vee T\equiv T$, $P\wedge T\equiv P$ (Anything “or” True is True, and anything “and” True remains unchanged).

9. Unsatisfiability Laws: $P\vee \perp \equiv P$, $P\wedge \perp \equiv \perp$ (Anything “or” False remains unchanged, anything “and” False is False).

10. Excluded Middle: $P\vee \neg P\equiv T$ (A statement is either true or false).

11. Contradiction: $P\wedge \neg P\equiv \perp$ (A statement and its negation cannot both be true).

These laws are used to simplify formulas and show their logical equivalence.

Example 2.8:

$A\iff B\equiv (A\Rightarrow B)\wedge (B\Rightarrow A)$. This demonstrates that equivalence can be expressed using implication.

Example 2.9:

$(A\wedge \neg B)\vee (B\wedge \neg C)\equiv (A\vee B)\wedge \neg (B\wedge C)$. This demonstrates a more complex equivalence.

Example 2.10:

$(A\wedge B)\vee C\equiv (A\vee C)\wedge (B\vee C)$. This shows a distributive law.

2.3.4 Logical Consequence (for Propositional Logic)

Logical Consequence:

$P\models Q$ (read as “P logically implies Q”) signifies that whenever $P$ is true, $Q$ must also be true. This is a semantic relationship between formulas ; it means that the truth of Q is guaranteed by the truth of P. It is not a syntactic relationship like implication. This means that if there is no truth assignment where $P$ is true and $Q$ is false, then $P\models Q$.

Example 2.11:

$A\wedge B\models A\vee B$. (If both $A$ and $B$ are true, then at least one of $A$ and $B$ is true).

Example 2.12:

$(A\wedge B)\vee (A\wedge C)\models \neg B\Rightarrow (A\vee C)$. This is a more complex example of logical consequence. This requires demonstrating that there are no truth assignments where $(A\wedge B)\vee (A\wedge C)$ is true, and $\neg B\Rightarrow (A\vee C)$ is false.

Example 2.13:

$(A\Rightarrow B)\wedge (B\Rightarrow C)\models A\Rightarrow C$. (Implication is transitive). This example demonstrates the transitivity of logical consequence.

2.3.5 Lifting Equivalences and Consequences to Formulas

Equivalence Lifting:

If two formulas $P$ and $Q$ are equivalent ($P\equiv Q$), then replacing $P$ with $Q$ (or vice versa) in any larger formula doesn’t change its truth value.

Consequence Lifting:

If $P\models Q$ and $P$ is part of formula $F$, then replacing $P$ with $Q$ in $F$ gives a new formula $F^{\prime }$ where $F\models F^{\prime }$. The resulting formula $F^{\prime }$ will still be a logical consequence of $F$.

2.3.6 Tautologies and Satisfiability

Tautology:

A tautology is a formula that is always true, regardless of the truth values of its variables. We denote this with $\models P$.

Example 2.15:

$A\vee \neg A$ and $(A\wedge (A\Rightarrow B))\Rightarrow B$ are tautologies.

Satisfiable:

A formula is satisfiable if there exists at least one truth assignment for which it’s true.

Unsatisfiable:

A formula is unsatisfiable if it is false for all possible truth assignments. We often write this as $P\equiv \perp$

Lemma 2.2:

A formula $P$ is a tautology if and only if $\neg P$ is unsatisfiable.

Proof: If $P$ is a tautology, it’s always true, so $\neg P$ is always false (unsatisfiable). Conversely, if $\neg P$ is unsatisfiable (always false), then $P$ must be always true (a tautology).

Lemma 2.3:

$P\Rightarrow Q$ is a tautology if and only if $P\models Q$.

Proof:

1. Assume $P\Rightarrow Q$ is a tautology. This means there’s no truth assignment where $P$ is true and $Q$ is false. Thus, whenever $P$ is true, $Q$ must also be true, implying $P\models Q$.

2. Assume $P\models Q$. This means there is no truth assignment where $P$ is true and $Q$ is false. This is the exact definition of $P\Rightarrow Q$ being a tautology. Thus if $P\models Q$ is true, $P\Rightarrow Q$ is a tautology.

2.3.7 Logical Circuits *

Logical circuits are electronic circuits implemented using logic gates (AND, OR, NOT, etc.) that perform the operations of propositional logic. They can physically represent and compute the values of propositional logic formulas.

2.4 A First Introduction to Predicate Logic

TLDR: Predicate logic extends propositional logic by allowing statements about properties of objects and relationships between them. It uses quantifiers ($\forall$ for “for all,” $\exists$ for “there exists”) to make general statements about a universe of objects. The section introduces predicates, functions, and the manipulation of quantifiers, emphasizing the importance of interpretations (which assign meaning to the symbols) and extending concepts like tautologies and logical consequences to this richer logical framework.

2.4.1 Predicates

Definition:

A predicate is a statement containing one or more variables that becomes a proposition (true or false) when specific values are substituted for its variables. The number of variables determines the predicate’s arity.

Examples:

• Example 2.17: Let $P(x)$ be the predicate “x is an even number.” Then $P(2)$ is true, $P(3)$ is false. This is a unary predicate (one variable).

• Example 2.17: Let $Q(x,y)$ be the predicate ”$x$ is less than $y$.” Then $Q(1,2)$ is true, $Q(3,1)$ is false. This is a binary predicate (two variables).

• Example 2.19: Let $prime(x)$ be the predicate ”$x$ is a prime number.” Then $prime(2)$ is true, $prime(4)$ is false. This is again a unary predicate.

• Example 2.20: Fermat’s Last Theorem can be expressed using predicates: $\forall x\forall y\forall z\forall n((n\ge 3)\Rightarrow (x^n+y^n\ne z^n))$ where the universe is the natural numbers, and the predicate indicates whether a specific equation is true or false.

2.4.2 Functions and Constants

Functions

• Definition: A function symbol, $f$, maps a specified number (the arity) of input values from a universe to an output value within that same universe. For a k-ary function, we write $f^{(k)}$.

Examples:

• Example 2.18: $f(x)=x+1$. This is a unary function. $f(2)=3$, $f(5)=6$.

• Example 2.18: $g(x,y)=x\times y$. This is a binary function. $g(2,3)=6$, $g(4,0)=0$.

Constants

A constant symbol is a function with zero arguments ; it simply names a specific value within the universe of discourse.

Examples:

• Example 2.18: In the statement “x > 3,” the ‘3’ is a constant representing the value 3.

2.4.3 The Quantifiers $\exists$ and $\forall$

Quantifiers:

• Existential Quantifier ($\exists$): The symbol $\exists$ means “there exists.” $\exists xP(x)$ means “there exists at least one $x$ such that $P(x)$ is true.”

• Universal Quantifier ($\forall$): The symbol $\forall$ means “for all.” $\forall xP(x)$ means “for all $x$, $P(x)$ is true.”

Examples:

• Example 2.17: $\exists x(x>5)$ means “There exists a number greater than 5,” which is true over the natural numbers.

• Example 2.17: $\forall x(x>0)$ means “All numbers are greater than 0,” which is true over the positive integers but false over the integers (because 0 is not greater than 0).

• Example 2.21: $\forall x\exists y(y>x\wedge prime(y))$ states that for any natural number x, there is a larger prime number y.

2.4.4 Nested Quantifiers

Quantifiers can be nested, creating more complex statements where the order is crucial.

Examples:

• Example 2.18: $\forall x\exists y(y<x)$ means “For every $x$, there exists a $y$ such that $y<x$.” This is true for the set of real numbers or integers but false for the natural numbers (there is a smallest natural number, 0).

• Example 2.18: $\exists y\forall x(y<x)$ means “There exists a $y$ such that $y<x$ for all $x$.” This is false for all number systems.

• Example 2.22: $\forall x(x=0\vee \exists y(xy=1))$ states that “Every number is either 0 or has a multiplicative inverse.” This is true for the set of non-zero rational numbers but is false for the set of integers (e.g., 2 does not have an integer multiplicative inverse).

2.4.5 Interpretation of Formulas

An interpretation gives meaning to the symbols (predicates, functions, and constants) in a predicate logic formula within a specific universe. This provides a concrete way to evaluate the formula’s truth.

Definition:

An interpretation consists of:

1. A universe $U$ (a non-empty set).
2. An assignment of a value in $U$ to each free variable.
3. For each k-ary function symbol $f$, a function $f_U:U^k\to U$.
4. For each k-ary predicate symbol $P$, a function $P_U:U^k\to \{true,false\}$.

Examples:

• Example 6.20: Consider the formula $F=\forall x(P(x)\vee P(f(x,a)))$. One interpretation might be:

• $U=\mathbb{N}$ (natural numbers).

• $a=3$ (a constant).

• $f(x,y)=x+y$ (a function).

• $P(x)=$ ”$x$ is an even number” (a predicate).

With this interpretation, F would be true. A different interpretation might have $U=\mathbb{R}$ (real numbers), $P(x)=$ ”$x>0$,” and $f(x,y)=x\times y$. In this case, F would be false.

2.4.6 Tautologies and Satisfiability

These concepts, already defined for propositional logic, extend to predicate logic with the caveat that we must consider truth values over all possible interpretations.

Definitions:

• Tautology: A formula that is true in every interpretation.
• Satisfiable: A formula that is true in at least one interpretation.
• Unsatisfiable: A formula that is false in every interpretation.

2.4.7 Equivalence and Logical Consequence

These concepts are similar to the propositional case, but we consider all possible interpretations.

Definitions:

• Equivalence: Formulas $P$ and $Q$ are equivalent ($P\equiv Q$) if they have the same truth value under all interpretations.
• Logical Consequence: $P\models Q$ if, for any interpretation where $P$ is true, $Q$ is also true.

Examples:

• Example 2.24: $\forall x(x=0\vee \exists y(xy=1))$ is equivalent to $\forall x(\neg (x=0)\Rightarrow \exists y(xy=1))$.

• This demonstrates an equivalence involving quantifiers.

2.4.8 Some Useful Rules

These informal rules, as in propositional logic, provide guidance for constructing valid arguments but lack the formal structure of rules within a fully defined calculus.

Additional Rules and Examples:

1. Universal Specialization: If $\forall xP(x)$ is true, then $P(c)$ is true for any constant symbol $c$ from the universe. (Similar to universal instantiation but for constants).

2. Existential Generalization: If $P(c)$ is true for some constant symbol $c$, then $\exists xP(x)$ is true. (If we can find one object in the universe that satisfies a property, then there exists at least one object with that property.)

3. Quantifier Movement (Limited): In certain specific cases, the order of quantifiers can be changed. Care is needed ; the truth value will only be preserved under certain conditions. For example:

• $\forall x\forall yP(x,y)\equiv \forall y\forall xP(x,y)$. (The order of universal quantifiers is interchangeable.)
• $\exists x\exists yP(x,y)\equiv \exists y\exists xP(x,y)$. (The order of existential quantifiers is interchangeable.)

However, $\forall x\exists yP(x,y)$ is not generally equivalent to $\exists y\forall xP(x,y)$. But $\exists y\forall xP(x,y)\models \forall x\exists yP(x,y)$ is always true.

These added rules and examples further clarify the use of quantifiers in constructing predicate logic arguments. Remember, these are guidelines, not formal rules within a specific calculus. A formal treatment would require a precisely defined logical calculus.

2.5 Logical Formulas vs. Mathematical Statements

TLDR: This short chapter distinguishes between predicate logic formulas (syntactic objects) and mathematical statements (semantic assertions). A formula only becomes a statement when an interpretation (which assigns meaning to its symbols) is explicitly given. Mathematical statements can then be made about formulas, concerning their truth value, equivalence, or logical consequences.

2.5.1 Fixed Interpretations and Formulas as Statements

A predicate logic formula is a syntactic object, a sequence of symbols, lacking inherent truth value. It only becomes a mathematical statement (true or false) when we provide a fixed interpretation that assigns meanings to its predicates, functions, constants, and universe.

Example:

Consider the formula $\forall x(x>0)$. This is just a formula.

• Interpretation 1: Let the universe be the natural numbers ($\mathbb{N}$). The formula is true since all natural numbers are greater than 0.

• Interpretation 2: Let the universe be the integers ($\mathbb{Z}$). The formula is false because 0 is not greater than 0.

The formula itself is not true or false ; only the formula within a specific interpretation becomes a mathematical statement with a definitive truth value.

2.5.2 Mathematical Statements about Formulas

Once interpretations are given to formulas, we can make mathematical statements about those formulas. These meta-statements concern properties such as truth value, equivalence, or consequence.

Examples:

• “Formula $F$ is a tautology.” This meta-statement asserts that $F$ is true under all possible interpretations.

• “Formula $F$ is satisfiable.” This meta-statement asserts that there exists at least one interpretation where $F$ is true.

• “Formula $F$ is unsatisfiable.” This meta-statement asserts that $F$ is false under all possible interpretations.

• “Formula $P$ logically implies formula $Q$ ($P\models Q$)“. This means that, for any interpretation, if $P$ is true, $Q$ is also true within that interpretation.

• “Formulas $P$ and $Q$ are logically equivalent ($P\equiv Q$)“. This means $P$ and $Q$ have the same truth value under all interpretations.

These statements about formulas are themselves mathematical statements that can be proven or disproven using appropriate logical techniques. They highlight the distinction between the syntax (form) and semantics (meaning) of a formula.

2.6 Some Proof Patterns

TLDR: This section outlines common proof strategies used in mathematics. It covers direct and indirect proofs for implications, modus ponens, proof by cases, proof by contradiction, existence proofs (including the pigeonhole principle), proof by counterexample, and proof by induction. Each method is explained with its underlying logic and illustrated (where possible) with examples.

2.6.1 Composition of Implications

This rule formalizes the idea of chaining implications:

Rule: If $P\Rightarrow Q$ and $Q\Rightarrow R$ are true, then $P\Rightarrow R$ is also true.

Proof (using truth tables): We can construct the truth tables for the implications:

P	Q	$P\Rightarrow Q$	R	$Q\Rightarrow R$	$P\Rightarrow R$	$(P\Rightarrow Q)\wedge (Q\Rightarrow R)\Rightarrow (P\Rightarrow R)$
T	T	T	T	T	T	T
T	T	T	F	F	F	T
T	F	F	T	T	F	T
T	F	F	F	T	F	T
F	T	T	T	T	T	T
F	T	T	F	F	T	T
F	F	T	T	T	T	T
F	F	T	F	T	T	T

The final column shows that the implication $(P\Rightarrow Q)\wedge (Q\Rightarrow R)\Rightarrow (P\Rightarrow R)$ is always true, thus proving the rule. This rule is essentially the transitivity of implication.

2.6.2 Direct Proof of an Implication

This is a fundamental proof technique for implications:

Method: To prove $P\Rightarrow Q$ directly, assume $P$ is true and then logically derive the truth of $Q$.

Example:

Claim: If $n$ is an even integer, then $n^2$ is also an even integer.

Proof:

1. Assumption: $n$ is an even integer. By definition, this means $n=2k$ for some integer $k$.

2. Derivation: $n^2=(2k{)}^2=4k^2=2(2k^2)$.

3. Conclusion: Since $2k^2$ is an integer, $n^2$ is of the form $2\times \text{integer}$, making it an even integer by definition. Therefore, the implication holds.

2.6.3 Indirect Proof of an Implication (Proof by Contradiction)

This approach uses contradiction to prove an implication:

Method: To prove $P\Rightarrow Q$, assume both $P$ and $\neg Q$ are true and then derive a contradiction. The contradiction shows that our initial assumptions must be false, proving $P\Rightarrow Q$.

Example 2.26:

Claim: If $x>0$ is irrational, then $\sqrt{x}$ is irrational.

Proof:

1. Assumptions: $x>0$ is irrational, and $\sqrt{x}$ is rational.

2. Derivation: If $\sqrt{x}$ is rational, then $\sqrt{x}=\frac{m}{n}$ for some integers $m,n$ where $n\ne 0$ and $gcd(m,n)=1$. Squaring both sides gives $x=\frac{m^2}{n^2}$. This implies that $x$ is rational, contradicting the initial assumption that $x$ is irrational.

3. Conclusion: The contradiction arises from the assumption that $\sqrt{x}$ is rational. Therefore, $\sqrt{x}$ must be irrational.

2.6.4 Modus Ponens

A fundamental rule of inference:

Rule: If $P\Rightarrow Q$ is true and $P$ is true, then $Q$ is true.

Proof (using truth tables): The implication $((P\Rightarrow Q)\wedge P)\Rightarrow Q$ is always true.

$P\Rightarrow Q$	P	Q	$(P\Rightarrow Q)\wedge P$	$((P\Rightarrow Q)\wedge P)\Rightarrow Q$
T	T	T	T	T
T	F	F	F	T
F	T	T	F	T
F	F	T	F	T

2.6.5 Case Distinction (Proof by Cases)

This involves dividing a proof into separate cases:

Method: To prove a statement, one breaks the proof down into a set of exhaustive cases. If the statement holds true in each case, it must be true generally.

Example:

Claim: For any integer $n$, $n^3-n$ is divisible by 3.

Proof:

1. Case 1 ($n\equiv 0(\mathrm{mod}3)$): If $n$ is divisible by 3, then $n^3-n=n(n^2-1)=n(n-1)(n+1)$ is also divisible by 3.

2. Case 2 ($n\equiv 1(\mathrm{mod}3)$): If $n$ has a remainder of 1 when divided by 3, then $n-1$ is divisible by 3. Thus $n^3-n$ is divisible by 3.

3. Case 3 ($n\equiv 2(\mathrm{mod}3)$): If $n$ has a remainder of 2 when divided by 3, then $n+1$ is divisible by 3. Thus $n^3-n$ is divisible by 3.

4. Conclusion: Since these cases are exhaustive, $n^3-n$ is divisible by 3 for all integers $n$.

2.6.6 Proofs by Contradiction

This approach proves a statement by showing the opposite leads to a contradiction.

Method: To prove $P$, assume $\neg P$ and derive a logically impossible result (a contradiction). This contradiction shows that $\neg P$ must be false, therefore $P$ must be true.

Example:

Claim: There are infinitely many prime numbers.

Proof:

1. Assumption: Assume a finite number of primes ($p_1,p_2,...,p_n$).

2. Derivation: Construct a new number $x=(p_1\times p_2\times ...\times p_n)+1$. This number is either prime or divisible by a prime not in the original set, contradicting the initial assumption.

3. Conclusion: The assumption of a finite number of primes leads to a contradiction. Therefore, there must be infinitely many prime numbers.

2.6.7 Existence Proofs

This type of proof shows that at least one object with a particular property exists. It doesn’t necessarily tell us how to find that object.

Method: To prove $\exists xP(x)$, you need only find one specific $x$ for which $P(x)$ is true.

Example:

Claim: There exists a prime number $n$ such that $n-10$ and $n+10$ are also prime.

Proof: $n=13$ satisfies the condition since 13, 3, and 23 are all prime. This is a constructive existence proof, as it provides a specific example. Otherwise we call the proof non-constructive.

2.6.8 Existence Proofs via the Pigeonhole Principle

The Pigeonhole Principle states: if $n$ items are put into $m$ containers, with $n>m$, then at least one container must contain more than one item.

Example 2.31:

Claim: In any group of 100 people, at least nine share the same birth month.

Proof: There are 12 months (containers). If we have 100 people (items), then at least $\lceil \frac{100}{12}\rceil =9$ must share a birth month.

2.6.9 Proofs by Counterexample

This method disproves a universal statement.

Method: To disprove $\forall xP(x)$, it suffices to find a single example (a counterexample) where $P(x)$ is false.

Example:

Claim: All even numbers are divisible by 4.

Counterexample: 2 is an even number that is not divisible by 4. This disproves the claim.

2.6.10 Proofs by Induction

This is a powerful technique for proving statements about recursively defined sequences.

Method (Mathematical Induction): To prove that a statement $P(n)$ is true for all natural numbers $n\ge 1$, we follow these steps:

1. Base Case: Prove $P(1)$ (or $P(0)$, depending on the starting point of the sequence).

2. Inductive Step: Assume $P(k)$ is true for some arbitrary $k\ge 1$ (the inductive hypothesis). Prove that $P(k+1)$ is also true.

The base case establishes the starting point. The inductive step shows that if the property holds for a given number, it also holds for the next. By the principle of mathematical induction, the property then holds for all subsequent numbers. It’s like climbing an infinite ladder: If you can reach the first rung and climb from any rung to the next, you can climb to any rung.

Example 2.37:

Claim: Every integer amount of postage greater than or equal to 12 cents can be made using only 4-cent and 5-cent stamps.

Proof:

1. Base Case: 12 cents = 3(4 cents), 15 cents = 3(5 cents)

2. Inductive Hypothesis: Assume that it is possible to form a postage of $k$ cents, where $k\ge 12$, using only 4-cent and 5-cent stamps.

3. Inductive Step: We now need to show that we can also make a postage of $k+1$ cents. Since $k\ge 12$, we have two cases:

• If the postage of $k$ cents contains at least one 5-cent stamp, replace it with two 4-cent stamps ($5=4+1$). This yields a postage of $k+1$ cents.
• If the postage of $k$ cents does not contain any 5-cent stamps, it must consist entirely of 4-cent stamps, and thus $k$ is a multiple of 4. Since $k\ge 12$, we must have $k\ge 16$, so we can replace at least four 4-cent stamps with five 5-cent stamps ($16=4(4)=5(4)-4=20-4$). This yields a postage of $k+1$ cents.

4. Conclusion: By the principle of mathematical induction, the statement is true for all integers $n\ge 12$.

Next Chapter: Chapter 3 - Sets, Relations, and Functions