WEEK 5 JOURNAL: CONTRADICTION AND EXISTENCE

    This week we learned about how to prove a universal statement by using different methods and how to prove an existential statement.
    In week 4 we proved a universal statement directly, but sometimes we'll find that prove some statements directly is not easy. In this case, we need to try some other methods to prove those statements. First, we know that a statement's contrapositive is equivalent to this statement. Thus, when we cannot prove a statement directly, we can try to prove the statement's contrapositive.
   Another method to prove a statement is prove by contradiction. This method is similar to prove by using contrapositive. For example, the statement is A => B, to prove this by using contradiction, we can assume ¬B and if we get ¬A, then we can say that ¬B => ¬A and thus, A => B is correct.
    To prove existential, what we need to do is to find an example, so that we can say there exist an element that can make the statement to be true. However, the difficult part here is how to choose a suitable example. Sometimes the example we choose may not be a constant like x = 2, the example may be related to some other parameters (i.e. "pick x = 2y").

WEEK 3 JOURNAL: CONJUNCTION, DISJUNCTION, NEGATION AND IMPLICATION

    This week, we learned the elements of language of math. In math, we use "and" to represent conjunction relationship. The "and" in math  is different from the "and" in English. For example, in math, if I say A and B, I mean both A and B are correct. But in English, if I say x = 1 and x = 2, what I really want to say is that x is either 1 or 2. In math, if we want to say x is either 1 or 2, we need to use "or". "Or" means disjunction. In math, A or B means that there is at least one correct statement between A and B. We use "∧"  to represent conjunction and "∨" to represent disjunction.

    Then we learned how to write a negation of a statement. We can translate the statement from math language to English, and negate the statement in English, and translate our negation into math language. 

    Finally we learned how to construct a truth table. In the truth table, we have our inputs and outputs.

the inputs are some statements and whether they are T or F, and the outputs enumerates over all possible combinations of input values. The truth table can help us evaluate expressions (whether it is true of false) in a quicker way. 

    After learning this week's stuff, I find that expressing statements in math language is precise and efficient.    

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.