Homework 1

General Comments

• Problems are taken from the textbook unless otherwise noted.
• For full credit, provide context for each problem, show all calculations, and explain your work/answers.
• Numbers and/or algebra by themselves are not enough.
• You will lose a significant amount of credit if you do not show enough work/context for your answers.
• Precision is very important. You cannot skip steps, make guesses, or use flawed logic. Any of these things can lead to incorrect answers.
• Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
• You must indicate any assistance you had on an assignment as specified on the Policies page.

Details

1. Write a formal description for each of the following sets
   1. The set containing all integers which are multiples of 3 and are larger than 17.
   2. The set containing all integers which have either 2 or 3 (or both) as a factor.
2. Let A = {1,2,3,4}, and B = {X,Y,Z}.
   1. List the elements of A×B
   2. List the elements of B×A
   3. What is |P(A×B)|?
3. Use induction to prove that 2⁰ + 2¹ + 2² + ... + 2^k = 2^k+1-1 for k > 0.
4. Prove that congruence modulo n is an equivalence relation on the set of integers. Use the following definition of congruence in your proof: a≡b mod n if and only if a-b=kn for some integer k.