Math 109 Sections A and B (Winter 2025)

March 25: Course grades have been assigned and uploaded to eGrades. Check Canvas for Final scores, graded Finals, and other information.

If you are enrolled in Section A (09:00am) then your final exam is on March 19 from 8:00am to 11:00am at Peterson Hall 102.
If you are enrolled in Section B (10:00am), then your final exam is on March 21 from 8:00am to 11:00am at Peterson Hall 102.

March 14

March 12: We solved a few practice problems involving counting principles. See Canvas lecture notes.

March 10: Given any function f: X----> Y, we saw how to define the image f(A) of a subset A of X, and the ``pre-image" f^{-1}(B) of a subset B of Y. Using this, and some elementary observations, we arrived at the Generalized Pigeonhole principle which states that given a function f: X ---> Y and m > 1 with |X| >= (m-1)|Y| + 1, there exists an element y in Y such that |f^{-1}({y})| >= m. We saw a few applications of this problem as well.

March 7: We recalled the definition of ``convergence" for a sequence {a_n} and proved rigorously that the sequence a_n = 2 for all n and b_n = 1/n for all n converges to 2 and 0 respectively. We then defined a relation on a set X and defined an equivalence relation and saw several examples.

March 5: We spent some time reviewing problems involving induction and strong induction. Please refer to the notes uploaded on Canvas.

March 3: I provided an overview of Chapter 14. In particular, we used the notation |X| <= |Y| to mean that there is an injection from |X| to |Y|; |X| = |Y| to mean there is a bijection from X to Y; and |X| < |Y| to mean that there is an injection X ---> Y but no bijection X ---> Y. We proved |X| < |P(X)| using a self referential type argument. We stated the Schröder--Bernstein theorem, that if |X| <= |Y| and |Y| <= |X|, then |Y| = |X|. We also stated the continuum hypothesis that there is no cardinalities between |Z| and |P(Z)| = |R|.

February 28: The main result we proved was that the set of rational numbers is enumerable after first proving some preliminary results. I stated another theorem: given a set X, there are no surjective functions X ---> 2^X. 

February 26: We proved the identity {n choose r} = {n - 1 choose r - 1} + {n - 1 choose r} using the formula for {n choose r} [boring!] and via a combinatorial interpretation of both sides. We then saw the binomial theorem which generalizes the identity (a+b)^2 = a^2 + 2ab + b^2. I defined the notion of "equipotence" for two sets. We saw that N and Z are equipotent; (0,1) and (0, 2) are equipotent; but N and (0, 1) are *not* equipotent via Cantor's diagonalization argument.

February 24: Midterm 2.

February 21: Midterm 2 review.

February 19: We defined "n choose r" as the cardinality of the set of subsets of {1. 2. ..., n} of size r. We saw some identities involving this number and specifically saw that "n choose r" = "n choose n-r".

February 14: The sub from last time continued with more applications of the pigeonhole principle. We also defined the minimal and maximal elements of a set of numbers and saw they always exist when the set is finite. We moved on to counting special functions from X to Y. For example, the number of injective functions is (|Y|)(|Y|-1)...(|Y|-|X|+1). 

February 12: We had another sub today who used the inclusion-exclusion principle to solve many interesting counting problems. After that we saw the pigeonhole principle, which in essence, is that a function f: X ---> Y with |X| > |Y| cannot be injective and did some examples.

February 10: We had sub today who defined a sequence as a function f: N ---> R and what it means for a sequence to “converge” to a real number a. We also precisely saw what the “cardinality”: a set X has cardinality n if there is a bijection from the set N_n := {1,2,…, n} to X (if no such bijection exists for all n, then X has cardinality infinity). We need to make sure there is no ambiguity, i.e., there is a bijection between {1, 2, …, n} and {1, 2, …, m} if and only if n = m (we did not rigorously prove this in class). We then made whatever we talked about on February 7 precise and saw the inclusion-exclusion principle:
|X U Y| = |X| + |Y| - |X intersection Y|
and generalizations.

February 7: We defined the notion of invertibility for a function and saw that a function f : X ---> Y is invertible if and only if f is both injective and surjective (i.e., f is bijective). We also saw how these notions allow you to measure the size of the set: given a function f: X ---> Y, if f is injective, then |X| <= |Y|, if f is surjective, then |X| >= |Y|, and if f is bijective/invertible, then |X| = |Y|.

February 5: We counted the number of functions f : X ---> Y where X has m elements and Y has p elements (and saw there are p^m distinct functions). We discussed how function composition is not commutative, i.e., fg is not the same function as gf when they are both defined. Finally, we defined injectivity and surjectivity and saw many examples.

February 3: Looked at several examples/non-examples of a function after defining it. Then discussed the many parts of  f : X ---> Y; f is the name of the function, X is the domain, Y is the codomain, and also defined the range/image of f. Finally introduced the composition fg of two functions f : X ---> Y and g : Z ---> X which is a function from Z to Y.
Optional Reading: (6) Tim Gowers' blogpost summarizing basic logic.

January 31: We discussed how to negate statements involving quantifiers, especially statements involving two quantifiers. We paid special attention to the difference between the two statements "for all a, there exists b, P(a, b)" and "there exists b, for all a, P(a,b)".
Optional Reading: (5) Tim Gowers' blogpost on "Negations". 

January 29: Midterm 1.

January 27: Midterm 1 review.

January 24: We defined the difference A - B of two sets, and the power set P(A) of a set A, and did many examples. We also started talking about quantifiers and saw what it means for the statements "for all a in A, P(a)" and "there exists a in A, P(a)" to be TRUE.
Optional Reading: (4) Tim Gowers' blogpost on "Quantifiers".

January 22: We saw how to check equality of two sets and defined the terms subset, proper subset, union of two sets, intersection of two sets, complement of a set, paying special attention to why union is like OR, intersection is like AND, and complement is like NOT.

January 17: Explained how to prove statements using strong induction, and specifically proved that the n-th Fibonacci number is less than 2^n. Introduced sets and how to define sets in various ways.

January 15: We finished Q2.1 and spent some time discussing why (n^2 - n - 2 = 0 => n=2) OR (n^2 - n - 2 = 0 => n= -1) is FALSE. This led us to the realization that quantifiers are important [which will be introduced soon]. We continued with induction and saw how to define sums recursively and simplify them.

January 13: We proved De Morgan's Laws: NOT (P OR Q) = (NOT P) AND (NOT Q); and NOT (P AND Q) = (NOT P) OR (NOT Q). We did most of Q2.1 from the textbook.

January 10: We showed that the equation "a^2 + b^2 + 2 = 1 + 2ab" has no real solutions via a proof by contradiction. We defined the contrapositive and saw that to show P => Q, it is equivalent to show that NOT Q => NOT P. We finally talked about the principle of mathematical induction and did a few examples. 

Homework 1 is now posted.
Note that first week survey had a minor mistake -- the first midterm is on JANUARY 29; the second midterm is on FEBRUARY 24.

January 8: The statement "P implies Q" being TRUE means that you can deduce Q by assuming P is TRUE. So it is FALSE only if P is TRUE and Q is FALSE. Started talking about proofs and discussed "direct proofs" and "proof by contradiction". Please fill the first week survey by January 11, 2025.
Optional Reading: (3) Tim Gowers' blogpost on "IMPLIES".

January 6: We discussed mathematical statements, propositions, predicates, free variables. We then introduced logical connectives and looked at "AND", "OR", and "NOT" in detail, and introduced "IMPLIES".
Optional Reading: (1) Tim Gowers' blogpost on "AND" and "OR"; (2) Tim Gowers' blogpost on "NOT".

Here are some resources from other UCSD instructors that you may find useful:
1) Prof. Rayan Saab's notes from Math 109, Spring 2017: Basic Logic; Methods of Proof; Set theory; Functions; Counting; More counting;
2) Dr. John Eggers' lists: Tautologies; Terminology;
3) Prof. Sasha Knop's amazing videos: Logic; Proofs;