Reflection of CSC165 Lec 5 Oct. 7

Reflection of CSC165 Lec 5 Oct. 7

This week the content is less than before as the first period is used as term test. The professor introduced some different ways of proving.

5.1 Contrapositive and contradiction

5.1.1 Proof using Contrapositive

Sometimes it is hard to prove P => Q directly. However, as we have learnt before, P => Q <=> ¬Q => ¬P. By using thie property, we can say if ¬Q => ¬P is true, then P => Q is true. We may still apply the chain method as introduced in 4.2 to prove that ¬Q => ¬P is true.

A typical example is to prove  ∀n∈N, n2 is odd =>n is odd.

If we try to prove it in a direct way, that is, get rid of the square, we would probably get n = and it hard to get through. (k could be everything ∈N)

However, by proving if n is not odd => n2 is odd, we get:

n is even => n2 is even

n = 2k + 1 and n2 = 4k2 + 4k + 1 = 2(2k2 + 2) + 1

Let k be 2k2 + 2

n2 is even.

5.1.2 Proof using Contradiction

In some cases, the P in P => Q is not explicit. For example: There are infinitely many even natural numbers.

Here we see the result Q "there are infinitely many even natural numbers", but the P is abstract. In this case, we would use the way of contradiction.

Proof:

assume there are a finite number of even numbers

# assuming ¬Q

  then there exists a largest even number, m

  then let m’ = 2m

  then m’ is an even number, and larger than m

  # contradiction, since m is the largest even number

then there are infinitely many even numbers

# assuming ¬Q leads to contradiction, so Q.

The # here is important as others may not quite understand what the content is about, the comments after hashtag would help others understanding.

5.2 existential, sequence

5.2.1 direct proof of existential

  As mentioned in the beginning of the course as this figure shows

one example could verify existential

5.2.2 prove a claim about a sequence

  The proof may consist several different structures and multiple quantifiers. One example introduced in class is:

∀n∈N, an = n2

Now prove:

∃i∈N, ∀j∈N, aj <= i => j < i

The professor still use the way of contrapositive, but I think it is also okay to prove it directly.

an = aj = (j2 ≤ i) => j ≤ i

since j ∈N and j2∈N, they are either positive or zero,so j2≥j. Thus,   j ≤j2 and j2≤i, j ≤i