#12 More about countable

In the last week's class, we learned more about countability and induction. We talked about the definition as countable for a set of number- basically iff it is listable (which means it can be described as a list for each item in its own position).
There is also a new concept called diagonalization. By using this concept, we can prove that the rational numbers are countable.e.g. The set of infinite number of floats in [0,1] can be put in a large list. Cantor was already proved that at least one number was missed when listing all numbers between 0 and 1, since the increment is keep decresing.
When using diagonalization proof, we add 1 to the tenth digit when digit is less than or equal to 5, minus 1 to the the tenth digit when digit is bigger than 5.And do the same thing to 100th digit and so on.After all, there will be a diagonal line in the matrix of digits.And a new number is created by this step.

#11 Halting Problem

This week we were taught about halting problem. Honestly saying I still find it is hard to tell what exactly it is. Yet there is a question about proving some function is not computable in Assignment 3. I went through the given proof in course note. Here is the question below.
Claim : the function meaning_of_life is non-computable.
Proof by reduction:

For a contradiction, assume that meaning_of_life is computable,i.e. It can be implemented as a python function. So, implement halt(f, n) using meaning_of_life(f, I),

def halt(g, i):

     def meaning_of_life(f, I):

         ...code for meaning_of_life goes here...

     def g_prime(x):

         g(i)

         return 42

return meaning_of_life(g_prime, i)

If g(i) halts, then g_prime(i) will execute the statement return 42, so meaning_of_life(g_prime, i) returns True, so halt(g, i) returns True.

If g(i) does not halt, then g_prime(i) will not execute the statement return 42(no matter what value x has), then meaning_of_life(g_prime, i) returns False, then halt(g, i) returns False.

But there is no python implementation of function halt.

Hence, there is no python implementation of function meaning_of_life.

It just use the property of halting problem(it has no result)

#10 More about Big-Omega

The statement of big-omega is shown below:
∃c ϵ ℝ+ ∃B ϵ ℕ, ∀n ϵ ℕ, n ≥B ⇒ f(n) ≥ cn2 

This is basically the same statement as the big-oh nontaion, except the less than or equal is replaced by bigger than or equal to.

So the cn^2 is the greatest lower bound of the function, it is closest to the running time under best case.

And the proof method is as same as the big-oh, which is using the proof structure.

#9 More about Big-oh

In last week's slog I was given the basic concept of big-oh, this week I got the deeper understanding anout it.

Danny taught us the concept of big-oh notations is f(n) is in O(n^2) iff

                            ∃c ϵ ℝ+ ∃B ϵ ℕ, ∀n ϵ ℕ, n ≥B ⇒ f(n) ≤ cn^2. 

f(n) can be seen as the biggest running time for the worst case of the function.This has to be less than or equal to the bound.

And the rest is same as before, using the proof structure :

Pick c = ________. Then c ϵ ℝ+ #intro- ∃

Pick B = ________. Then Bϵℕ #intro- ∃

Assume n ϵ ℕ #intro-∀

                 Assume n ≥B #antecedent

                #proof body 

                 Then n ≥B ⇒ f(n) ≥ cn2 #intro-⇒

Then ∀n ϵ ℕ, n ≥B ⇒ f(n) ≥ cn2 #intro-∀

Then ∃c ϵ ℝ+ ∃B ϵ ℕ, ∀n ϵ ℕ, n ≥B ⇒ f(n) ≥ cn2 #intro-∃

Now the basic way of solving big-oh Problem is shown.

#8 Midterm test 2 Big-Oh, Big-Omega

Finished the second midterm in this week, and I got 100%,Hureh!
Instead of proof again, new material was introduced this week, that is called big-oh.
Since I've already taken the course CSC148, this is not the first time hearing about this concept.
But I still found it hard when comes to the counting steps part.
Tracing recursive functions i.e. counting-steps is easist under worst-case, which was the mainly case we focus on. Sometimes I couldn't get straight out the counting time under n variables, so I just start from n = 1, then count at n = 2, and then using the induction to get when n is a variable.
 Danny describes the big-oh as the 'turkey size' and the function is the 'chicken size'. Cause the biggest chicken is smaller than the turkey, so big-oh is a special way to describe the upper bound of a function. In contrast, the big-omega is the way to describe the lower bound.

#7 More Proofs

After this week, the learning of proof techniques will almost comes to an end. So I think now is the proper time to sum up main techniques of proofing.

Direct proof : the most common way to carry out a proof,one conclusion followed by another one,just like chains connects together. Straight forward.

Equivalent proof: use contrapositive to prove the original statement. From the truth table, statement and its contrapositive statement hold the same status, i.e. Statement A is true iff contrapositive of A is true.

Proof of existence: useful under disproving the for all... statement or proving the exist statement. Just to find one example.

Proof by contradiction:contains assumption, disprove a statement by proving its negation is true.In personal view, this is the most effective way of proof we've learnt so far. Especially when cannot figuring out whether the statement is true or not.

Proof by cases:divide the antecedent into several parts(all are true) and proof the consequence for each condition. It take times to divide the antecedent.

Most of the times one problem can be solved in multiple ways, if I were writing the proof during exam, I would consider direct proof at first.Then proof by contradiction.

#6 Idea of Proof Sturctures

This week Danny introduced us about the proper proof structures.Danny described the logical/math problems as 'the enemy', and proof structure is the most efficient way to 'defeat' them.
We also attached delta-epsilon proofs, I was not unfamiliar with this theorem since I've seen it from my calculus classes.Yet I never thought a proof can be written as logical sentences,like
assume.....
      let......
          then......
      then exist.......
then for all..... exist......
This kind of structure helps a lot to clarify my thoughts while solving problems, not only in CSC165, but also in math classes as well. And the structure can be used for all mix quantifier problems(for all, there exist....).This means the range of its application could be really wild.
While learning how to write the proof, I didn't find writing the structure hard. It is just a tool to be used, to sort out the steps of proof, yet the real hardest part is still the 'then.....' part. It depends on the problem and usually contains math statements. Will we be given hints during the final exam?