Lecture B

Winter 2014

**Instructor:** Brendon Rhoades

**Instructor's Email:** bprhoades (at) math.ucsd.edu

**Instructor's Office:** 7250 APM

**Instructor's Office Hours:** MWF 5:00-6:00pm or by appointment

**TA:** Sinan Aksoy

**TA's Email:** saksoy (at) ucsd.edu

**TA's Office:** APM 5412

**TA's Office Hours:** W 3:00-5:00 pm

**Lecture Time:** MWF 2:00-2:50 pm

**Lecture Room:** 104 PETER

**Discussion Times:** B01: W 6:00-6:50 pm, B02: W 7:00-7:50 pm

**Discussion Room:** CENTR 217A

**Final Exam Time:** 3:00-5:59pm, 3/17/2014

**Syllabus:**
Please read carefully

**Lectures:**

**1/6:** Syllabus and administrivia. Class activity. Chapter 1.
Propositions, predicates, and statements. Truth tables for the
connectives "and", "or", and "not". The negation of
"All UCSD students like Sun God."

**1/8:** Equivalence of statements using truth tables.
Chapter 2. The connective "implies". Examples. Various ways
of writing "P implies Q." The converse and the contrapositive.
The definitions of "a divides b", "b is even" and "b is odd" for
integers a and b. A proof that 101 is odd.

**1/10:** Chapter 3. The method of direct proof. The proof
that for a, b positive real numbers, (a < b) implies (a^2 < b^2)
(Axioms of Inequality). Proof by cases with a simple example.

**1/13:** Chapter 3. A more complicated example of proof by cases:
if a is a real number other than zero, then a^2 is positive. An example
of working backwards: prove that ab + ac + bc <= a^2 + b^2 + c^2 for all
real numbers a, b, c. Chapter 4. A proof by contradiction that there
do not exist integers m, n such that 6m + 8n = 33.

**1/15:** Chapter 4. A proof by
contradiction that if d > 1 is an integer, then for any integer n either
d does not divide n or d does not divide (n+1). A proof by working
backwards that for any positive distinct reals x, y, we have
(x/y) + (y/x) > 2. A proof by contradiction that if n is an integer
and n^3 - 7n is odd, then n is odd. Proof by contrapositive.

**1/17:** Chapter 5. Proof by induction. A proof that 3 divides
n^3 - n for all positive integers n. A warning that one must remember
the base case in an inductive proof. Changing the index of the base case.
A proof that m^3 <= 2^m for all integers m >= 10.

**1/22:**
Chapter 5. The "strong" principle of induction. An example: the Binet formula
for the Fibbonacci numbers.

**1/24:**
Chapter 6. Sets. Ways to construct sets. Some "common" sets.

**1/27:**
Chapter 6. Equality of sets. Union, intersection, subsets, and proper
subsets. Disjoint sets. Complements. The empty set. Using truth tables
to prove set equality.

**1/29:** Chapter 6.
More on sets, Russell's Paradox. Chapter 7.
Quantifiers ("for all, there exists").
Proving and disproving statements involving quantifiers.

**1/31:** Midterm 1.

**2/2:** Chapter 7.
Mixing and matching quantifiers. The Cartesian Product of sets.
Anonymous course feedback.

**2/5:** Chapter 8. Functional notation f: X ---> Y. Domain,
codomain, image, graph, composition, identity function I_X on X.
Functional equality. Restriction of domain.

**2/7:** Chapter 8. Associativity and non-commutativity of functional
composition. Chapter 9. Injections, surjections, and bijections. Examples.

**2/10:** Chapter 9. Inverses and invertible functions.
Theorem: A function is invertible if and only if it is bijective, in
which case its inverse is unique.

**2/12:** Chapter 9. Given a function f: X to Y, we get induced functions
(P(X) to P(Y)) and (P(Y) to P(X)). Chapter 10. Finite sets and
cardinality. Theorem: The cardinality |X| of a finite set is well defined.
Proof: Postponed. Basic counting theorems. |X x Y| = |X| |Y| and
|X \cup Y| = |X| + |Y| - |X \cap Y|.

**2/14:** Chapter 11. A proof of the fact the cardinality |X| of a finite
set X is well defined. If f: X ---> Y is an injection of finite sets,
then |X| <= |Y|. Pigeonhole Principle:
If f: X ---> Y is a function between finite sets and |X| > |Y|, then
there exist distinct x, x' in X such that f(x) = f(x').

**2/19:** Chapter 11. Examples of the Pigeonhole Principle.
Given any 5 points on a sphere, there is a closed hemisphere containing at least
4 of them. There are two people on Facebook with the same number of friends.
Any subset X of a finite set Y is finite and |X| <= |Y|.
If f: X ---> Y is a function and |X| < |Y|, then f is not a surjection.
If f: X ---> Y is a function and |X| = |Y|, then f is a surjection
iff f is an injection iff f is a bijection. Maximum and minimum elements
of sets of real numbers. Any finite set of real numbers has a maximum element.

**2/21:** Chapter 12. Counting Fun(X,Y) and Inj(X,Y) for finite
sets X and Y. Permutations of a set. The sets P_r(X). Binomial
Coefficients. Counting the power set P(X) of a finite set X.

**2/23:** Chapter 12. The binomial coefficients. The Pascal recursion.
Formula for binomial coefficients. The binomial theorem.

**2/26:** Chapter 14. Infinite sets. Denumerable sets. Countable
sets. Uncountable sets. A set is infinite iff it is equipotent to a proper
subset of itself. A Cartesian product of two denumerable sets
is denumerable. A Cartesian product of finitely many denumerable
sets is denumerable. A subset of a denumerable set is countable.

**2/28:** Midterm 2.

**3/3:** Chapter 14. The set of rational numbers is countable.
A countable union of countable sets is countable. The real interval
[0,1] is not countable: Cantor's diagonalization argument.
For any set X, there is no bijection between X and the power set P(X).

**3/5:** Chapter 15. The Division Theorem and its proof. If an integer n
is a perfect square, then n = 3k+1 or n = 3k for some integer k. If a is an
integer, then a is divisible by 3 if and only if a^2 is divisible by 3.

**3/7:** Chapter 16. The greatest common divisor gcd(a,b). Using the
Euclidean algorithm to find the gcd. gcd(a,b) is an integer linear
combination of a and b.

**3/10:** Chapter 17. gcd(a,b) is the minimum positive integer linear
combination of a and b. Chapter 22. Partitions of a set.

**3/12:** Chapter 22. Relations. The reflexive, symmetric, and transitive
properties. (Non-)examples.

**3/14:** Review.

**Homework:**

Homework 1, due 1/10/2014.

Homework 2, due 1/17/2014.

Homework 3, due 1/24/2014.

Homework 4, due 2/7/2014.

Homework 5, due 2/14/2014.

Homework 6, due 2/24/2014.

Homework 7, due 3/7/2014.

Homework 8, due 3/14/2014.

**Midterms:**

Midterm 1 and
Solutions.

Practice Midterm 2
and Solutions.

Midterm 2 and
Solutions.

Practice Final Exam and
Solutions.