This class has completed. Information on this web page may not be applicable to future semesters.

Quick links:

• Blackboard page for MATH 311-01
• Course syllabus, in PDF format, formatted for printing
• Problem Sets
  • Problem Set #1, due Friday, September 14 (solutions)
  • Problem Set #2, due Friday, October 12
  • Problem Set #3, due Friday, November 9
• Exams
  • Practice Midterm 1 (solutions)
  • Midterm 1 (solutions)
  • Practice Midterm 2 (solutions)
  • Practice Final (solutions)
  • Final Exam (solutions)

• Course information
• Daily problems

Course information:

Daily problems:

Solutions to the daily problems should be written in full sentences; while symbolic expressions can be used, they should be connected by written exposition. Solutions should be legible and grammatical, and are due at the beginning of class. You may find it useful to type your solutions, although doing so is not necessary.

• Problem Set #1, due on Friday, September 14
• Solutions to short problems
• Due August 27: Let A={1,{1,2},3,{2,5}}, and let B={3,{1,2}}. By explicitly listing out the elements, calculate |A| and |B|. Explain why it is the case that B is a subset of A. What does the fact that B⊆A tell you about the relationship between |B| and |A|, and why?
• Due August 29: Give a short explanation in words of what each of the following symbolic statements means, and why it must be true. Below, the letters A and B represent arbitrary sets — do not appeal to specific examples!
  • A∈P(A)
  • (A-B)∩B=∅
• Due August 31: Translate the following written statements to symbolic logic, and use a truth table to determine the circumstances under which each is true. Below, P, Q, and R represent named statements.
  • "P is not true, or both P and Q are true."
  • "If either P or Q is true, then Q is not true."
  • "It is not the case that if both P and Q are true, then either Q or R is true."
• Due September 5: For each of the following true implications, write out its converse and contrapositive in words (Indicate which is which when you write them). Determine whether the converse is generally true, and briefly justify your determination.
  • If A is a subset of B, then A is an element of the power set of B.
  • If n is an even number larger than 2, then n is not prime.
• Due September 7: The following statements are from a classical syllogism of Lewis Carroll. Translate each of them into symbolic logic with quantifiers, using the following names for things: let A be the set of ducks, P(x) the proposition "x belongs to Mrs. Bond", Q(x) the proposition "x is branded with a 'B'", R(x) the proposition "x is gray", and S(x) the proposition "x is wearing a lace collar".
  • All ducks branded with a 'B' belong to Mrs. Bond.
  • Ducks never wear lace collars, unless they are branded with a 'B'.
  • Mrs. Bond has no gray ducks.
  Using the symbolic logic above, what can be said about a gray duck? Justify your assertion.
• Due September 10: Perform the following steps in order to prove the statement: "The product of two odd numbers is an odd number."
  • Rephrase this assertion as an implication, giving the unknown quantities names. Identify what part of your rewritten assertion is the premise and what part is the conclusion.
  • Assume that the premise is true, and use known definitions to convert the premise to an arithmetical statement.
  • Use arithmetic to explore the statement you have derived from your premise, and use a known definition to show that the conclusion follows.
• Due September 12: Prove if a product of two integers is not even, then neither of the two factors are even. You will want to restate the above as an implication and use a contrapositive technique, but be very careful about how you negate things! (Also, note that, at this point in the course, we have not shown — and you cannot assume — that "not even" and "odd" are the same thing)
• Due September 17: Prove that if n is an integer, then either 4|n² or 4|(n²-1).
• Due September 19: Prove that if n, k, a, and b are integers such that k|n and a≡b (mod n), then a≡b (mod k).
• Due September 21: Prove formally (i.e., do not simply appeal to a Venn diagram) that for sets A and B, it is the case that A∪B=(A-B)∪(B-A)∪(A∩B).
• Due September 24: Prove that there is no smallest positive real number.
• Due September 26: Prove that for an irrational number α and a real number x, it is the case that either α+x or α-x is irrational.
• Due September 28: Disprove and suggest an improvement to this statement: if n is a natural number, then 3|(2n²+1).
• Due October 1: Let A, B, and C be sets such that A⊆B⊆C, and let us consider the possible sets S such that B∩S=A and B∪S=C. It is clear that at least one set satisfies this condition, namely, S=A∪(C-B). Prove that set is unique—i.e., there is no other set S such that B∩S=A and B∪S=C. (Hint; assume two such sets S and T exist and show that S⊆T; by symmetry you can then show that T⊆S and thus S=T).
• Due October 3: Prove that for any positive integer n, it is the case that 1(2¹)+2(2²)+3(2³)+…+n(2ⁿ)=(2n-2)2ⁿ+2.
• Due October 15: Let the sequence of values a_n be given by the recurrence relation a₁=2, a₂=5, and a_n=3a_n-1+4a_n-2 for n≥3. Using this recurrence, determine the values of a₃ and a₄ (showing your work). Then prove that a_n has the formula 0.05(7×4ⁿ-12(-1)ⁿ).
• Due October 17: Let F₁=1, F₂=1, and F_n=F_n-1+F_n-2 for all n≥3. Prove that for any positive integer n, F_n is even if and only if n is divisible by 3. (hint: make the statement being inductively proven include both parts of the "if-and-only-if" assertion).
• Due October 19: For each of the two following relations, determine if they are reflexive, symmetric, and/or transitive. Briefly give reasons for the properties you assert are true; give a counterexample for those which are false.
  • The relation of "being a proper subset (written with ⊂ or ⊊)" on the power set of the natural numbers (example usage: {1,3,4}⊊{1,2,3,4,6}).
  • The relation R on the rational numbers given by the criterion that xRy iff either x=2y, x=y, or x=y/2 (example usage: the relation 6R3 is true, since 6=2×3, while 2R7 is not true, as 7 is not equal to 4, 2, or 1).
• Due October 22: Let the relation R on the set {1,2,3,…,100} be defined by making xRy iff ⌊x/3⌋=⌊y/3⌋ (note that the "floor function" ⌊z⌋ is the value of z rounded down to the next integer; for instance, ⌊8/3⌋=2, and ⌊9/3⌋=3). Prove that R is an equivalence relation, and describe its equivalence classes.
• Due October 24: Write multiplication tables for Z₆ and Z₇. Determine which elements of Z₆ and Z₇ it makes sense to consider "dividing by".
• Due October 26: For each of the following three functions from R to R, determine, with a brief justification, whether it is injective but not surjective, surjective but not injective, neither surjective nor injective, or both surjective and injective:
  • The function f determined by the rule f(x)=2x³.
  • The function g determined by the rule g(x)=x²–3.
  • The function h determined by the rule h(x)=e^x.
  2 point bonus problem! The above three functions fit into three of the four categories given above. Find a function from R to R fitting into the fourth category (or assert that it is impossible), and justify your claim.
• Due October 29: For a finite set A, we have known since early in the course that the power set of A has 2^|A| elements. Note that the set of functions {0,1}^A also has 2^|A| elements. Describe a straightforward correspondence between the functions from A to {0,1} and the subsets of A. Does this correspondence still make sense if A is infinite?
• Due October 31: Given an injection f:A→B, explain how a surjection g:B→A could be constructed. For a∈A, is it generally true that g(f(a))=a? For b∈B, is it generally true that f(g(b))=b?
• Due November 2: We saw on the very first PotD that if A and B are finite with A⊆B, it is true that |A|≤|B|. Prove that it's true for all sets—not just the finite ones!
• Due November 5: Construct (and describe) a bijection f between the set of natural numbers N and the set of ordered pairs of natural numbers N² (hint: you can use a geometric intuition; try to associate each lattice point in the first quadrant of the coordinate plane with a different integer). Illustrate that your construction works by specifically calculating, as an example, f(15)$ and f^-1((5,4)) (i.e. find which natural number n gives f(n)=(5,4)$.). What does your construction tell you about the comparative number of elements in N and N²?
• Due November 7: Prove that for (not necessarily finite!) sets A, B, C, and D, if |A|≤|C| and |B|≤|D|, then |A×B|≤|C×D|.
• Due November 12: A "phrase" is a finite sequence consisting of any of the 26 English letters and spaces. So, for instance, "i like pie" is a phrase, as is "this    phrase has several      consecutive spaces". Prove (most easily done by describing a procedure which lists every single phrase) that the number of phrases is countably infinite.
• Due November 14: Let A be an uncountable set and B be a countable set. Prove that A–B is uncountable.
• Due November 26 (extra special 5-bonus-points PotD!): Let "1-3-4" Nim be a traditional Nim game in which there is a single pile of objects (stones or pennies or whatnot) and each player takes away 1, 3, or 4 objects on their turn. The player who removes the last object wins. Explore several small games of 1-3-4 Nim and determine which states one can win from; conjecture a general-winning-state criterion and prove it.
• Due November 28 Here let ⊕ represent the Nimsum described in class. Prove that if N=a₁⊕a₂⊕…⊕a_n, then (a₁⊕N)⊕a₂⊕…⊕a_n=0. You may use the following universally true facts without proof: a⊕b=b⊕a, (a⊕b)⊕c=a⊕(b⊕c), a⊕0=a, and a⊕a=0.
• Due November 30 We have seen that a position in traditional classic Nim is winning if and only if the nimsum is nonzero. Find and briefly explain the reasoning behind a winning condition on the nimsum for misere classic Nim (i.e. classic Nim where removing the last piece results in a loss rather than a win).