Math 215 Introduction to Advanced Mathematics

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

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