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.

WEEK 11 JOURNAL: HALTING PROBLEMS

    This week, we talked about how to write a halt function, how to define a computable function, what is reduction and what is a countable set.
    First, we proved that we cannot write a halt(f, n) works for all functions f. To prove this, we can say that let the function test itself. Case 1 is that if the halt function does not halt, we can return a number, but if the function returns a number, it actually halts. Thus, we get a contradiction. Case 2 is that if the halt function halts, this function will continue run the while loop, this is an infinite loop and the function won't halt. Thus, we also get a contradiction for case 2. Therefore, we cannot write halt(f, n).
    A computable function is a function that f(x) is for every x in some certain domain and we know how to compute f(x) for every x in domain. Otherwise, f(x) is non-computable. For example, the halt function is a non-computable function.
     We say that f reduces to g if we find that f can be implemented by extending another function g. We can use reduction to show whether a function is computable or not, because a computable function reduces to a computable function.
     We use |A| to represent the size of  set A and if  |A| ≤ |ℕ|, we say that set A is countable. 

WEEK 10 JOURNAL: BIG-OMEGA, GENERAL PROPERTIES

    This week we continue talking about the big-oh problem. This time, we learned how to prove some general statements about big-oh. For example, we want to prove that for all f, g, h belong to F, (f∈O(g) and g∈O(h) ) => f∈O(h). In this question, we first know that if f∈O(g), and g∈O(h), then f <= c1g and g <= c2g. We want to show that f∈O(h), thus we need to choose a suitable c. We can easily know that when c >= c1*c2, f is always smaller than or equal to h. Therefore, we can pick b the biggest between b1 and b2 then pick c as c=c1*c2, then this statement is proved.
    Another statement is that ∀ f, g ∈ F, f ∈O(g) =>g∈Ω(f). Since f ∈O(g), we know that n>=B => f<= cg. Since g∈Ω(f), we know that n>= B' => g>=c'f. Because f<= cg, g>=f/c, thus, we can pick c' = 1/c and let B' = B. Then this statement can be proved.
    There is a tricky question: ∀ f, g ∈ F, f ∈O(g) =>f∈O(g*g). This statement is false, because g*g is not always bigger than g (i.e. let g = 1/(n+1)^2).
    In conclusion, to prove these statements, we need to find the relationship between the c we want to show and the c we have already known, and we also need to use the upper bound and the lower bound to bound the function.

WEEK 9 JOURNAL: BIG-OH OF POLYNOMIALS

    This week we talked about how to prove 7n^6 - 5n^4 + 2n^3 ∈ O(6n^8 - 4n^5 + n^2). To solve this problem, we first need to find the relationship between these two functions. We find that 6n^8 - 4n^5 + n^2 >= 6n^8 - 4n^5 >= 6n^8 - 4n^8 = 2n^8 since n is a nature number. Then, we can also find that 7n^6 + 2n^6 = 9n^6 >= 7n^6 + 2n^3 >= 7n^6 + 2n^3 - 5n^4. Therefore, our task now is to make some connections between 9n^6 and 2n^8. We need to make the constant the same and the number to the power of n to be different so that we can judge which one is bigger. Therefore, we choose our c = 9/2, and c * 2n^8 = 9n^8 >= 9n^6. Therefore, (6n^8 - 4n^5 + n^2) is always bigger than or equals to (7n^6 - 5n^4 + 2n^3) when c = 9/2. The hard point in this problem is that we need to pick a c that can connect both functions together.
 
    I remember that the test question 2 is a little bit similar to this question. In question 2, we need to find a "d" to make the negation of the statement to be true. Since "∃ d", this d must be unique and cannot be a universal number. The principle we judge whether a number is unique or not is that whether this number we choose can connect the antecedent and the consequent together. How to choose a unique number is quite hard sometimes, and we need to keep on practising.

WEEK 8 JOURNAL: BIG O PROBLEMS

    This week, we we talked about the formal definition of O and Ω, and we learned how to prove a function is in O. The definition for O is that ∃c∈ℝ+,∃b∈ℕ,∀n∈ℕ,n≥b => f(n) ≤ cg(n). This definition means that after a break point "b", f is always smaller than g. Conversely, Ω means that after the break point "b", f is always bigger than Ω. Therefore the definition of Ω is that ∃c∈ℝ+,∃b∈ℕ,∀n∈ℕ,n≥b => f(n) ≥ cg(n).
    To prove a function is in O, we need to find a suitable c such that f(n) ≤ cg(n). For example, in class we talked about how to prove the worst case complexity of insertion sort is in O(n^2). To solve this question, we can pick n = 10 then Wis = (3/2)n^2 + (9/2)n - 4 ≤ 10n^2. Next, we pick a b ≤ 10. Therefore, we proved that Wis is in O.