21 127 Final Exam Study Guide Mary Radcli e 1 Exam Structure Your nal exam will have 10 problems though some will have multiple parts The exam will have the following structure The rst 3 questions will deal with material covered since the second exam Speci cally relations equivalence relations modular arithmetic and related issues posets The remaining 7 questions will be cumulative and may include concepts covered since the second exam You should expect questions that either ask you to directly state or explain key theorems from the semester You should expect questions that either ask you to directly de ne terms or give examples of objects illustrating key de nitions concepts You should expect some short answer questions in which you will be asked to write a brief response in words explaining a concept rather than writing a proof The di culty level of the proofs on the nal should be similar to the di culty level of midterm proofs 2 Major Topics ditional 2 De Morgan s Laws 2 1 Propositional Logic and Proof Techniques 1 Understanding propositional formulae propositional variables conjunction disjunction negation con 3 Quanti ers ordering of quanti ers negations 4 Direct Proof proving statements of the form p q by assuming p and deriving q 5 Biconditional proving statements of the form p q 6 Proof by contradiction proving statements of the form p q by assuming p and q and deriving a contradiction 7 Proof by cases proving statements of the form p q r by taking two cases p r and q r 8 Proof by contrapositive proving statements of the form p q by assuming q and deriving p 9 Law of Excluded Middle 10 Induction weak and strong 1 2 2 Set Theory and functions 1 Basic de nitions set builder notation 2 Unions intersections complements power sets Cartesian products 3 Proving equality between sets using double containment 4 De Morgan s Laws 5 Basic de nitions for functions domain codomain graph injective surjective bijective image preim age compositions left right two sided inverses 6 Well de nedness de nitions how to prove 2 Basic counting theorems Products unions intersections 4 Permutations and binomial coe cients Binomial Theorem 2 3 Counting nite 1 De nition of niteness 3 Inclusion Exclusion 5 Counting in 2 ways 6 Counting by bijection 2 4 Counting in nite 1 De nition of two sets having the same size 2 De nition of countably in nite uncountably in nite 3 Proof that the nite product of countable sets is countable 4 Proof that the countable union of countable sets is countable 5 Proof that Q is countable 6 Cantor s Diagonalization and proofs of uncountability 2 5 Equivalence Relations 1 Basic de nitions of relations equivalence relations 2 Understanding of equivalence relations via partition of ground set 2 6 Divisibility and Number Theory 1 Division Theorem 2 GCDs basic de nitions and theorems 3 Euclidean Algorithm 4 Bezout s Lemma 5 Primes basic de nitions 6 Fundamental Theorem of Arithmetic 2 2 7 Modular arithmetic 1 Basic de nitions of congruence 2 Understanding of modular equivalence as an equivalence relation and Zn 3 Arithmetic how to perform basic operations 4 Multiplicative inverses when they exist and how to nd them 5 Fermat s Little Theorem Euler s Totient Theorem 6 Chinese Remainder Theorem 2 Key terminology minimum maximum supremum aka LUB aka join in mum aka GLB aka meet 3 Understanding of Hasse diagram for representing poset structure You should be able to state explain anything on this list when referred to by name 1 Basic de nitions of poset as a relation 2 8 Posets lattice 3 Theorems with Names De Morgan s Laws for Propositions De Morgan s Laws for Quanti ers Pigeonhole Principle Principle of Weak Induction Principle of Strong Induction Fundamental Theorem of Arithmetic De Morgan s Laws for Sets Well Ordering Principle Pascal s Identity Binomial Theorem Principle of Includsion Exclusion Cantor s Diagonalization Division Theorem Euclidean Algorithm B ezout s Lemma Euler s Totient Theorem Freshman Exponentiation Theorem Fermat s Little Theorem Chinese Remainder Theorem 3 4 Terms and Notation Proposition Conjunction Disjunction Exclusive disjunction Negation Propositional formula Logical equivalence Tautology Conditional operator Biconditional operator Universal quanti er Existential quanti er Unique existential quanti er Rational number Q Irrational number R Q Limit Peano axioms and associ ated terms n cid 88 Formal ak n cid 89 ak de nitions for k m k m Set Set Builder notation x p x Empty set Subset Superset Power set P X Intersection Disjoint pairwise disjoint Union Cartesian product Universal complement X c X Y n cid 91 Formal Ak n cid 92 Ak de nitions for k m k m Lower bound Upper bound In mum in R inf S Supremum in R sup S Minimum in R min S Maximum in R max S Well ordered Function Domain Codomain Well de ned totality exis tence uniqueness Identity function X Identically equal functions Image f A Range f X Restriction f U Preimage f 1 V Composition f g Injective injection Surjective surjection Bijective bijection Left inverse Right inverse Two sided inverse ible f 1 Finite In nite Cardinality X Permutation Permutation of n Sn Binomial coe cient cid 0 n cid 1 k invert tition 4 Relative complement Pairwise disjoint nite par Countably in nite Uncountably in nite Countable Divides divisible a b Divisor factor Multiple Quotient Remainder Greatest common divisor Least common multiple lcm Coprime relatively prime gcd Relation from X to Y Relation on X Re exive relation Symmetric relation Transitive relation Antisymmetric relation Equivalence relation Equivalence class x Congruent modulo n a b mod n Integers modulo n Zn Multiplicative inverse mod ulo n Order nite order Euler s Totient function Poset Lower bound in a poset Upper bound in a poset In mum Meet in a poset Supremum Join in a poset Hasse diagram Minimum in a poset Maximum in a poset cid 62