How to homework

From CS2800 wiki

There are a few basic steps that will help you solve any homework in 2800. These will be the first questions a TA asks you when you come to them for help; the interaction will be much more productive if you have at least tried these steps before hand.

Review the relevant definitions and theorems

In order to write a proof, you need to know the relevant definitions or theorems. I find it is most useful to first try to write down a definition from memory by thinking about the intuitive idea of the term. Then, check that you have the right definition by looking it up.

You may need to recursively write down other definitions. For example, if asked to prove that something is bijective, you must show that it is injective and surjective; this in turn may require you to show that two things are equal, or that something is a function.

Once I have the definitions in the abstract, I like to instantiate them to the problem at hand. For example, if I'm trying to show that [math]A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} C \href{/cs2800/wiki/index.php/%5Ctimes}{\times} D [/math], I might first look up the definition of :

Definition: Subset
If [math]A [/math] and [math]B [/math] are sets, then [math]A [/math] is a subset of [math]B [/math] (written [math]A \href{/cs2800/wiki/index.php/%5Csubseteq}{\subseteq} B [/math]) if every [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] is also in [math]B [/math]

but then I might instantiate it to the problem at hand by replacing variable names and using the fact that elements of [math]A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B [/math] are pairs:

[math]A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} C \href{/cs2800/wiki/index.php/%5Ctimes}{\times} D [/math] if for every [math](a,b) \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%5Ctimes}{\times} B [/math], [math]a \href{/cs2800/wiki/index.php/%E2%88%88}{∈} C [/math] and [math]b \href{/cs2800/wiki/index.php/%E2%88%88}{∈} D [/math].

Try pictures and small examples

It's good to get an intuitive understanding of what a claim says, and why it is true before diving into a proof. If asked to prove something for all [math]x [/math], choose a few small examples of [math]x [/math] and work it out in those specific cases. If asked to prove something for an arbitrary set, try it with a set containing 2 elements.

It also helps to work with general diagrams, such as a Venn diagram; these pictures can help you keep track of the variables you've defined in your general proof.

Apply the standard proof techniques

If you have a complex logical formula to prove (such as [math]f [/math] is bijective), you can always consult the table of proof techniques to get a list of steps you can take next. As you walk through those steps, update your diagram. For example, when you choose an arbitrary value, label it in your diagram, and choose a specific value in your example.

In other words, do what it says, use what you know.

Think about similar proofs or techniques from class

You can always consult the lecture notes to for recent lectures to get inspiration if you get stuck.

Finish up

Students often ask me to review whether their proof is correct. Here's the process to check for yourself. Recall that A proof is just an argument that something is true. While writing a proof, you will make a series of claims; each claim should be

  • clearly described (all terms have definitions)
  • true (based on the current set of assumptions)
  • obviously true based on what has already been stated.

To check that your proof is good, first make sure all of the terms have definitions (you don't need to write them all down, but you should be able to point to them). Then, check that each step in your proof follows from the steps before. For additional assurance, you can walk through your proof with a few small examples to double check that each statement you make is true.