Example of an Existence Proof
To prove that there exists an n ∈ N for which 11 | (2n − 1), we need to show that there exists a natural number n such that 11 is divisible by (2n - 1).
Proof:
Let's consider the number n = 6. We will demonstrate that 11 | (2n - 1) using this value of n.
Substituting n = 6 into the expression (2n - 1), we get:
2n - 1 = 2(6) - 1 = 12 - 1 = 11.
We see that (2n - 1) equals 11, which is divisible by 11 with no remainder.
Therefore, by choosing n = 6, we have shown that there exists an n ∈ N (specifically, n = 6) for which 11 | (2n - 1).
This completes the proof.
To Construct or Not to Construct
Constructive Existence Proof:
In a constructive existence proof, we provide a specific example or method to explicitly construct the object or solution that satisfies the given conditions. This type of proof not only establishes the existence of an object but also provides a way to obtain it.
Example 1:
Claim: There exists an integer x such that x2 - 5 = 0.
Constructive Proof:
To prove this claim constructively, we can find a specific value for x that satisfies the equation x2 - 5 = 0.
Let's solve the equation:
x2 - 5 = 0
x2 = 5
x = √5
Here, we have explicitly constructed the solution x = √5, which satisfies the equation x2 - 5 = 0. Therefore, we have shown the existence of an integer x that satisfies the given condition.
Non-Constructive Existence Proof:
In a non-constructive existence proof, we establish the existence of an object or solution without providing an explicit example or method to obtain it. The proof shows that the object or solution must exist based on logical reasoning or properties.
Example 2:
Claim: There exists an irrational number x such that x2 - 3x + 1 = 0.
Non-Constructive Proof:
To prove this claim non-constructively, we can use the fact that the equation x2 - 3x + 1 = 0 has irrational solutions.
We know that the quadratic formula provides solutions for any quadratic equation of the form ax2 + bx + c = 0. Applying the quadratic formula to the given equation, we obtain:
x = (3 ± √(9 - 4))/2 = (3 ± √5)/2.
Since √5 is an irrational number, we have found that the equation x2 - 3x + 1 = 0 has an irrational solution. However, we do not explicitly provide the value of x.
Therefore, by using logical reasoning and properties of the equation, we have established the existence of an irrational number x that satisfies the given condition. However, we have not provided a specific example or method to obtain the value of x.
In summary, a constructive existence proof provides an explicit example or method to construct the desired object or solution, while a non-constructive existence proof establishes the existence without providing a specific example or method.