The example I will be using (even though this example is covered in lecture, I want to go more in-depth, step-by-step):
"For every natural number n, n² odd implies that n is odd"
1. Decide whether you want to prove the statement or disprove the statement. Do this by using intuition or scribbling some cases you think will make the statement wrong. Basically look for some counter-examples.
Since I can't think of any odd numbers` that has an even root, I'm going to attempt to prove this.
2. Now you're ready to begin. Always start with the symbolic representation of the original statement of what you're trying to prove or disprove. After figuring out the symbolic representation of the statement, if you decided you want to disprove it, NEGATE the statement before proceeding with the next steps.
- What does an odd natural number mean symbolically??? We'll have to refer to the symbolic definition of what it means to be an odd number by either looking it up on the internet, or finding it in the Course Notes.
- We see that for a natural number to be odd, it means there exists a natural number where 2 multiplied by that natural number, plus one, equals to our odd number. Thus the symbolic statement would be:
∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)
- Since we want to prove this, then we don't need to negate it.
3. Now it's time to set up the structure for the proof, while leaving out the meat of it. While setting up the structure for a proof, you want to follow these guide lines:
- Start from left to right of the symbolic statement
- Whenever you have have a Universal Quantifier (∀), you want to assume there is a generic number of this set, and then proceed with the proof with everything below with one indent. After completing the structure and/or proof for all the proceeding elements after the universal quantifier, the whole statement after the universal quantifier, including the universal quantifier should be restated in conclusion form, aligned vertically with the original assumption line of this universal quantifier.
- Assume x∋Y # x is a generic to introduce ∀
- proceeding lines start here vertically (without a bullet obviously)
- # ***Lines connecting the antecedent to the consequent ***
- Then x∋Y................ # conclude for all x in Y
- For our example:
- Assume ∀n∋N # n is a generic natural number to introduce ∀
- Then conclude ∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1) # for all n in N
- Whenever you have an Existential Quantifier (∃), you want to "pick" or "let" that number equal to something that you haven't decided yet, unless the existential is a part of your antecedent for a direct proof. So you want to have either:
- pick x = _____ then x∋Y
- or let x = _____ then x∋Y
- For our example, since our existential is part of our antecedent for a direct proof, we don't pick until we get the the consequent part of our proof
- Whenever you get to an antecedent of an implication, you want to assume the antecedent is true and the lines proceeding the proof should be indented by one. The proceeding lines should be the meat of your proof where you show a connection from the antecedent to the consequent. Then, after these lines, the consequent should be stated. Then on the next line afterwards, the whole implication should be stated without the indent, thus lined back up with the antecedent vertically.
- Assume x = y # x = y is an example antecedent
- proceeding lines start here vertically (without the bullet obviously)
- then consequent
- Then x=y ⇒consequent
- For our example:
- Then ∃ k∋N, n² = 2k + 1
- Then ∃ k₀∋N, n² = 2(k₀) + 1
- Then (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)
- Keep in mind that the meatiest part of the proof, the fruit of the proof, the most meaningful part of the proof, the hardest part of the proof, are the ***Lines connecting the antecedent to the consequent ***, from the antecedent assumption. Thus you can have this structure set up while leaving space for these lines.
4. If you suspect that your antecedent implies a conjunction, you may want to have different cases set up in your proof that follow the same structure guidelines.
5. Now that you have enough information to start, setup, and structure a proof, all you need is to figure out the hard part of connecting any antecedent to the consequent. In the case of just showing if a conjunction or disjunction is true, the same structure can be followed.
- For our example:
- Then ∃ k∋N, n² = 2k + 1
- Then n² - 1 = 2k
- Then (n + 1)(n - 1) = 2k
- Then n = 2(k/(n+1)) + 1
- Then let k₀ = (k/(n+1))
- Then∃ k₀∋N, n² = 2(k₀) + 1
6. When concluding a disprove, state that the original statement is incorrect because you showed the negation to be true.
7. This is just a simple guide, there are many other things you may need to think of while proving such as should you take the contrapositive of the statement? Should you perform a direct proof? Should you perform an indirect proof? Should you prove by contradiction? Etc.
So he final product for our proof of ∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)
is:
- Assume ∀n∋N # n is a generic natural number to introduce ∀
- Then ∃ k∋N, n² = 2k + 1
- Then n² - 1 = 2k
- Then (n + 1)(n - 1) = 2k
- Then n = 2(k/(n+1)) + 1
- Then let k₀ = (k/(n+1))
- Then∃ k₀∋N, n² = 2(k₀) + 1
- Then ∃ k₀∋N, n² = 2(k₀) + 1
- Then (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)
- Then conclude ∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1) # for all n in N
So this would be a proper proof with proper structure (minus the bullet points on each line).
Hope someone finds this helpful!
