Introduction to Logic, Quantifiers, and Proofs

Notation and Foundational Conventions

• Number Sets:

  • Standard natural numbers: $\mathbb{N} = \{0, 1, 2, \dots\}$
  • Positive integers / non-zero natural numbers: $\mathbb{N}^* = \mathbb{N} \setminus \{0\} = \{1, 2, 3, \dots\}$
  • Integers ($\mathbb{Z}$), rational numbers ($\mathbb{Q}$), and real numbers ($\mathbb{R}$) follow standard mathematical definitions.

• Logical Connectives:

  • Negation: $\neg$ ("not")
  • Conjunction: $\land$ ("and")
  • Disjunction: $\lor$ ("or")
  • Implication: $\Rightarrow$ ("implies")
  • Biconditional / Equivalence: $\Leftrightarrow$ ("equivalent" or "if and only if")

• Truth Values:

  • True is designated by $T$ (or the binary digit $1$).
  • False is designated by $F$ (or the binary digit $0$).

• Quantifier Syntax:

  • Universal quantification: $\forall x \in E : P(x)$
  • Existential quantification: $\exists x \in E : P(x)$
  • Consecutive quantifiers are separated by a comma (for example, $\forall x \in \mathbb{R}, \forall y \in \mathbb{R} : x + y = y + x$).

• Numbering Scheme:

  • All definitions, theorems, propositions, examples, and exercises share a single sequential counter within each section (e.g., Theorem 1.3.2 represents the second numbered item of Section 1.3).

Propositional Logic

• Definition 1.1.1 (Proposition):
  • A statement (or proposition) is a declarative sentence that is either true (denoted $T$ or $1$) or false (denoted $F$ or $0$), but not both simultaneously.
  • Fundamental truth table for a proposition $P$:

• Example 1.1.2 (Sentences That Are Propositions):

  • "Socrates was a human." — A proposition because it is a declarative historical assertion that has a definite truth value ($T$).
  • "All cows are brown." — A proposition because it makes a definitive universal assertion that is either true or false (it is false, $F$).
  • "Some triangles have 5 sides." — A proposition (it is false, $F$, because by definition triangles have 3 sides).
  • "There is life on Mars." — A proposition because it asserts an objective fact about reality that is definitively true or false, regardless of whether human science has currently confirmed it.
  • "Humans are just fish with legs." — A proposition (it is a declarative sentence with a truth value, $F$).
  • "Milk is white." — A proposition (it is a declarative sentence with a truth value, $T$).

• Example 1.1.3 (Sentences That Are Not Propositions):

  • "Do you have a dog?" — Not a proposition; it is an interrogative sentence (a question) and therefore cannot be true or false.
  • "Clean your room!" — Not a proposition; it is an imperative sentence (a command/order).
  • "Some coffee mug with a mermaid on it." — Not a proposition; it is an incomplete sentence (a noun phrase lacking a main verb or predicate).
  • "$2x = x + 2$" — Not a proposition; while it is a declarative mathematical sentence, its truth value cannot be determined unless a specific value is assigned to the variable $x$. Without an assignment or a quantifier, it is neither true nor false.

• Exercise 1.1.4 (Evaluating Whether Statements Are Propositions):

  • "I am a dolphin." — A proposition (it is a declarative statement that is false for any human speaker).
  • "Supercalifragilisticexpialidocious." — Not a proposition (an isolated word, not a complete sentence).
  • "Jupiter is the 5th planet from the sun." — A proposition (a declarative assertion that is true, $T$).
  • "On Thursdays, van Gogh painted landscapes." — A proposition (a factual assertion that possesses an objective truth value, $T$ or $F$).

• Taxonomy of Propositions:

  • Atomic (Simple) propositions: Statements that cannot be broken down into simpler constituent propositions (e.g., "$2 + 2 = 4$"). These are traditionally denoted by propositional variables such as $P$, $Q$, $R$, or $A$, $B$.
  • Compound (Complex) propositions: Statements constructed by joining one or more atomic propositions using logical connectives.

Logical Connectives and Truth Tables

• Definition 1.1.5 (Negation):
  • The negation of a proposition $P$ is the proposition $\neg P$, which is true when $P$ is false, and false when $P$ is true.
• Truth table for negation:

• Example 1.1.6:

  • Let $P$: "11 is an even number" (which is false, $F$).
  • Then $\neg P$: "11 is not an even number" is true ($T$).

• Definition 1.1.7 (Conjunction):

  • The conjunction of propositions $P$ and $Q$ is the proposition $P \land Q$ ("$P$ and $Q$"), which is true if both $P$ and $Q$ are true, and false otherwise.
  • Truth table for conjunction:

• Example 1.1.8:

  • Let $P$: "2 divides 9" (false, $F$).
  • Let $Q$: "136 is a multiple of 17" (true, $T$, since $17 \times 8 = 136$).
  • The conjunction $P \land Q$ is false because $P$ is false.

• Definition 1.1.9 (Disjunction):

  • The disjunction of propositions $P$ and $Q$ is the proposition $P \lor Q$ ("$P$ or $Q$"), which is true if at least one of $P, Q$ is true, and false otherwise (inclusive "or").
  • Truth table for disjunction:

• Example 1.1.10:

  • Taking $P$: "2 divides 9" ($F$) and $Q$: "136 is a multiple of 17" ($T$).
  • The disjunction $P \lor Q$: "2 divides 9 or 136 is a multiple of 17" is true because $Q$ is true.

• Definition 1.1.11 (Implication / Conditional):

  • The proposition "$P$ implies $Q$", denoted $P \Rightarrow Q$, is false only when $P$ is true and $Q$ is false. In particular, if $P$ is false, the implication is vacuously true, regardless of the truth value of $Q$.
  • In the conditional statement $P \Rightarrow Q$, $P$ is termed the hypothesis (or antecedent) and $Q$ is termed the conclusion (or consequent).
  • Truth table for implication:

• Example 1.1.12 (Implications Over Real Numbers):

  • Let $x \in \mathbb{R}$:
  1. $(x = 3) \Rightarrow (x^2 = 9)$ is true (since $3^2 = 9$).
  2. $(x^2 = 9) \Rightarrow (x = 3)$ is false (counterexample: $x = -3$ yields $(-3)^2 = 9$, but $-3 \ne 3$).
  3. $(x^2 = 9) \Rightarrow (x = -3 \lor x = 3)$ is true.
  4. $(x > 3) \Rightarrow (x^2 > 9)$ is true.
  5. $(x < -3) \Rightarrow (x^2 > 9)$ is true (e.g., $(-4)^2 = 16 > 9$).
  6. $(x < -3) \Rightarrow (x^2 < 9)$ is false (since any number less than $-3$ has a square strictly greater than $9$).

• Proposition 1.1.13 (Converse, Contrapositive, and Negation of an Implication):

  • For any implication $P \Rightarrow Q$:
  • Its converse is: $Q \Rightarrow P$
  • Its contrapositive is: $\neg Q \Rightarrow \neg P$

• Its negation is: $P \land \neg Q$

• Example 1.1.14:

  • Consider the implication $(n^2 \text{ is even}) \Rightarrow (n \text{ is even})$:
  1. Its converse is $(n \text{ is even}) \Rightarrow (n^2 \text{ is even})$.
  2. Its contrapositive is $(n \text{ is odd}) \Rightarrow (n^2 \text{ is odd})$.
  3. Its negation is $(n^2 \text{ is even}) \land (n \text{ is odd})$.

• Definition 1.1.15 (Biconditional / Equivalence):

  • The proposition $P \Leftrightarrow Q$ ("$P$ is equivalent to $Q$" or "$P$ if and only if $Q$") is true whenever $P$ and $Q$ share identical truth values.
  • It expresses that $P$ is a necessary and sufficient condition for $Q$.
  • It is logically equivalent to the conjunction of two mutual implications: $(P \Rightarrow Q) \land (Q \Rightarrow P)$.
  • Truth table for biconditional:

• Example 1.1.16:

  • For every $x \in \mathbb{R}$:     $x^2 - 1 = 0 \Leftrightarrow (x = -1 \lor x = 1)$
  • This equivalence holds because both the implication $(x^2 - 1 = 0) \Rightarrow (x = -1 \lor x = 1)$ and its converse $((x = -1 \lor x = 1) \Rightarrow (x^2 - 1 = 0))$ are true.

• Precedence of Logical Operators and Complex Truth Tables:

  • The negation connective $\neg$ takes precedence over all other logical connectives unless explicit parentheses mandate otherwise.

• Evaluating compound statements requires systematic truth tables. For instance, analyzing $(P \Rightarrow R) \land (Q \lor \neg R)$:

Logical Equivalence and Fundamental Equivalences

• Definition 1.1.18 (Logical Equivalence):

  • Two propositions $P$ and $Q$ are logically equivalent, written $P \equiv Q$, if they have the exact same truth table—that is, they yield identical truth values for every possible combination of truth assignments to their variables.

• Example 1.1.19 (Proof of Biconditional Equivalence):

  • Proving that $P \Leftrightarrow Q \equiv (P \Rightarrow Q) \land (Q \Rightarrow P)$ by constructing a comparative truth table:

• The fifth and sixth columns match across all four rows, proving the equivalence.

  • Proposition 1.1.20 (Famous Equivalences):

• Let $P$ and $Q$ be arbitrary propositions. The following standard equivalences hold:

  1. Expressing implication as disjunction:        $(P \Rightarrow Q) \equiv (\neg P \lor Q)$

1. Expressing implication as negated conjunction:    $(P \Rightarrow Q) \equiv \neg (P \land \neg Q)$
2. De Morgan's Laws:    $\neg (P \land Q) \equiv \neg P \lor \neg Q$$\neg (P \lor Q) \equiv \neg P \land \neg Q$
3. Double Negation:    $\neg \neg P \equiv P$

Predicates and Quantifiers

• Definition 1.2.1 (Predicate):

  • A predicate is a declarative sentence $P(x)$ or $P(x_1, x_2, \dots, x_n)$ concerning one or more variables.
  • A predicate is not a proposition on its own because its truth value depends directly upon the specific value(s) assigned to its variable(s).

• Definition 1.2.2 (Domain):

  • The domain (or universe) of a variable is the set of all permissible values that the variable may assume within a predicate.

• Components of Quantified Statements:

  • Quantified statements in predicate logic are built from three components: quantifiers, domains, and predicates.

• Example: Let $S$ be the set of all humans, and let $M(x)$ denote the predicate "$x$ is mortal". The statement "All humans are mortal" is formally transcribed as:     $\forall x \in S : M(x)$

  • Definition 1.2.3 (Universal Quantifier $\forall$):

• The universal quantification of a predicate $P(x)$ over a domain $E$ is the proposition:     $\forall x \in E : P(x)$

• It is true if $P(x)$ is true for every element $x \in E$, and false if there exists at least one element in $E$ for which $P(x)$ is false.

• The symbol $\forall$ is read as "for all", "for every", or "for each".

  • Definition 1.2.4 (Existential Quantifier $\exists$):

• The existential quantification of a predicate $P(x)$ over a domain $E$ is the proposition:     $\exists x \in E : P(x)$

• It is true if $P(x)$ is true for at least one element $x \in E$, and false if $P(x)$ is false for every element in $E$.

• The symbol $\exists$ is read as "there exists" or "there is at least one".

  • Definition 1.2.5 (Unique Existential Quantifier $\exists!$):

• The unique existential quantification of a predicate $P(x)$ over a domain $E$ is the proposition:     $\exists! x \in E : P(x)$

• It is true if $P(x)$ is true for exactly one unique element $x \in E$.

• The symbol $\exists!$ is read as "there exists a unique" or "there is exactly one".

  • Example 1.2.6 (Evaluating Quantified Statements):

• $\forall n \in \mathbb{N}^* : n^2 - 1 \ge 0$ is true, because the smallest element of $\mathbb{N}^*$ is $1$, where $1^2 - 1 = 0 \ge 0$, and for any integer $n \ge 2$, $n^2 - 1 > 0$.

• $\forall p \in \mathbb{N} : p \text{ prime} \Rightarrow p^2 \ge 4$ is true, because the smallest prime natural number is $p = 2$, giving $2^2 = 4 \ge 4$, and all subsequent primes satisfy $p \ge 3$, giving $p^2 \ge 9 > 4$.

• $\forall x \in \mathbb{R}, \forall y \in \mathbb{R} : x + y = y + x$ is true, expressing the commutativity of real addition.

• $\exists x \in \mathbb{R} : x^2 = 4$ is true, because an explicit witness exists (e.g., $x = 2$ satisfies $2^2 = 4$).

• $\forall x \in \mathbb{Z}, \exists! y \in \mathbb{Z} : x + y = 0$ is true, because for any integer $x$, its unique additive inverse is $y = -x$.

Negation of Quantified Statements

• Proposition 1.2.7 (Negation Rules for Quantifiers):

  • Distributing a negation across a quantifier changes the quantifier type and negates the inner predicate:     $\neg (\forall x \in E : P(x)) \equiv \exists x \in E : \neg P(x)$$\neg (\exists x \in E : P(x)) \equiv \forall x \in E : \neg P(x)$
  • Operational algorithm for negating consecutive quantifiers:
  1. Invert every universal quantifier to an existential quantifier: $\forall \leftrightarrow \exists$.
  2. Keep the domain set $E$ unchanged.
  3. Pass the negation operator to the right until it is applied directly to the underlying predicate.

• Example 1.2.8 (Negating a Universal-Existential Statement):

  • Problem: Negate $\forall x \in \mathbb{R}, \exists y \in \mathbb{R} : x + y > 0$.
  • Step-by-step derivation:     $\neg [\forall x \in \mathbb{R}, \exists y \in \mathbb{R} : x + y > 0]$$\exists x \in \mathbb{R} : \neg [\exists y \in \mathbb{R} : x + y > 0]$$\exists x \in \mathbb{R}, \forall y \in \mathbb{R} : \neg (x + y > 0)$$\exists x \in \mathbb{R}, \forall y \in \mathbb{R} : x + y \le 0$

• Example 1.2.9 (Negating an Existential-Universal Statement):

  • Problem: Negate $\exists x \in \mathbb{R}, \forall y \in \mathbb{R} : x + y > 0$.
  • Step-by-step derivation:     $\neg [\exists x \in \mathbb{R}, \forall y \in \mathbb{R} : x + y > 0]$$\forall x \in \mathbb{R} : \neg [\forall y \in \mathbb{R} : x + y > 0]$$\forall x \in \mathbb{R}, \exists y \in \mathbb{R} : \neg (x + y > 0)$$\forall x \in \mathbb{R}, \exists y \in \mathbb{R} : x + y \le 0$

Methods of Mathematical Proof

• Principles of Formal Proof:

  • A mathematical proof is a rigorous logical deduction demonstrating that a mathematical theorem must be true under specified axioms and hypotheses.

• Direct Proof:

  • Method: To prove $P \Rightarrow Q$, assume $P$ is true and deduce the truth of $Q$ through definitions, algebraic manipulations, and established facts.
  • Theorem 1.3.1: If $n$ is an even integer, then $n^2$ is even.
  • Proof:
    • Let $n$ be an even integer.
    • By definition of an even integer, $n = 2k$ for some integer $k \in \mathbb{Z}$.
    • Squaring both sides yields:         $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$
    • Since $k \in \mathbb{Z}$, the term $2k^2$ is an integer. Thus, $n^2$ is $2$ times an integer, proving $n^2$ is even.
  • Theorem 1.3.2: If $x$ and $y$ are real numbers, then     $x^2 + y^2 \ge 2xy$
  • Proof:
    • For any real numbers $x, y \in \mathbb{R}$, the square of their difference is non-negative:         $(x - y)^2 \ge 0$
    • Expanding the left-hand side yields:         $x^2 - 2xy + y^2 \ge 0$
    • Adding $2xy$ to both sides of the inequality gives:         $x^2 + y^2 \ge 2xy$

• Proof by Contrapositive:

  • Method: An implication $P \Rightarrow Q$ is logically equivalent to its contrapositive $\neg Q \Rightarrow \neg P$. Proof by contrapositive proceeds by assuming $\neg Q$ (the conclusion is false) and proving $\neg P$ (the hypothesis is false).
  • Theorem 1.3.3: Let $n$ be an integer. If $n^2$ is even, then $n$ is even.
  • Proof:
    • The contrapositive to prove is: If $n$ is not even, then $n^2$ is not even (i.e., if $n$ is odd, then $n^2$ is odd).
    • Assume $n$ is odd. Then $n = 2k + 1$ for some integer $k \in \mathbb{Z}$.
    • Squaring $n$ gives:         $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$
    • Since $k$ is an integer, $2k^2 + 2k$ is an integer. Thus, $n^2$ is written in the form $2m + 1$ where $m = 2k^2 + 2k$, proving that $n^2$ is odd.
    • Because the contrapositive is true, the original implication holds.

• Proof by Contradiction (Reductio Ad Absurdum):

  • Method: To prove a proposition $P$, assume its negation $\neg P$ is true. Follow logical steps until reaching an explicit contradiction (such as $Q \land \neg Q$, or contradicting an axiom or known fact). Conclude that $\neg P$ must be false, meaning $P$ must be true.

• Theorem 1.3.4: There do not exist integers $a$ and $b$ with $b \ne 0$ such that $\sqrt{2} = a/b$. In other words, $\sqrt{2}$ is irrational.

• Proof:

  • Assume, for contradiction, that $\sqrt{2}$ is rational.
  • Then there exist integers $a, b \in \mathbb{Z}$ with $b \ne 0$ such that $\sqrt{2} = a/b$.

• Assume without loss of generality that the fraction $a/b$ is irreducible, meaning $a$ and $b$ share no common factor other than $1$ (i.e., $\gcd(a, b) = 1$).

• Squaring both sides yields:   $2 = \frac{a^2}{b^2}$

• Multiplying by $b^2$:   $a^2 = 2b^2$

• This shows $a^2$ is even. By Theorem 1.3.3, $a$ must also be even.

• Since $a$ is even, $a = 2c$ for some integer $c \in \mathbb{Z}$.

• Substituting this into $a^2 = 2b^2$ gives:   $(2c)^2 = 2b^2$$4c^2 = 2b^2$$b^2 = 2c^2$

• This demonstrates $b^2$ is even. By Theorem 1.3.3, $b$ must also be even.

• Since both $a$ and $b$ are even, $2$ divides both $a$ and $b$, which contradicts the assumption that $\gcd(a, b) = 1$.

• Therefore, the initial assumption is false, and $\sqrt{2}$ is irrational.

Mathematical Induction

• Foundational Concept:

  • Mathematical induction is designed to prove statements indexed by integers, $P(n)$, for all $n \ge n_0$.
  • The domino effect analogy:
  • Falling of the first domino: The base case $P(n_0)$ is proven true.
  • Transmission of impact: The inductive step proves that whenever any domino falls, it knocks down the subsequent domino ($P(n) \Rightarrow P(n + 1)$).
  • Inevitable consequence: Every domino in the infinite chain falls ($P(n)$ holds for all $n \ge n_0$).

• Theorem 1.3.5 (Principle of Mathematical Induction):

  • Let $n_0 \in \mathbb{N}$ and let $P(n_0), P(n_0 + 1), P(n_0 + 2), \dots$ be a family of statements. If:
  1. (Base case): $P(n_0)$ is true, and
  2. (Inductive step): For every integer $n \ge n_0 : P(n) \Rightarrow P(n + 1)$,     then $P(n)$ is true for every integer $n \ge n_0$.

• Theorem 1.3.6 (Sum of the First $n$ Odd Numbers):

  • For every $n \in \mathbb{N}^*$:     $1 + 3 + 5 + \dots + (2n - 1) = \sum_{i=1}^n (2i - 1) = n^2$
  • Inductive pattern discovery:
  • For $n = 1$: $1 = 1^2$
  • For $n = 2$: $1 + 3 = 4 = 2^2$
  • For $n = 3$: $1 + 3 + 5 = 9 = 3^2$
  • For $n = 4$: $1 + 3 + 5 + 7 = 16 = 4^2$
  • For $n = 5$: $1 + 3 + 5 + 7 + 9 = 25 = 5^2$
  • Proof by Induction:
  • Let $P(n)$ denote the statement $\sum_{i=1}^n (2i - 1) = n^2$.
  • Base case ($n = 1$):
    • Left-hand side: $2(1) - 1 = 1$.
    • Right-hand side: $1^2 = 1$.
    • Both sides equal $1$, so $P(1)$ holds.
  • Inductive step:
    • Let $n \in \mathbb{N}^*$ and assume $P(n)$ holds: $1 + 3 + \dots + (2n - 1) = n^2$.
    • We must prove $P(n + 1)$: $1 + 3 + \dots + (2n - 1) + [2(n + 1) - 1] = (n + 1)^2$.
    • Grouping the first $n$ terms and using the induction hypothesis:         $1 + 3 + \dots + (2n - 1) + [2(n + 1) - 1] = n^2 + (2n + 1)$$= n^2 + 2n + 1$$= (n + 1)^2$
    • Thus $P(n + 1)$ holds.
  • By mathematical induction, $P(n)$ is true for all $n \in \mathbb{N}^*$.

• Theorem 1.3.7 (Sum of the First $n$ Even Numbers):

  • For every $n \in \mathbb{N}^*$:     $2 + 4 + 6 + \dots + 2n = \sum_{i=1}^n 2i = n(n + 1)$
  • Proof by Induction:
  • Let $P(n)$ denote the statement $\sum_{i=1}^n 2i = n(n + 1)$.
  • Base case ($n = 1$):
    • Left-hand side: $2(1) = 2$.
    • Right-hand side: $1 \cdot (1 + 1) = 2$.
    • Both sides equal $2$, so $P(1)$ holds.
  • Inductive step:
    • Let $n \in \mathbb{N}^*$ and assume $P(n)$ holds: $2 + 4 + \dots + 2n = n(n + 1)$.
    • We must prove $P(n + 1)$: $2 + 4 + \dots + 2n + 2(n + 1) = (n + 1)[(n + 1) + 1]$.
    • Calculating the sum using the induction hypothesis:         $2 + 4 + \dots + 2n + 2(n + 1) = n(n + 1) + 2(n + 1)$$= (n + 1)(n + 2)$$= (n + 1)[(n + 1) + 1]$
    • Thus $P(n + 1)$ holds.
  • By mathematical induction, $P(n)$ is true for all $n \in \mathbb{N}^*$.

• Theorem 1.3.8 (Geometric Sum Formula):

  • Let $k \in \mathbb{R}$ with $k \ne 1$. Then for every $n \in \mathbb{N}$:     $1 + k + k^2 + \dots + k^n = \sum_{i=0}^n k^i = \frac{k^{n+1} - 1}{k - 1}$

• Proof by Induction:

  • Let $P(n)$ denote the statement $\sum_{i=0}^n k^i = \frac{k^{n+1} - 1}{k - 1}$.
  • Base case ($n = 0$):
  • Left-hand side: $k^0 = 1$.
  • Right-hand side: $\frac{k^{0+1} - 1}{k - 1} = \frac{k - 1}{k - 1} = 1$ (valid since $k \ne 1$).
    • Both sides equal $1$, so $P(0)$ holds.
  • Inductive step:
    • Let $n \in \mathbb{N}$ and assume $P(n)$ holds: $1 + k + \dots + k^n = \frac{k^{n+1} - 1}{k - 1}$.
    • We must prove $P(n + 1)$: $1 + k + \dots + k^n + k^{n+1} = \frac{k^{n+2} - 1}{k - 1}$.
    • Adding $k^{n+1}$ to both sides of the inductive hypothesis:         $1 + k + \dots + k^n + k^{n+1} = \frac{k^{n+1} - 1}{k - 1} + k^{n+1}$$= \frac{k^{n+1} - 1 + k^{n+1}(k - 1)}{k - 1}$$= \frac{k^{n+1} - 1 + k^{n+2} - k^{n+1}}{k - 1}$$= \frac{k^{n+2} - 1}{k - 1}$
    • Thus $P(n + 1)$ holds.
  • By mathematical induction, $P(n)$ is true for all $n \in \mathbb{N}$.

• Exercise 1.3.9 (Demonstrating Four Proof Methods on One Proposition):

  • Proposition: Let $n$ be an integer. The sum of any two consecutive integers is odd, i.e., $n + (n + 1)$ is odd.
  • Method 1: Direct Proof:
  • Algebraic simplification gives $n + (n + 1) = 2n + 1$.
  • Since $n$ is an integer, $2n + 1$ satisfies the explicit definition of an odd integer ($2k + 1$ with $k = n \in \mathbb{Z}$).
  • Method 2: Proof by Contrapositive:
  • Prove that if $n + (n + 1)$ is not odd (i.e., even), then the integers cannot be consecutive.
  • Suppose $n + (n + 1) = 2k$ for some integer $k$.
  • Then $2n + 1 = 2k$, which implies $2(k - n) = 1$, meaning $k - n = \frac{1}{2}$.
  • Since $k, n \in \mathbb{Z}$, their difference must be an integer, which contradicts $k - n = \frac{1}{2} \notin \mathbb{Z}$.

• Method 3: Proof by Contradiction:

  • Assume that there exists an integer $n$ such that $n + (n + 1)$ is even.
  • Then $2n + 1 = 2k$ for some $k \in \mathbb{Z}$.
  • Rearranging gives $1 = 2(k - n)$, stating that $1$ is an even integer (divisible by $2$), which is a contradiction.

• Method 4: Proof by Mathematical Induction (for $n \in \mathbb{N}$):

  • Base case ($n = 0$): $0 + (0 + 1) = 1$, which is odd.
  • Inductive step: Assume $n + (n + 1) = 2k + 1$ for some $k \in \mathbb{Z}$.
  • For $n + 1$, the sum of consecutive integers is:     $(n + 1) + ((n + 1) + 1) = (n + 1) + (n + 2) = [n + (n + 1)] + 2$
  • Substituting the induction hypothesis yields $(2k + 1) + 2 = 2(k + 1) + 1$.
  • Since $k + 1 \in \mathbb{Z}$, the sum is odd.

Disproof by Counterexample

• Definition and Mechanism:

  • A universal statement of the form $\forall x : P(x) \Rightarrow Q(x)$ is disproved by establishing the existence of a single element $x_0$ that satisfies the hypothesis $P(x_0)$ while violating the conclusion ($\neg Q(x_0)$).

• The element $x_0$ is called a counterexample.

• Finding a single valid counterexample proves the negation $\exists x_0 : P(x_0) \land \neg Q(x_0)$, thereby entirely refuting the universally quantified claim.

• Example 1.3.10 (Disproving Universal Statements via Counterexample):

  1. Statement: $\forall n \in \mathbb{N} : n \text{ prime} \Rightarrow n \text{ odd}$
  • Evaluation: False.
  • Counterexample: Consider $n = 2$. The integer $2$ is prime (satisfies the hypothesis), but $2$ is even (violates the conclusion). Therefore, $n = 2$ serves as a counterexample.
  1. Statement: $\forall n \in \mathbb{N} : n^2 + n + 41 \text{ is a prime number}$
  • Evaluation: False.
  • While the formula generates prime numbers for values $0 \le n \le 39$, testing $n = 41$ gives:        $41^2 + 41 + 41 = 1681 + 41 + 41 = 1763 = 41 \times 43$
  • Since $1763$ has non-trivial factors ($41$ and $43$), it is composite.
  • Thus, $n = 41$ is a valid counterexample, disproving the statement.