Logic and Induction Flashcards

Foundations and Key Concepts of Mathematics

• Historical Perspective:

  • Simon Stevin (17th century) defined mathematics using the Dutch term wisconst, which translates to the "art of the certain" ("kunst van het gewisse").

• Core Building Blocks of Mathematics:

  • Axioms: Statements accepted as foundational truths without proof.
  • Example: Every natural number $n$ has a successor.
  • Definitions: Formal and precise descriptions of concepts or mathematical terms.
  • Example: A natural number $p$ is defined as a prime number if it cannot be expressed as the product of two numbers that are both unequal to $p$.
  • Theorems: Mathematical assertions and results derived logically from previously established axioms, definitions, and theorems.
  • Example: The square of an odd number is always an odd number.
  • Proofs: Rigorous logical derivations of a theorem starting from axioms, definitions, and prior theorems.

Proof Structure: Direct Proof Example

• Theorem Statement:

  • If $k$ is an odd integer, then $k^2$ is also an odd integer.

• Definition of an Odd Integer:

  • An integer $x$ is defined as odd if there exists an integer $n$ such that $x = 2n + 1$

• Step-by-Step Direct Proof:

  • Let $k$ be an arbitrary odd integer.
  • Objective: Prove that $k^2$ is an odd integer.
  • Apply the definition of an odd integer to $k$:
  • There exists an integer $n$ such that $k = 2n + 1$
  • Square both sides of the equality:
  • $k^2 = (2n + 1)^2 = 4n^2 + 4n + 1$
  • Factor out $2$ from the quadratic and linear terms:
  • $k^2 = 2(2n^2 + 2n) + 1$
  • Define $m = 2n^2 + 2n$. Since $n$ is an integer, $m$ is also an integer ($m \in \mathbb{Z}$).
  • Substitute $m$ back into the equation:
  • $k^2 = 2m + 1$
  • By definition, any integer expressed in the form $2m + 1$ (where $m \in \mathbb{Z}$) is odd.
  • Conclusion: $k^2$ is odd.

Propositional Logic and Compound Statements

• Definition of Logical Statements:

  • Logical reasoning is built upon assertions or statements (propositions) that possess a definite truth value, meaning they can be evaluated unambiguously as either true ($T$) or false ($F$).

• Propositional Variables:

  • Statements are symbolized using proposition letters such as $P$, $Q$, and $R$:
  • $P$: "my hair is blue"
  • $Q$: "3 is a prime number"
  • $R$: "all birds can fly"

• Compound Propositions:

  • Basic statements can be combined using logical operators to form compound statements:
  • Negation ("Not $P$"): "my hair is not blue"
  • Conjunction ("$P$ and $Q$"): "my hair is blue and 3 is a prime number"
  • Implication ("If $Q$, then $R$"): "if 3 is a prime number, then all birds can fly"

Logical Connectives and Truth Tables

• Logical Connectives Overview:

  • Negation: $\neg P$ (read as "not $P$")
  • Conjunction: $P \land Q$ (read as "$P$ and $Q$")
  • Disjunction: $P \lor Q$ (read as "$P$ or $Q$")
  • Implication: $P \Rightarrow Q$ (read as "if $P$, then $Q$")
  • Equivalence: $P \Leftrightarrow Q$ (read as "$P$ if and only if $Q$")

• Truth Table for Negation ($\neg P$):

  • When $P$ is $T$, $\neg P$ is $F$.
  • When $P$ is $F$, $\neg P$ is $T$.

• Truth Table for Conjunction ($P \land Q$):

  • $P = T$, $Q = T \implies P \land Q = T$
  • $P = T$, $Q = F \implies P \land Q = F$
  • $P = F$, $Q = T \implies P \land Q = F$
  • $P = F$, $Q = F \implies P \land Q = F$
  • Rule: Conjunction is true if and only if both statements $P$ and $Q$ are true.

• Truth Table for Disjunction ($P \lor Q$):

  • $P = T$, $Q = T \implies P \lor Q = T$
  • $P = T$, $Q = F \implies P \lor Q = T$
  • $P = F$, $Q = T \implies P \lor Q = T$
  • $P = F$, $Q = F \implies P \lor Q = F$
  • Rule: Disjunction is true if at least one of the constituent statements is true.

Truth Table Analysis: Implication and Equivalence

• Evaluation of Material Implication ($P \Rightarrow Q$):

  • "If 2 is even, then 3 is odd": True ($T \Rightarrow T$ evaluates to $T$).
  • "If 2 is even, then 3 is even": False ($T \Rightarrow F$ evaluates to $F$).
  • "If 2 is odd, then 3 is odd": True ($F \Rightarrow T$ evaluates to $T$).
  • "If 2 is odd, then 3 is even": True ($F \Rightarrow F$ evaluates to $T$).

• Complete Truth Table for Implication ($P \Rightarrow Q$):

  • $P = T$, $Q = T \implies P \Rightarrow Q = T$
  • $P = T$, $Q = F \implies P \Rightarrow Q = F$
  • $P = F$, $Q = T \implies P \Rightarrow Q = T$
  • $P = F$, $Q = F \implies P \Rightarrow Q = T$
  • Key Property: An implication $P \Rightarrow Q$ is false if and only if the premise $P$ is true and the conclusion $Q$ is false. If the premise $P$ is false, the implication is vacuously true regardless of $Q$

• Complete Truth Table for Equivalence ($P \Leftrightarrow Q$):

  • $P = T$, $Q = T \implies P \Leftrightarrow Q = T$
  • $P = T$, $Q = F \implies P \Leftrightarrow Q = F$
  • $P = F$, $Q = T \implies P \Leftrightarrow Q = F$
  • $P = F$, $Q = F \implies P \Leftrightarrow Q = T$
  • Key Property: Equivalence is true when both statements share the exact same truth value.

Multi-Variable Truth Table Construction

• Constructing the Truth Table for $(P \land Q) \Rightarrow R$
  • Total number of truth rows for 3 propositions: $2^3 = 8$ rows.
  • Complete truth values:
  • Row 1: $P = T$, $Q = T$, $R = T \implies P \land Q = T \implies (P \land Q) \Rightarrow R = T$
  • Row 2: $P = T$, $Q = T$, $R = F \implies P \land Q = T \implies (P \land Q) \Rightarrow R = F$
  • Row 3: $P = T$, $Q = F$, $R = T \implies P \land Q = F \implies (P \land Q) \Rightarrow R = T$
  • Row 4: $P = T$, $Q = F$, $R = F \implies P \land Q = F \implies (P \land Q) \Rightarrow R = T$
  • Row 5: $P = F$, $Q = T$, $R = T \implies P \land Q = F \implies (P \land Q) \Rightarrow R = T$
  • Row 6: $P = F$, $Q = T$, $R = F \implies P \land Q = F \implies (P \land Q) \Rightarrow R = T$
  • Row 7: $P = F$, $Q = F$, $R = T \implies P \land Q = F \implies (P \land Q) \Rightarrow R = T$
  • Row 8: $P = F$, $Q = F$, $R = F \implies P \land Q = F \implies (P \land Q) \Rightarrow R = T$

Logical Equivalence Analysis

• Definition of Logical Equivalence:

  • Two logical formulas are defined as logically equivalent if and only if they yield identical truth values for every possible combination of truth values of their constituent propositional variables.

• Equivalence Proof Exercise: Comparing $(P \Rightarrow Q) \land (Q \Rightarrow P)$ and $P \Leftrightarrow Q$

  • Row 1 ($P = T$, $Q = T$
  • $P \Rightarrow Q = T$
  • $Q \Rightarrow P = T$
  • $(P \Rightarrow Q) \land (Q \Rightarrow P) = T$
  • $P \Leftrightarrow Q = T$
  • Row 2 ($P = T$, $Q = F$
  • $P \Rightarrow Q = F$
  • $Q \Rightarrow P = T$
  • $(P \Rightarrow Q) \land (Q \Rightarrow P) = F$
  • $P \Leftrightarrow Q = F$
  • Row 3 ($P = F$, $Q = T$
  • $P \Rightarrow Q = T$
  • $Q \Rightarrow P = F$
  • $(P \Rightarrow Q) \land (Q \Rightarrow P) = F$
  • $P \Leftrightarrow Q = F$
  • Row 4 ($P = F$, $Q = F$
  • $P \Rightarrow Q = T$
  • $Q \Rightarrow P = T$
  • $(P \Rightarrow Q) \land (Q \Rightarrow P) = T$
  • $P \Leftrightarrow Q = T$
  • Conclusion: Because the final columns for $(P \Rightarrow Q) \land (Q \Rightarrow P)$ and $P \Leftrightarrow Q$ are identical in all 4 rows ($T, F, F, T$), the two formulas are logically equivalent.

Set Theory and Standard Number Sets

• Fundamentals of Sets:

  • A set is defined as an unordered collection of distinct objects.
  • Example: Set $Z = \{\text{cow}, \text{pig}, \text{elephant}\}$.
  • Objects within a set are called elements.
  • Membership Notation: $\text{cow} \in Z$ denotes that "cow is an element of set $Z$".

• Standard Sets of Numbers:

  • Empty Set: $\emptyset = \{\}$ (contains no elements).
  • Set of Natural Numbers: $\mathbb{N} = \{1, 2, 3, \dots\}$
  • Set of Integers: $\mathbb{Z} = \{\dots, -2, -1, 0, 1, 2, \dots\}$
  • Set of Rational Numbers: $\mathbb{Q} = \left\{\frac{p}{q} : p, q \in \mathbb{Z} \text{ and } q \neq 0\right\}$
  • Set of Real Numbers: $\mathbb{R}$
  • Closed Interval: $[a, b] = \{x \in \mathbb{R} : a \le x \le b\}$

Quantifiers and Predicate Logic

• Logical Quantifiers:

  • Universal Quantifier ($\forall$): Symbolizes "for all" or "for every".
  • Existential Quantifier ($\exists$): Symbolizes "there exists at least one".

• Formalizing Expressions with Quantifiers:

  • Statement: "There exists a number greater than 3"
  • Formal expression: $\exists n, n > 3$
  • Statement: "Every natural number is positive"
  • Formal expression: $\forall n, (n \in \mathbb{N} \Rightarrow n > 0)$

• Importance of Universe of Discourse (Context):

  • The truth value of quantified statements depends strictly on the set or universe of discourse being considered.
  • Example: The statement $\exists n, n > 3$ is true in the universe of real numbers $\mathbb{R}$, but false in the restricted universe of the closed interval $[0, 1]$.

Truth Evaluation of Quantified Statements

• Example 1: $\forall n \in \mathbb{N}, n + 1 > n$

  • Status: True ($T$). Adding 1 to any natural number always yields a strictly larger number.

• Example 2: $\forall x \in \mathbb{Q}, x^2 - 1 = 0$

  • Status: False ($F$).
  • Counterexample: Choose $x = \frac{1}{2} \in \mathbb{Q}$. Then $\left(\frac{1}{2}\right)^2 - 1 = \frac{1}{4} - 1 = -\frac{3}{4} \neq 0$

• Example 3: $\forall x, y \in \mathbb{R}, x^2 + y^2 \ge 0$

  • Status: True ($T$). The square of any real number is non-negative, so the sum of two squares is always greater than or equal to zero.

• Example 4: $\exists x \in \mathbb{Z}, x^2 - 1 = 0$

  • Status: True ($T$).
  • Example: Choose $x = 1 \in \mathbb{Z}$, which satisfies $1^2 - 1 = 0$

• Example 5: $\exists n \in \mathbb{N}, n^2 = 2$

  • Status: False ($F$). The square root of 2 ($\sqrt{2}$) is irrational and thus not a natural number ($\sqrt{2} \notin \mathbb{N}$).

Proofs by Mathematical Induction

• Principle of Mathematical Induction (Principe van Volledige Inductie):
  • To prove that a statement $P(n)$ holds for all natural numbers $n \in \mathbb{N}$, it is necessary and sufficient to demonstrate two essential steps:
  1. Base Step: Show that the statement holds for $n = 1$ (i.e., $P(1)$ is true).
  2. Inductive Step: Show that if the statement holds for an arbitrary natural number $n$ (i.e., assuming $P(n)$ is true), then it must also hold for $n + 1$ (i.e., $P(n+1)$ is true).
  • Visual Conceptual Model:
  • Induction acts like a chain reaction or set of falling dominoes, propagating truth from $1 \to 2 \to 3 \to \dots \to n \to n+1 \to \dots$

Induction Proof Example 1: Sum of Natural Numbers

• Claim: For all $n \in \mathbb{N}$, statement $P(n)$ holds:

  • $1 + 2 + \dots + n = \frac{n(n+1)}{2}$

• Step-by-Step Proof:

  • Base Step ($n = 1$):
  • Left-hand side: $1$
  • Right-hand side: $\frac{1 \times (1 + 1)}{2} = \frac{1 \times 2}{2} = 1$
  • Both sides are equal. Therefore, $P(1)$ holds.
  • Induction Hypothesis (IH):
  • Assume $P(n)$ holds for an arbitrary $n \in \mathbb{N}$.
  • $1 + 2 + \dots + n = \frac{n(n+1)}{2}$
  • Inductive Step:
  • Prove $P(n+1)$ holds:
  • $1 + 2 + \dots + n + (n + 1)$
  • Substitute the Induction Hypothesis for the sum of the first $n$ terms:
  • $= \frac{n(n+1)}{2} + (n + 1)$
  • Find a common denominator:
  • $= \frac{n^2 + n}{2} + \frac{2(n + 1)}{2}$
  • $= \frac{n^2 + n + 2n + 2}{2}$
  • Combine terms in the numerator:
  • $= \frac{n^2 + 3n + 2}{2}$
  • Factor the quadratic expression in the numerator:
  • $= \frac{(n + 1)(n + 2)}{2}$
  • Notice that this expression matches the formula for $n + 1$: $\frac{(n+1)((n+1)+1)}{2}$.
  • Conclusion:
  • By the Principle of Mathematical Induction, $P(n)$ holds for all $n \in \mathbb{N}$.

Induction Proof Example 2: Divisibility Proof

• Claim: Prove that $2^{3n} - 1$ is divisible by $7$ for all $n \in \mathbb{N}$.

• Step-by-Step Proof:

  • Base Step ($n = 1$):
  • Evaluate for $n = 1$:
  • $2^{3 \times 1} - 1 = 2^3 - 1 = 8 - 1 = 7$
  • Since $7$ is divisible by $7$, the statement holds for $n = 1$.
  • Induction Hypothesis (IH):
  • Assume that $2^{3n} - 1$ is divisible by $7$ for an arbitrary $n \in \mathbb{N}$.
  • By definition of divisibility, there exists an integer $k \in \mathbb{Z}$ such that:
  • $2^{3n} - 1 = 7k \implies 2^{3n} = 7k + 1$
  • Inductive Step:
  • Prove that $2^{3(n+1)} - 1$ is divisible by $7$:
  • $2^{3(n+1)} - 1 = 2^{3n + 3} - 1$
  • Use exponent laws to separate $2^3$:
  • $= 2^{3n} \times 2^3 - 1 = 8 \times 2^{3n} - 1$
  • Substitute the Induction Hypothesis ($2^{3n} = 7k + 1$):
  • $= 8 \times (7k + 1) - 1$
  • Expand the expression:
  • $= 56k + 8 - 1 = 56k + 7$
  • Factor out $7$:
  • $= 7 \times (8k + 1)$
  • Define $m = 8k + 1$. Since $k \in \mathbb{Z}$, $m \in \mathbb{Z}$.
  • Thus, $2^{3(n+1)} - 1 = 7m$, which is a multiple of $7$
  • Conclusion:
  • The claim holds for $n + 1$. By the Principle of Mathematical Induction, $2^{3n} - 1$ is divisible by $7$ for all $n \in \mathbb{N}$.

Set Theory Foundations and Russell's Paradox

• Definition of Russell's Paradox:

  • Consider the set $S$ defined as the set of all sets that are not elements of themselves:
  • $S = \{K : K \text{ is a set and } K \notin K\}$

• Logical Analysis of Set Membership:

  • Evaluate whether $S \in S$:
  • Case 1: Assume $S \in S$.
    • By the defining condition of $S$, any element $K \in S$ must satisfy $K \notin K$. Therefore, $S \notin S$. This is a direct contradiction!
  • Case 2: Assume $S \notin S$.
    • By the defining condition of $S$, any set $K$ that satisfies $K \notin K$ must belong to $S$. Therefore, $S \in S$. This is also a direct contradiction!

• Mathematical Implications:

  • Neither case is logically possible.
  • Conclusion: The set $S$ cannot exist under naive set theory. Not every arbitrary collection or logical rule forms a valid mathematical set.