CS103 notes PDF

Preview

Summary

Notes I took as a student in Keith Schwarz's class at Stanford University, CS103: Mathematical Foundations of Computing....

Description

Lecture 1: 4/3/17 - Key questions in cs103 - What problems can you solve with a computer? (computability theory) - Why are some problems harder to solve than others? (complexity theory) - How can we be certain in our answers to these questions? (discrete mathematics) Introduction to Set Theory!! - A set is an unordered collections of distinct objects, which may be anything (including other sets) - {a,b,c,d} and {c,d,a,b} are the same set - {a,b} and {a,a,a,b,b,b} are the same set - { } is called the empty set, contains no elements, can also be represented as ∅ - 1 ≠ {1} (number is not equal to set containing that number - ∅ ≠ {∅} (first is empty set, second is set with one element that is an empty set) - Anything is never equal to the set containing that thing (x ≠ {x}) - Membership - “a is an element of the set {a,b,c,d}” represented as: a ∈ {a,b,c,d} - “e is not an element of the set {a,b,c,d}” represented as: e ∉ {a,b,c,d} - If x ∈ S, we say “x is an element of S” - Everything either is or is not an element of a set, there’s no middle ground of kinda being an element of a set - Infinite sets - Some sets contain infinitely many numbers - Natural numbers (integers 0,1,2,etc.) represented by N with two diagonal lines - Integers represented by Z with two diagonal lines - Real numbers is R with two vertical lines - To describe complex sets like “all even natural numbers” say “the set of all n where n is a natural number and n is even” which we represent by { n | n ∈ N and n is even} - This notation is called set-builder notation - Takes form of { x | some property x satisfies } - | means “where” or “such that” - Comparing sets - Use venn diagrams yay!! - To combine sets take the union of the two “∪” - A = {1,2,3}, B = {3,4,5}, A ∪ B = {1,2,3,4,5} - To find common elements, take intersection “∩” - A = {1,2,3}, B = {3,4,5}, A ∩ B = {3} - To find difference between two sets use “-” - A = {1,2,3}, B = {3,4,5}, A - B = {1,2} (alternative notation uses “\” instead) - B \ A = {4,5} - Symmetric difference is everything that appears in one but not both, uses “∆”

-

-

- A = {1,2,3}, B = {3,4,5}, A ∆ B = {1,2,4,5} Subsets - A set S is called a subset of a set T (S ⊆ T) if all elements of S are also elements of T - Are there any sets S where ∅ ⊆ S? - We say that this is always true for every set S (by vacuous truth) - Vacuous truth: a statement of the form “All objects of type P are also of type Q” is vacuously true if if there are no elements of type P (no counter examples) - If S = {a,b}, there are 4 sets that are subsets of S: ∅, {a}, {b}, {a,b} - The power set of S, ℘(S), is the set of all subsets - ℘(S) = {∅, {a}, {b}, {a,b}} - ℘(∅) = {∅} (power set of empty set is a set containing the empty set Cardinality - Cardinality of a set is the number of elements that it contains - Denote cardinality with absolute value signs (magnitude/size) - |{a,b,c,d,e}| = 5 - |{{a,b},{c,d,e}}| = 2 - |{a,b,c,c,c,c}| = 3 - For cardinality of (most) infinite sets we don’t say it is infinite, we say it’s “aleph-zero” (ℵ0) - By definition: Two sets have the same cardinality if there is a way to pair their elements off without leaving any elements uncovered - Now you may think that the cardinality of natural numbers shouldn’t be the same as of all integers, but there is a way  to pair them off such that nothing is uncovered because the sets are infinite! So both have cardinality of ℵ0 - Exception to infinite sets having same cardinality: if S is infinite, then its power set has to be bigger because for every new element you look at through infinity you generate more elements in the power set - Cantor theorem: write elements down left side and top and as you go across for each thing you’ve paired it with, indicate whether or not you included the element in that row that’s the top of this column - Take the diagonal and flip which ones you use and it is impossible to ever have included this set in a pair - Therefore, you haven’t paired this one off so the cardinalities are not equal - Diagonalization Proof: no matter how we pair up elements of S and subsets of S, the complemented diagonal won’t appear in the table (in row n, the nth element will be wrong) - Earth-shattering, destroys the concept of infinity - Not all infinite sets have the same size - There is no biggest infinity - There are infinitely many infinities

-

If we accept that the number of possible programs is at most as big as the number of strings (each program can be represented with the string of the source code) and that the number of possible problems we can solve is at most as big as the set of all strings (problems formed from sets of strings ∈ all problems) - We eventually get that |Programs| < |Problems| so there are problems we can’t solve OOOOOH

Lecture 2: 4/5/17 - A proof is an argument about why something is right/true - A mathematical proof is an argument about why a mathematical statement is true - An integer n is defined as even if there is an integer k for which n = 2k - An integer n is odd if there is an integer k such that n = 2k + 1 - Every integer is either even or odd and no integer can be both - We can use these to prove principles about even/odd numbers - First direct proof: - Theorem: if n is an even integer, then n2 is even - Proof: let n be an even integer - Since n is even, there’s an integer k s/t n = 2k - This means that n2 = (2k)2 = 4k2 = 2(2k2 ) - There is clearly a number m (in this case 2k2 ) where n2 = 2m - Therefore, n2 is even ■ (black square for end of proof?) QED - General form of proofs: If P, then Q...assume P is true, then show Q must also be true - Proofs typically use definitions to back up claims - Assign names to variables to represent quantities and refer back to them - Transitive property of subsets (theorem): if A ⊆ B and B ⊆ C, then A ⊆ C - Prove this by arbitrary choices: to prove something holds for all possible x, show that no matter what you choose the property is true - Start proof by making arbitrary choice of x (“Let x be chosen arbitrarily”, etc) - Proof: Let A, B, and C be arbitrary sets where A ⊆ B and B ⊆ C - Consider any x where x ∈ A. Since A ⊆ B and x ∈ A, we see that x ∈ B as well. Then since B ⊆ C and x ∈ B then x ∈ C as well. - Thus for every x, if x ∈ A, then x ∈ C - Therefore, A ⊆ C.■ - Hint for doing this: first observe that if A ⊆ C, what we need to prove that if x ∈ A, then x ∈ C, then work from there with definition of what it means to be a subset - Say now we want to extend this to 4 sets, we can call back on the OG transitivity theorem and use that to prove this ish - How not to write proofs: - If you say make an arbitrary choice, don’t actually pick values-leave unspecified - Don’t flip the direction and prove the opposite of what you say (if you have “if P then Q”, assume P and prove Q, don’t assume Q and prove P

-

-

-

Universal statements - for all x, some property holds for x (must be true for all) Existential statements - there is some x where some property holds for x (must be true for any one, easiest to prove by just finding an example) Biconditional statements - always involve the phrase “if and only if” - P if and only if Q means that if P then Q and if Q then P - Usually means you have to prove both implications separately - Set equality is biconditional: for two sets A and B, we say A = B if this is true: for any object x , x ∈ A if and only if x ∈ B - This is the axiom of extensionality!! - New (easier) way to write this: if A ⊆ B and B ⊆ A then A = B - Proof: let A and B be arbitrary sets where A ⊆ B and B ⊆ A. We will prove that A = B by proving that, for any arbitrary x, that x ∈ A if and only if x ∈ B. - First, we’ll prove that if x ∈ A, then x ∈ B. Take any x ∈ A. Since A ⊆ B and x ∈ A, we see that x ∈ B, as required. - Then do same proof for other way around - Proven both directions of implication, so we see that A = B ■ Say we prove some union/intersection junk equals some other union/intersection junk - Do this by proving each is a subset of the other - Decompose!! Do the two proofs separately (small ones called lemmata, small one called a lemma) In order to do proofs with union/intersection/difference/etc. We need formal definitions of these operations to refer back to - If x is in S union T that means x is either in S or T (or both) - If x is in S intersect T that means x is in S and T - For unions, do proof by cases (proof by exhaustion) where you consider all possible cases (Case 1: x belongs to S, Case 2: x belongs to T...