Week 12

A set is countable only when it can be described as a list (because a countable set can be count in a way that is 1-1 and onto). The set of rational numbers, Q, is countable because a 1-1 and onto function can be specified from N --> Q, where N is the set of natural number.

Then, a Cantor's example is showed for the uncountable sets:
"To show that the set of in nite decimals in [0; 1] was bigger
than the natural numbers, Cantor showed that any so-called list
of these numbers would always miss entries" (form slide w12)

A specification of a function is its behavior on every step.

Python functions are countable because every python function can be written in UTF-8, which is out of 256 characters. "Each string can be converted to a different number by treating each character as a digit in base 256. This gives us an onto function from N to the set of python programs".

Then, an introduction of induction is given.
First, we have an assumption for example: P(n) for all n
Then, we get the base statement: P(k) is true
Then, we prove the P(n) => P(n+1) for all n greater or equal to k
Then, we know that for all n greater or equal to k: P(n)

Week 11

This week we learned how to distinguish whether a function is computable or not.
Some functions are not computable because the solutions are infinitely long, and some other functions are not computable because they are just not.

For example,
def halts_or_not(f, I):
      "return true if the function will halt, false otherwise"

This function is not computable. Why?
Consider this function:
def test(f):
      while halts_or_not(f,f):
             pass
      return True

Then halts_or_not(test, test) only halts when it doesn't halt. By contradiction, we know the function halts_or_not is not computable.

Then, the idea of 1-1 and onto is introduced. Two infinite sets have the same size only when they can be matched up in a way that is 1-1 and onto. Here's the definition of 1-1 and onto:

 Then, when |A| <= |N|, where N is the set of natural number, we say A is countable.

Week 10 non-polynomials and big-Omega

When proving functions about non-polynomials, we prove the function using l'Hopital rule and limit as we learned last week.

Then, the definition of big-Omega is similar to the definition of big-oh except for just one character:

For big-Oh, it's a function bounded above and big-Omega is a function bounded below. So for a function in both big-oh and big-Omega, we have:

Then we also had some examples of proofs, and you can find them in slide of week 10.

Week 9

This week, we had some examples of proving a function is in O(another function).
For example, to prove a function is not in O(n square), we need to prove:

And to prove a function is not in O(n square), we need to prove the negation of the above expression.

This is the way to prove polynomial functions.

Then, we know logarithmic functions are in big-Oh of any polynomial, whereas exponential functions (with a base bigger than 1) are not in big-Oh of any polynomial.
So, to prove exponential function is not in big-Oh of n square:

Week 8 More asymptotics

As we learned last week, we are counting the steps in the worst case of a function.
For big-oh of n square:

Week 7

The first thing we learned this week is how to prove a claim false.

For example:

           Claim: all x in X, all y in Y, P(x, y) => Q(x, y)

           To prove this claim false, we can prove: {all x in X, all y in Y, P(x, y) => not Q(x, y)} or                   {exist x in X, exist y in Y, not( P(x, y) => Q(x, y))}. But we cannot prove {all x in X, all y in                Y, not(P(x, y) => Q(x, y))}.

Then we learned some allowed inference. By these inferences, we can have faster ways to prove or disprove claims.

These are some examples of inferences, and there are actually more inferences that can be found in slides of week 7.

Different sorting strategies have different efficiency, which is the speed of a function that ignores hardware, programmer virtuosity. The speed we count is in the worst case in the course CSC165.

Week 6 Different kinds of proofs

This week, we learned many different kinds of proofs. Like non-boolean proof, limit proof, and proof for a sequence and also prove by cases.

To prove or disprove a statement about sequence, we just use the skills we learned in last week. But for proving non-boolean statements, we learned some new skills. We are use the non-boolean functions and we can also break down the functions to make it more precise, and then we can only use part of the functions.

Then, we can also proof a statement by cases. If a implication can be true in several different conditions, then we need to prove each of the conditions to show the implication is true. And for some "or" statement, we also need to prove it by cases. For example, there's a general format in notes:

Week 5 Direct and Indirect Prove(as well as prove by contradiction)

In this week, we learned several ways to prove different kinds of proves.

For example, when proving existence, we just need to give one example that satisfies the statement, then the statement is proved.

There are also several ways to prove an implication, two of the ways are direct proof and indirect proof. In direct proof, we prove the implication directly ( We assumed p(x) and get q(x) by several steps, p(x) => q(x)). In indirect proof, we prove the contrapositive of the proof, which is equal to the implication (we prove not q(x) => not p(x) instead of p(x) => q(x)).

Then we can also prove an implication by use of contradiction(a special case of contrapositive). A general format is shown in notes:

A general form of a direct proof for an existential implication is also shown in notes:

Week 4 mixed quantifiers and proofs

In this week, we learned mixed quantifiers and proofs.

First we learned that the meaning of a statement may change when we change the sequence of universal quantifiers and existential quantifiers. For example, let C be a set of courses, r(x, y) means x is the prerequisite course for y, then the meaning of "all x in C, exist y in C, r(x, y)" is different from "exist y in C, all x in C, r(x, y)". The first statement means all courses in C has a prerequisite and the second statement means there exist a course y where all courses in C are its prerequisite.,

Then we learned how to make proofs, the professor said there are two main steps of an argument to convince audience something true or false:
   1. think about why you believe true/false informal reasoning.
   2. write up your reasoning in a clear(existing, funny, suspenseful) way

The proof need to follow a specific structure. In class, a structure is showed:

Week 3 Logic

In week 3, we learned logic, which is using symbols to present logical statements. The symbols include conjunction and disjunction etc.

Conjunction, which is "∧", is similar to intersection and is the expression of and in logic. Because conjunction is similar to intersection, conjunction is false if either part is false. For example, for x∈prime number, x = 3 ∧ x = 7 is true, but x = 3 ∧ x = 4 is false.

Disjunction, which is "∨", is similar to union and is the expression of or in logic. In disjuction, it's different from conjunction, disjunction is true if either part is true and is false if both parts are false.

Then, we learned negation, whose symbol is "¬". Negation is the nagated original statement. The original statement is true if its negation is false.

We also learned some standard transformations for negated expressions like  "¬ ∀x ∈ X, .... ⇔ ∃ x ∈ X, ¬....", and then we can use them to negate a statement as well as change the "¬" symbols position in a statement. 

Drawing truth and tabulating truth are two ways to check if an implication is true. We draw Venn diagrams for drawing truth and build tables for all possible outcomes for tabulating truth.

Week2 Quantifiers

In the first two weeks, I learned CSC165 is the course that help us to understand programming and math languages, which needs precision.

Then, the main thing we learned is quantifies.Quantifies are symbols including a variable that indicates the degree of generality of the expression in which the variable occurs. The symbols include Universal Claim(∀), existential claims(∃), negation(¬) etc.

The sentence comprised by the symbols is called statement. And there is also a negation for the statement. For example, if the statement states that "there is no female students in computer science specialist". Then, the negation will be "there exist at least one female student in computer science specialist", but not "there is no male student in computer science specialist." 

The statements also need to be precise. For example, the sentence " The students go to school in the morning." is not precise enough. Because "the students" doesn't show the number of students and the information for students either. "The school" doesn't show which school it is and "morning" doesn't show the exact time.

Then, the converse, contrapositive and negation of a statement is defined. Converse is the reverse of the original implication. Contrapositive is the toggled and reversed implication. Negation is the statement which false the original sentence. 

eg. the original statement is: ∀ x ∈ E, F(x) ⇒ L(x)
      the converse of it is: ∀ x ∈ E, L(x) ⇒ F(x)
      the contrapositive of it is: ∀ x ∈ E, ¬ L(x) ⇒ ¬ F(x)
      the negation of it is: ∃ x ∈ E, F(x) ⇒ ¬ L(x)