WEEK 12 JOURNAL: COUNTABLE SETS AND UNCOUNTABLE SETS

    This week we talked about the definition of countability and how to show a set is countable. First, we need to know how to define the size of set x and the size of the set y are the same. We use |x| = |y| to represent set x and set y 's size are the same. We say that if f f is one-to-one and onto, then, |x| = |y|. Then, we can give a definition to countable. If a set A's size |A| ≤ |ℕ|, then, this set is a countable set.

    Then we can prove that the set of all possible functions is an uncountable set. To prove this, we can create a unique function fx. First, we draw a table of function halting behaviours include all possible functions, then we take the diagonal and change the T to F and F to T such that we can create a fx. Obviously, this fx is not in our list, thus, the set of all possible functions is uncountable. However, since halt functions cannot be programmed, the unique fx cannot be programmed either. Thus, there are uncountably many functions that we cannot program. 

    I think the difficult part to prove this statement is that at first we don't know how to create a function should in the list but actually not in the list. To create this function, we need to assume that this function is not in the set first, and let this function differs from all other functions in the set. By using this method, we can get this function as our counter-example and prove that the set is uncountable.