Problem Set 3

Due Friday, January 31 at 1:00 PM Pacific

Solutions are available!

🔑 Solutions


This third problem set explores functions and set theory. We've chosen these problems to help you learn how to reason about injections, surjections, bijections, and the like; how to write proofs using formal mathematical definitions; and why all this matters in practice. Before beginning this problem set, we strongly recommend doing the following:

  • Read the Guide to Proofs on Discrete Structures, which explores how to write proofs when definitions are rigorously specified in first-order logic. This handout contains both general guiding principles to follow and some sample proof templates that you’re welcome to use here.
  • Read the Discrete Structures Proofwriting Checklist, which contains some specific items to look for when proofreading your work. We will be applying the items on this checklist when grading your work, so it’s worthwhile to apply this checklist to your work before submitting.
  • Read the Guide to Proofs on Sets, which talks about how to write proofs involving sets (e.g. $\cap\text,$ $\subseteq\text,$ etc.)

We also recommend that you take a look at the proofs from this week’s lectures to get a sense of what this looks like and how to approach these problems. In particular, the two-column proof organizer and the table of how to assume/prove things will be extremely helpful here.

Good luck, and have fun!

Starter Files

Here are the starter files for the problems you'll submit electronically:

📦 PS3 Starter Files

Unpack the files somewhere convenient and open up the bundled project.

If you would like to type your solutions in $\LaTeX$, you may want to download this template file where you can place your answers:

🖋 PS3 $\LaTeX$ Template

General Advice

  • First, read through the index of problems below to get an idea of time management for this assignment.
  • Next, glance through all the questions before you start working. This not only ensures you won't be caught off guard as you reach later problems, but also gives your brain a chance to start working on some of these as a background process while you do other things.
  • If you get stuck, consider moving on to another problem for a while! Changing things up is a great way to get out of a rut, make new connections between concepts, and spark creative insights!
  • If you realize you don't have the requisite knowledge to complete a problem, take a step back from it and review the relevant lecture materials. Skipping lecture and trying to extract the relevant tidbits for each problem will lead to a more frustrating experience than engaging fully with a lecture and approaching the problem sets afterward.

Problem Index

Part 1: Warmup Problems

This section contains two problems (one autograded and one short-response question that is written / manually graded). We recommend you aim to complete Q1-Q2 by Saturday evening. If you run into trouble, read through the resources linked in the pset introduction above.

  • Q1: Properties of Functions
  • Q2: All You Need Is Love

Part 2: Function Proofs

This section contains two problems (both written / manually graded, both focusing on writing proofs about properties of functions). We recommend you aim to complete Q3-Q4 by Sunday evening. If you run into trouble, read through the resources linked in the pset introduction above.

  • Q3: Strictly Increasing Functions
  • Q4: Eventual Bijections

Part 3: Set Theory Revisited

This section contains four problems (all written / manually graded). These rely on the knowledge and understanding you honed above in Q1 through Q4, as well as information from Lecture 8 on Monday, Jan. 27, where we will use set theory as a vehicle for tying together concepts from our Week 3 lecture material. If you dive into these before Monday, we strongly recommend first reviewing the Guide to Proofs on Sets to make sure you're on the right track.

We recommend reading these all at once and then working on these and getting help by Thursday evening. We have a loose outline for that below, but recommend that you jump around and iterate on all of these instead of letting yourself get blocked by any one of them.

  • Q5: Set Theory Warmup (complete by Monday evening)
  • Q6: Sets and Power Sets (complete by Tuesday evening(ish))
  • Q7: Set-Builder Notation (complete by Wednesday evening(ish))
  • Q8: Minkowski Sums (complete by Thursday evening(ish))

Optional Fun Problem

This is an optional fun problem! Click through for more details.

  • Optional Fun Problem: Insufficient Connectives