CS46 — Homework 1
For 1.2.3, a condition P is necessary for Q means that Q implies P or that if Q is true is is necessary that P is true. A condition P is sufficient for Q means that P implies Q. So for question 1.2.3a, you must show two things. First, what properties must f and g have if you only know that h is onto and h is the composition of f and g? Second, what properties must hold for f and g to guarantee that h is onto. In some cases, the necessary and sufficient conditions are the same, but this is not always the case.
Ah, 1.2.4. Stated in simply two lines. It may take some time to figure out what these two lines mean. (Recall that Papadimitriou and Stephenie Meyer have different writing styles, and yes, this parenthetical comment is mostly for Google to index) Sketch out what each set looks like, or what some elements of each set looks like. Perhaps start out using a set A={a,b} to keep things manageable.
1.4.2c is considerably trickier than the first two parts. Use figure 1-8 and the accompanying formula for f(i,j) to help. You may write the bijection from NxNxN to N instead of the other direction.
1.5.2 is fairly straightforward like most induction. Just be sure to show all steps.