Q.Show that the set of all prime numbers is infinite.

In mathematics, a "proof" is a rigorous, logical argument that establishes the truth of a statement. Unlike scientific theories, which are supported by evidence and can be disproven by new observations, mathematical theorems, once proven, are considered absolutely true within the given system of axioms and definitions.

Why Do We Need Proofs?

Imagine you observe that the sum of two odd numbers is always an even number:

• $1 + 3 = 4$ (even)
• $5 + 7 = 12$ (even)
• $11 + 9 = 20$ (even)

You could test many pairs of odd numbers, and each time you'd find their sum is even. This might make you believe the statement is true. However, no matter how many examples you check, you can never check all possible pairs of odd numbers. There's always a chance that the very next pair you haven't checked might break the pattern.

This is where proofs come in. A proof doesn't just show that a statement is true for some examples; it shows that it must be true for all cases that fit the description, based on fundamental definitions and logical rules. It provides absolute certainty.

What is a Proof?

A proof is a sequence of logical deductions, starting from known facts (like definitions, axioms, or previously proven theorems) and leading step-by-step to the conclusion you want to establish. Each step must be justified by a rule of logic or a known mathematical truth.

We use different "methods of proof" depending on the nature of the statement we want to prove. These methods are strategies for constructing a valid logical argument.

Common Methods of Proof

Here are some of the most common methods of proof:

1. Direct Proof

This is the most straightforward method. To prove a statement of the form "If $P$, then $Q$" (denoted $P \implies Q$), you assume that $P$ is true and then use definitions, axioms, and logical deductions to show that $Q$ must also be true.

Example: Prove that the sum of two even integers is an even integer.

Proof:

Let $a$ and $b$ be two even integers.

By the definition of an even integer, an integer is even if it can be written in the form $2k$ for some integer $k$.

So, we can write $a = 2m$ for some integer $m$, and $b = 2n$ for some integer $n$.

Now, consider their sum:

$a + b = 2m + 2n$

$a + b = 2(m + n)$

Since $m$ and $n$ are integers, their sum $(m+n)$ is also an integer. Let $k = m+n$.

Then $a + b = 2k$, where $k$ is an integer.

By the definition of an even integer, $2k$ is an even integer.

Therefore, the sum of two even integers is an even integer.

2. Proof by Contrapositive

The contrapositive of the statement "If $P$, then $Q$" ($P \implies Q$) is the statement "If not $Q$, then not $P$" ($\neg Q \implies \neg P$). These two statements are logically equivalent, meaning if one is true, the other must also be true, and vice versa.

Sometimes, it's easier to prove the contrapositive than the original statement directly.

Example: Prove that if $n^2$ is an even integer, then $n$ is an even integer.

Proof:

Let the original statement be $P \implies Q$, where $P$ is "$n^2$ is even" and $Q$ is "$n$ is even".

The contrapositive statement is $\neg Q \implies \neg P$, which means "If $n$ is not even, then $n^2$ is not even".

In other words, "If $n$ is odd, then $n^2$ is odd".

Let's prove the contrapositive:

Assume $n$ is an odd integer.

By the definition of an odd integer, $n$ can be written in the form $2k+1$ for some integer $k$.

Now, consider $n^2$:

$n^2 = (2k+1)^2$

$n^2 = (2k)^2 + 2(2k)(1) + 1^2$

$n^2 = 4k^2 + 4k + 1$

$n^2 = 2(2k^2 + 2k) + 1$

Let $m = 2k^2 + 2k$. Since $k$ is an integer, $m$ is also an integer.

So, $n^2 = 2m + 1$.

By the definition of an odd integer, $2m+1$ is an odd integer.

Thus, if $n$ is odd, then $n^2$ is odd.

Since the contrapositive statement is true, the original statement "If $n^2$ is an even integer, then $n$ is an even integer" is also true.

3. Proof by Contradiction (Reductio ad Absurdum)

This method involves assuming that the statement you want to prove is false. Then, you show that this assumption leads to a logical contradiction (something that is impossible or contradicts a known truth). Since a false assumption led to a contradiction, the initial assumption must be wrong, meaning the original statement must be true.

Example: Prove that $\sqrt{2}$ is an irrational number.

Proof:

Assume, for the sake of contradiction, that $\sqrt{2}$ is a rational number.

By the definition of a rational number, if $\sqrt{2}$ is rational, it can be expressed as a fraction $\frac{a}{b}$, where $a$ and $b$ are integers, $b \neq 0$, and the fraction is in its simplest form (meaning $a$ and $b$ have no common factors other than 1, i.e., $\text{gcd}(a,b)=1$).

So, $\sqrt{2} = \frac{a}{b}$.

Squaring both sides:

$2 = \frac{a^2}{b^2}$

$2b^2 = a^2$

This equation implies that $a^2$ is an even number (since it's $2$ times an integer $b^2$).

From our previous example (proof by contrapositive), if $a^2$ is even, then $a$ must also be an even number.

So, we can write $a = 2k$ for some integer $k$.

Substitute $a = 2k$ back into the equation $2b^2 = a^2$:

$2b^2 = (2k)^2$

$2b^2 = 4k^2$

Divide both sides by 2:

$b^2 = 2k^2$

This equation implies that $b^2$ is an even number.

Again, if $b^2$ is even, then $b$ must also be an even number.

So, we have found that both $a$ and $b$ are even numbers.

This means that $a$ and $b$ have a common factor of 2.

However, we initially assumed that the fraction $\frac{a}{b}$ was in its simplest form, meaning $a$ and $b$ have no common factors other than 1.

The conclusion that $a$ and $b$ both have a common factor of 2 contradicts our initial assumption that $\text{gcd}(a,b)=1$.

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

Therefore, $\sqrt{2}$ must be an irrational number.

4. Proof by Mathematical Induction

This method is used to prove statements about natural numbers (positive integers). It's like setting up a chain reaction or a line of dominoes. If you can show the first domino falls, and that if any domino falls, the next one will also fall, then all dominoes will fall.

A proof by mathematical induction consists of three steps:

1. Base Case: Show that the statement is true for the initial value (usually $n=1$ or $n=0$).
2. Inductive Hypothesis: Assume that the statement is true for an arbitrary positive integer $k$ (i.e., assume $P(k)$ is true).
3. Inductive Step: Show that if the statement is true for $k$, it must also be true for $k+1$ (i.e., prove $P(k) \implies P(k+1)$). …