12th Week - Nov 25th

This is week 12, which is the officially last lecture for csc165. In this week, we have learned countability, and a detailed review guide was talked during class.Speaking to countability, comparing the sizes of two sets was taught first. Thinking of comparing the size of two sets, there are actually three types of functions to analysis: well-defined function, 1-1 function, and ‘onto’ function. A well defined function a function that each x in function maps to a unique y; 1-1 function is each y mapped to by at most one x; while, ‘onto’ function is that every y has some x, which maps to it. One typical example I want to talk is to compare the sizes of X={natural numbers} and Y={even natural numbers}. At the time when I first saw this problem, I thought Y was obviously smaller than X, simply because Y was the set of even natural numbers which meant that Y was a subset of X. I know a lot of people would come to the same answer as I do, however, unfortunately, it is wrong. Actually, the two above have the same sizes, because they are both infinite, and even though you match the numbers of in each sets, they can be well defined.
Another specific question I want to talk about is the first question in this week’s tutorial: Prove “∀f: N->R>=0, ∀g: N->R>=0, g ϵ Ω(f) => g^2 Ω (f^2)”. Personally I think this is a typical prove example because all you need to do is to follow the structures have been taught so far. Therefore, the first step is to assume the domain which is written like “ Assume f: N->R>=0, ∀g: N->R>=0”. Then, antecedent needed to be written down which is “assume g ϵΩ(f)”. By doing the draft sketch, we know that if we want to say “ g>= C1*f ó g2 >=C1^2*f^2 ó g2>=C2*g2”, we have to assume C2=C1^2, and B2 =B1, which is the key idea for proving the problem. And the rest of the proof is nothing too much except the regular proving steps.

       Literally, this is all I want to say about this week’s lecture and tutorial. Good luck to my peers and me to the final CSC165 final exam.