View source for SP18:Prelim 1 guide

Prelim 1 will cover material all material covered in lecture and the homework up to and including material covered on Friday 3/2.  Material that you've had homework problems on will be stressed more heavily.  The exam will be closed book, closed notes, and will be 90 minutes long.

The first part of the course is somewhat different from past semesters; for questions on set theory and basic proof techniques, I would review homework 1.  Most of the questions in part 1 are good prelim questions.  For problems on functions and induction, see the corresponding sections of [[File:p1-sample.pdf|this list of sample questions]] ([[File:p1-sample-sol.pdf|solutions]]).  I expect the exam to be about as long as 4-6 of these questions.

Here is a brief summary of what we've covered; for an exhaustive list see the [[Main page]].


* [[:Category:Proof techniques|Proof techniques]]
** be able to write good proofs.  Know [[table of proof techniques|how to use and prove]] various kinds of [[propositions]]
** Be able to do the proofs we've done in lecture or on the homework.  ([https://courses.cs.cornell.edu/cs2800/wiki/index.php/Special:AllPages?from=&to=&namespace=3004 here is a partial list])
** Be able to write inductive proofs, including strong induction
** Understand [[diagonalization]] proofs.

* Know and be able to apply [[:Category:definition|definitions]] (both formal and informal):
** [[:Category:Set theory|Set definitions]]: [[union]], [[intersection]], [[power set]], [[cartesian product]], [[empty set]], <math>[[Set of all functions|[X \to Y]]]</math>.
** [[:Category:Functions|Functions]]: [[function]], [[partial function]], [[left inverse]], [[right inverse]], [[two-sided inverse]], [[injectivity]], [[surjectivity]], and [[bijectivity]] <math>[[\leq||A| \leq |B|]]</math>, <math>[[\geq||A| \geq |B|]]</math>, <math>[[Equality (cardinality)||A| = |B|]]</math>, [[countable]]
** [[:Category:Relations|Relations]]: [[relation]], [[reflexive]], [[symmetric]], [[transitive]], [[equivalence relation]], [[equivalence class]], [[mod|A / R]], [[well-defined|well-defined functions]] from [[mod|A/R]].
** [[:Category:Number theory|Number theory]]: [[Euclidean division algorithm]], [[quotient]], [[remainder]], [[base b representation]], [[Euclidean gcd algorithm]], <math>[[Divides|a|b]]</math>, [[equivalence mod m]], <math>[[integers mod m|\mathbb{Z}_m]]</math>, [[modular number]], arithmetic operations on modular numbers.

* Know and be able to apply basic results
** Relationship between 'jectivity and inverses
** Countability or uncountability of <math>\mathbb{Z}, \mathbb{N} \times \mathbb{N}, \mathbb{R}, 2^\mathbb{N}, [\mathbb{N} \to \{0,1\}]</math>.
** Properties of GCD algorithm, existence and uniqueness of quotient and remainder, existence of base b representation, set relationships, etc.