Agenda

<aside> 📌 Reminders

• Assignment 2 due October 20, 2024 </aside>

🤔 Universal Quantifiers (∀)

Proof Strategy:

• Direct proof: Assume an arbitrary element of the domain, then show that the statement holds for this element.

  Example:

  • Prove: $\forall n \in \mathbb{N}, n^2 \geq 0$
  • Proof: Let $n$ be an arbitrary natural number. If $n \geq 0$ then $n^2 \geq 0$, if $n < 0 \implies n = -1 \times n’, n’ > 0$ so ...

💡 Existential Quantifiers (∃)

Proof Strategy:

• Constructive proof: Find a specific example in the domain that satisfies the property.

  Example:

  • Prove: $\exists n \in \mathbb{N}, n^2 = 4$.
  • Proof: Consider $n = 2\in \mathbb{N}$…

➡️ Implications (P → Q)

Proof Strategies:

• Direct proof: Assume $P$ is true, and logically deduce that $Q$ must follow.

• Contrapositive proof: Sometimes might be easier to prove the logically equivalent statement $\neg Q \rightarrow \neg P$

  Example:

  • Prove: If $n \in \mathbb{N}$ is even, then $n^2$ is even.
  • Proof: Let $n \in \mathbb{N}$ be even, then $n = 2k$ for some $k\in \mathbb{N}$. Then $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$, which is clearly even.

🔄 Logical Equivalence (P ⇔ Q)

Proof Strategy:

• Two-part proof: Prove both $P → Q$ and $Q → P$.

  Example:

  • Prove: $n$ is even ⇔ $n^2$ is even.
  • Proof:
    • (⇒) We already did this!
    • (⇐) Try contrapositive

Practice