Reflection of CSC165 Lec. 12 Nov. 25th

Reflection of CSC165 Lec. 12   Nov. 25th

I forget a lot after one week's rest. Assignment 3's Q5 and Q6 really test my understanding to the content of week 10 and definitely I need to work more on it.

12.1 Countability

There are three types of countability in this course.

 1-1 means each x would correspond to each y (implies each x may correspond to more than one y and some y may not correspond to x.)

Well-defined means each x maps to a unique y.

onto means every y has some x that maps to it. (but x could correspond to more than one y or no y)

In conclusion, we can say a well-defined function is 1-1 and onto

Now, try to prove:

X =  {natural numbers}

Y =  {even natural numbers}

Intuition : X > Y as every two natural numbers generate one even number

Intuition 2: However, there are infinite X, so there will also be infinite Y and infinite = infinite

Work  with the countability:

We can find every X correspond to Y, which means they are well defined, every x has a unique y mapping to it. Thus |X| = |Y|.

Also there is a concept called "countable". In convention, any set A that satisfies |A|≤|N| is computable. 

Actually, there are countably  infinitely many python functions as all python functions could be transfer to natural number series which belongs to N. Thus it is countable