11
11
Office Hours: Wednesday 3-5pm in Skye 281.
Week 1 (Jan 7) - Notes: What are sets? Union, intersection, subset, proper subset, disjoint definitions.
Week 2 (Jan 14) - Worksheet on set operations and how to count cardinality of power sets.
If A is a set with n elements. Then to count the cardinality of power sets we may ask how can we construct any subset? To do so imagine that each element has the choice to be in the subset or not. By doing this for every element we have constructed all possible combinations of subsets. Therefore to count the number of elements in the power set is precisely 2^n.
Week 3 (Jan 21) - Worksheet on induction.
In general, when a questions asks that something holds for all natural numbers, then induction is a great first step to take.
How to write proofs with induction? Begin with the base case, which means we can consider when n = 1 (some problems might have say n = 0). Inductive step, assume the statement you are proving holds for some arbitrary number n. In our introductory problems for induction, most statements are some equality or inequality. Pick one of the sides and try to use the n-th step assumption to show the other side. Be careful not to write the (n+1)-th equality down as the first line, as this implies that you are already assuming the statement to be true.
Week 4 (Jan 28) - Worksheet on relations
Week 5 (Feb 11) - Midterm Review: To summarize I break down the class into five categories
Please note there is typo in the midterm review. Where it states P(A) = 2^|A| should really be written as |P(A)|=2^|A|. To clarify the confusion, P(A) is the set of all subsets of A and |P(A)| is the number of elements in the set P(A).
Basics of sets
Induction
Relations
Equivalence relations
Functions
Week 6 (Feb 18) - Worksheet on sets, functions, cardinality.
Injective, surjective functions
Key idea for cardinality is using the fact that unions of countable sets are countable
Week 7 (Feb 25) - Worksheet on logic
Logical operators
Logical equivalence
Quantifiers
Writing sentences with quantifiers
Week 8 (Mar 4) - Worksheet on logic part 2, which is similar to week before.
Week 9 (Mar 11) - Final review: To summarize I attempt to group the material of the course into categories.
Basics of sets
Induction
Relations
Equivalence relations
Functions
Cardinality
Algorithms and complexity
Logic
Counting
Week 10 - Finals week