Math 215 Introduction to Advanced Mathematics
Key Concepts
Chapter 1--The Language of Mathematics
- mathematical statements, propositions, predicates
- building compound statements using AND, OR, and NOT.
- truth tables--using truth tables to prove that statements are
equivalent
- negating statements: not (P and Q) is equivalent to (not P or not Q);
not(P or Q) is equivalent to (not Q or not P)
Chapter 2--Implication
- implications, universal implications
- negating an implication: not (P=>Q) is equivalent to (P and not Q)
- reading phrases like "P is necessary for Q", "P whenever Q"... as
implications
- converses
- contrapositives
- if and only if statements
Chapter 3--Proofs
- direct proofs
- proof by cases
- proof by proving contrapositive
- proving results for the reals using the
axioms for ordered fields
See the Methods of Proof handout
Chapter 4--Proof by Contradiction
- contradictions
- proof by contradiction
- proving P=>Q by contradiction
- proving P=>(Q or R) by contradiction
- the square root of 2 is irrational
- there are infinitely many prime numbers
Chapter 5--The Induction Principle
- proof by induction
- changing the base case
- definition by induction
- strong induction
Chapter 6--The Language of Set Theory
- sets
- equality of sets: proving two sets are equal
- subsets: proving one set is a subset of another
- the empty set
- union, intersection and difference of sets
- Venn diagrams
- power sets
- complements
Chapter 7--Quantifiers
- Existential and universal quantifier
- finding negations of statements with quantifiers
- proving universal and existential statements
- understanding and proving statements with several quantifiers
- Cartesian products
- Convergence of sequences
Chapter 8--Functionss
- Informal definition of function
- domains, codomains and images
- restriction and composition
- graphs of functions and the formal definition of functions
Chapter 9--Injections, Surjections and Bijections
- injections, surjections and bijections
- inverses
- f:X -> Y has an inverse if and only if f is a bijection
- the image and preimage functions.
Chapter 10--Counting
- cardinalities of finite sets
- the addition and multiplication priniciples
- the inclusion-exclusion principle
- counting the number of functions f:X->Y for X, Y finite (Chapter 12.1)
- counting the number of subsets of a finite set X (Chapter 12.1)
Chapter 11--Properties of Finite Sets
- If X and Y are finite and f:X -> Y is an injection, then |X| <= |Y|
- Pigeonhole Principle
- If Y is finite and f:X -> Y is an injection, then X is finite
- If X is finite and f:X -> Y is a surjection, then Y is finite
and |Y|<= |X|
- If X is finite and Y is a subset of X, then Y is finite (and on
homework we showed that if Y is a proper subset then |Y|<|X|)
Chapter 12--Counting Functions and Subsets
- Counting F(X,Y)
- Counting P(X)
- Counting I(X,Y)
- Counting P_r(X), evaluating binomial coefficients
Chapter 14--Counting Infinite Sets
- equipotent sets, |X|=|Y| and |X|<=|Y| for arbirtary sets
- denumerable and countable sets
- Z is denumerable
- N x N is denumerable
- Q is denumerable
- the sujective image of a countable set is countable
- the product of countable sets is countable
- the union of countable sets is countable
- R is uncountable
- Cantor's Theorem: |X|<|P(X)|
- Cantor-Schroder-Bernstien Theorem (without proof)
Chapter 22--Partitions and Equivalence Relations
- partitions
- equivalence relations
- If f:X ->Y is a surjection then x~y if and only if f(x)=f(y)
is an equivalence relation and there is a bijection between X/~ and Y
Last Updated 11/20/06