Week 12

This week was the last week of this course; therefore we covered last thing that was covered in this course.
This week's topics:

1. Explanation of the reason why rational numbers are countable/listable
2. Cantor's example
3. Diagonization
4. Induction

First of all, the term countable is same as the meaning of listable, which then we call this correspondence ( 1 - 1 and onto in one case). 

Next, rational numbers are countable, meaning there is a correspondance. As it is shown below:

For first row in the picture, we listed both positive and negative numbers of the same integer, once we did that then we incremented the integer by one, then repeated the process. For the rest of the rows, as you can see, they are fractions then we incremented the numerators by one the same way we did in the first row. 

As we went down the columns, we incremented individual denominator by one. 

As the result, we assumed that all the numbers listed, then this was the proof of rational numbers were countable. (there were no overlapping combinations of value from set X and value from set Y). 

Following, Cantor's example proved that all real numbers were non - countable. This example basically showed us that the reason why all real numbers were non-countable was simply because the different sizes of infinite. In Cantor's example, we tried mapping all real numbers to natural numbers, which we all knew both sets of numbers were infinite; however, there were always numbers that were greater than the size of the set (amount of numbers) that we assumed at the first place. Therefore, it was impossible for us to prove all real numbers were countable because infinite didn't equal to infinite (in this case; infinite could occasionally equal to infinite, but it varied on different cases) This concept was tricky and it really made struggled a little bit. I am glad I have figured it out eventually.

Moreover, we were also introduced to the idea that there were total of 256 characters in UTF-8 (python was written in UTF-8), all characters could be translated in to different numbers or combinations of numbers. By saying that, it meant each python function was unique and these python functions were countable.

Next, we were given an example of halt and loop behaviours as it was shown in the picture below:

In this case, we interpreted halts as the number 0 and loops as the number 1. The output of the behaviour of different inputting functions was either halts or loops (only two options). As we tried to list all the possible outputs, we realized it was impossible for us to do so because this halt and loop example was non-countable because there were more infinite behaviours than python functions. 

Last but not least, we learned the last new topic in this course, which it was induction. 

We started with the principle of induction as it was shown in the picture below.

We supposed P(n) as a predicate/boolean function of the natural numbers. 

If P started out true, such as P(0) and the truth of P transfers from each number to the next, which this could be written down in one expression. . This showed us that P was true for all natural numbers. However,  could be false. 

In the four tables below, we found one table that violated the expression. The third table (counting from left) violated the expression because when n = 1 and P(n) was true; therefore,  when n = 2 and P(n) should be true. Next, many of us believed that the fourth one violated the expression too; however, in fact this table was true. During the lecture, I thought this was false because I believed when n = 1 and P(n) = false then when n =2 and P(n) should be false (they should be consistent). 

Basically, the reason why fourth table was true was because we could choose a number (variable: k in this case) and used it as a restriction of the inout numbers. The expression that made the fourth table true :. Therefore, we believed P is true for all natural numbers when n was greater or equaled to k. 

Next, we did some induction examples, which we came up with the following steps to solve general induction problems. 

Step 1: Write base case(s) & prove they are true 

Step 2: Assume P(n) is true (Inductive Hypothesis)

Step 3: Show that P(n+1) is true, then transform one side of the equation so that you can use the Inductive Hypothesis to solve the problem.