List the negation of quantifier with example. Prove that √2 is irrational.

---

Negation of Quantifiers with Example

Quantifiers are logical operators used to express the quantity of elements in a set or domain that satisfy a given predicate. There are two primary types of quantifiers:

1. Universal Quantifier (∀): "For all" or "For every."

   • Symbol: ∀
   • Example: ∀x ∈ S, P(x) means "For all x in set S, P(x) is true."

2. Existential Quantifier (∃): "There exists" or "For some."

   • Symbol: ∃
   • Example: ∃x ∈ S, Q(x) means "There exists an x in set S such that Q(x) is true."

Negation of Quantifiers

The negation of a quantified statement follows these rules:

1. Negation of Universal Quantifier (∀)

   • Original: ∀x ∈ S, P(x)
   • Negation: ∃x ∈ S, ¬P(x)
   • Explanation: The negation of "all x satisfy P(x)" is "there exists at least one x that does not satisfy P(x)."

   Example:

   • Original: ∀x ∈ ℕ, x² ≥ x (For all natural numbers x, x² is greater than or equal to x.)
   • Negation: ∃x ∈ ℕ, x² < x (There exists a natural number x such that x² is less than x.)
   • Verification: For x = 0 (if included in ℕ), 0² = 0 is not greater than 0. Thus, the negation holds.

2. Negation of Existential Quantifier (∃)

   • Original: ∃x ∈ S, Q(x)
   • Negation: ∀x ∈ S, ¬Q(x)
   • Explanation: The negation of "there exists an x such that Q(x)" is "for all x, Q(x) is not true."

   Example:

   • Original: ∃x ∈ ℤ, x + 5 = 0 (There exists an integer x such that x + 5 = 0.)
   • Negation: ∀x ∈ ℤ, x + 5 ≠ 0 (For all integers x, x + 5 is not equal to 0.)
   • Verification: The original statement is true for x = -5. The negation is false because x = -5 satisfies x + 5 = 0.

---

Proof that √2 is Irrational

An irrational number is a real number that cannot be expressed as a ratio of two integers (i.e., a fraction $\frac{a}{b}$ where $a$ and $b$ are integers and $b\ne 0$). We will prove that $\sqrt{2}$ is irrational using proof by contradiction.

Proof Steps

1. Assume the opposite: Suppose $\sqrt{2}$ is rational. Then, it can be written as a reduced fraction: $$\sqrt{2}=\frac{a}{b}$$ where $a$ and $b$ are integers with no common factors (i.e., the fraction is in its simplest form), and $b\ne 0$.

2. Square both sides: $$(\sqrt{2}{)}^2={\left(\frac{a}{b}\right)}^2⟹2=\frac{a^2}{b^2}$$ $$⟹2b^2=a^2$$

3. Analyze the equation $2b^2=a^2$:

   • This implies that $a^2$ is even (since it is equal to $2b^2$, which is clearly even).
   • If $a^2$ is even, then $a$ must also be even (because the square of an odd number is odd).
   • Let $a=2k$ for some integer $k$.

4. Substitute $a=2k$ into the equation: $$2b^2=(2k{)}^2⟹2b^2=4k^2$$ $$⟹b^2=2k^2$$

5. Analyze $b^2=2k^2$:

   • This implies that $b^2$ is even, and thus $b$ must also be even.

6. Contradiction:

   • We have shown that both $a$ and $b$ are even, meaning they have a common factor of 2.
   • This contradicts our initial assumption that $\frac{a}{b}$ is in its simplest form (i.e., $a$ and $b$ have no common factors).

7. Conclusion:

   • Since our assumption that $\sqrt{2}$ is rational leads to a contradiction, the assumption must be false.
   • Therefore, $\sqrt{2}$ is irrational.

---

Key Takeaways

• The negation of quantifiers flips the type (∀ becomes ∃ and vice versa) and negates the predicate.
• Proof by contradiction is a powerful technique in mathematics, especially for proving the irrationality of numbers.
• The proof of $\sqrt{2}$ being irrational is foundational in number theory and demonstrates the importance of logical rigor.