Problem Set 1

Due Friday, April 11 at 1:00 PM Pacific

Solutions are available!

🔑 Solutions


Here we are – the first problem set of the quarter! This problem set is designed to give you practice writing proofs on a variety of different topics. We hope that this problem set gives you a sense of what proof-based mathematics is like and helps solidify your understanding of set theory.

  • Please take note that our psets are due at 1pm on the deadline day, NOT midnight.

Before you start this problem set, please do the following:

  • IMPORTANT!!! Review the Proofwriting Checklist, which is our style guide for proofwriting in this class. We will be running this same "checklist" on your proofs when grading, so please be sure to look over it before submitting! I cannot emphasize this enough, you want to read this.
  • Review the Guide to Proofs for information about common proofwriting techniques.
  • Review the Guide to Partners for information about how to work effectively in a pair.
  • Review the Guide to Office Hours for information about how office hours work.
  • Review the Guide to $\LaTeX$ to learn how to typeset your solutions with $\LaTeX$.
  • Review the Guide to $\in$ and $\subseteq$ to make sure you understand the distinction between these terms.

As always, please feel free to call into office hours or post on EdStem if you have any questions. We're happy to help out.

Good luck, and have fun!

Starter Files

You will need to download and set up this Qt Creator project to complete the first two problems on this problem set:

📦 PS1 Starter Files

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

As a reminder, you are required to type your solutions to this problem set. If you would like to type your solutions in $\LaTeX$, you may want to download this template file where you can place your answers:

🖋 PS1 $\LaTeX$ Template

You are also free to use Microsoft Word, Google Docs, etc. to type up your solutions.

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: Set Theory

This section contains three problems (two autograded, one written / manually graded). We recommend you aim to complete these by Sunday afternoon. If you run into trouble, read through the entire Guide to Elements and Subsets and consult the Lecture 0 materials.

  • Q1: Much Ado About Nothing
  • Q2: Set Theory in C++
  • Q3: Describing the World in Set Theory

Part 2: Proof Writing and Proof Techniques

This section contains three problems (all written / manually graded). We recommend you aim to complete these by Tuesday evening. If you run into trouble, take a look back at the Guide to Proofs, the slides from our lecture on mathematical proofs, or the Proofwriting Checklist, for a refresher about how to work with universally-quantified statements and implications.

  • Q4: Writing Direct Proofs
  • Q5: Writing Proofs by Contrapositive
  • Q6: Writing Proofs by Contradiction

Part 3: Universally and Existentially Quantified Statements

This section contains two problems (both written / manually graded). We recommend you aim to complete these by Tuesday evening.

  • Q7: Proving Proving Existentially-Quantified Statements
  • Q8: Proving Mixed Universal and Existential Statements

Part 4: Putting It All Together

This section contains two problems (both written / manually graded). We recommend you aim to complete these by Friday deadline.

  • Q9: Proof Critiques
  • Q10: Sums of Cubes

Part 5: Gradescope Submission Logistics: Tagging Problems

This section has some instructions related to submission logistics. This is something you are required to do when you submit your assignment.

  • Always Tag Your Problems. Note that Gradescope marks your submit time as the time you uploaded your PDF, so you should NEVER skip tagging problems in an attempt to not go over the deadline. It won't delay your submit time, and it will greatly frustrate the graders and possibly cause you to lose points.
  • The Importance of Planning: Of course we recommend that you not be submitting so close to the deadline anyway, to avoid mishaps of all kinds (wifi going out at the worst moment, etc). You are engineers in training, so demonstrating an understanding of fault tolerance is an in-scope thing to hold you accountable for in grading. For that reason, we expect you to get your work in on time and do not routinely grant exceptions for things like "my wifi went out right when I was submitting at 12:57." You should be taking the initiative to prepare accordingly, by doing things like aiming to finish a few hours before the deadline, submitting draft versions of your work as you complete individual problems so you have a version that will at least get most of the credit even if catastrophe should strike and block submission of your final version, and so on.
  • Q11: Tag Pages and Add Your Partner

Optional Fun Problem

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

  • Optional Fun Problem: Infinite Deviation