Prelim 1 topics

Everything covered in lecture through Wednesday 9/23 is in scope; the material starting Friday is out of scope. Material covered by the homework will likely receive more emphasis in the exam.

You should expect exam problems to require similar skills to homework problems, but to be substantially easier.

Here is a (potentially non-exhaustive) list of topics:

Update: By popular demand, here are the first prelims from the last two semesters: fall 2014 and spring 2015. The depth of coverage of topics was substantially different during those semesters, so don't use these exams to calibrate your expectations!

Logic and writing

These skills apply to all of the other sections below. For example, the definition of "onto" involves a for all and a there exists, so we might ask you to prove that something is onto.

• How to prove for all and there exists statement
• How to prove implications
• How to negate (disprove) for all and there exists statements
• Writing clear definitions and proofs
• Reading definitions and checking whether an example fits a definition or not
• Proof by induction

Sets, functions, relations

Definitions:

• set, union, intersection, cartesian product (A x B), set difference, power set (2^A), set of all functions from A to B ([A → B])
• function, domain, codomain
• one to one, onto, injective, surjective, bijective
• composition, left- and right- inverse
• equivalence relation, reflexive, transitive, symmetric

Facts:

• relationships between inverses and 'jectivity

Techniques:

• prove a function is one-to-one or onto
• prove that a relation is or is not an equivalence relation

Cardinality

Definitions:

• |A| ≤ |B|, |A| ≥ |B|, |A| = |B|
• countable, uncountable

Facts:

• it's good to have a few sets that you know are countable or uncountable.
• ≤, =, and ≥ work as expected with cardinalities, for example
  • if |A| ≤ |B| and |A| ≥ |B| then |A| = |B|
  • if |A| ≤ |B| and |B| ≤ |C| then |A| ≤ |C|

Techniques:

• proving statements like those listed above
• diagonalization
• showing a set is countable

Probability

Definitions:

• probability space, event, outcome, random variable
• independence, conditional probability
• expectation, variance, standard deviation

Facts:

• Bayes's rule
• expectations of sum and product of variables
• variance of sum
• statements and ideas behind Markov's inequality, Chebychev's inequality, weak law of large numbers