Quantifiers & Implications Summary

Statements vs Open Statements

• Statement: A sentence with a definite truth value (True/False)
• Open Statement: Contains a free variable; truth value depends on variable

Examples:

1. (2 + 2 = 4) → Statement
2. (x + 2 = 5) → Open statement (depends on (x))
3. “Close the door” → Not a statement

---

Variables in Logic

• Bound Variable: Variable whose scope is restricted by quantifiers

  • Example: (\forall x \in \mathbb{Z}, x^2 \ge 0) → (x) is bound

• Free Variable: Variable not restricted by quantifiers; truth depends on value

  • Example: (P(x) = x^2 = 4) → Truth depends on (x)

---

Sets and Membership

• Definition: A collection of objects/elements
• Set notation with conditions:

$$A = {x \mid x \text{ is prime}}$$

• Membership: (x \in A) → x belongs to set A
• Subset: (B \subseteq A) → all elements of B are in A

Example:

$${x \in \mathbb{Z} \mid x^2 = 1} = {-1, 1}$$

---

Quantifiers

1. Universal Quantifier: (\forall x \in D, P(x)) → “For all x in domain D, P(x) is true”
2. Existential Quantifier: (\exists x \in D, P(x)) → “There exists at least one x in D such that P(x) is true”

Negation Rules:

$$\neg (\forall x, P(x)) \equiv \exists x, \neg P(x)$$ $$\neg (\exists x, P(x)) \equiv \forall x, \neg P(x)$$

---

Implications in Logic

• Implication: (p \to q) → False only if (p) is True and (q) is False
• Negation:

$$\neg(p \to q) \equiv p \land \neg q$$

Example:

$$\forall x \in \mathbb{Z},; (x > 0 \to x^2 > 0)$$

Negation:

$$\exists x \in \mathbb{Z},; (x > 0 \land x^2 \le 0)$$

---

Nested Quantifiers

• Example:

$$\forall x \in \mathbb{Z},; \exists y \in \mathbb{Z},; x < y$$

• English: “Every integer has a larger integer” ✅

• Negation:

$$\exists x \in \mathbb{Z},; \forall y \in \mathbb{Z},; x \ge y$$

• Truth: Original True, Negation False

• Tip: Order of quantifiers matters drastically.

  • (\forall x \exists y) ≠ (\exists y \forall x)

---

Drills & Examples

Single Quantifier + Implication

$$\forall x \in \mathbb{Z}^+, \exists y \in \mathbb{Z}^+, (y > x \to y^2 > x)$$

• Negation:

$$\exists x \in \mathbb{Z}^+, \forall y \in \mathbb{Z}^+, (y > x \land y^2 \le x)$$

Truth Evaluation

$$\exists x \in \mathbb{Z},; \forall y \in \mathbb{Z},; (x + y > 0) ;;\text{False}$$

Reason: No integer (x) works for all (y)

---

Key Lessons Learned

1. Always translate English → symbols → evaluate

2. Check bound vs free variables

3. Negate quantifiers carefully:

   • Flip quantifiers
   • Apply (\neg(p \to q) = p \land \neg q)

4. Multi-quantifier statements are tricky → check order and counterexamples

5. Implications often produce vacuous truths when hypothesis is false