Sets

An assignment in CS 303. Some problems are from MCS

Assignment

1. Prove an identity.
   1. Give a proof that the subseteq operator makes a partial order. Namely, prove that the subseteq operator is reflexive, antisymmetric, and transitive. When you need to use names for sets, use A, B, C in the proof. PROOF.
   2. Give a proof that set intersection is associative. When you need to use names for sets, use A, B, C in the proof. PROOF.
2. Basic questions about sets / basic reasoning / using the identities and rules for sets.
   1. MCS Problem 15.4. What is the answer, you should come up with a formula, and explain why.
   2. MCS Problem 15.5. Make sure to only use set notation in part a. In part b, give a formula, also work it out, and explain.
   3. MCS Problem 15.9. Again, give formulas, explain why, work them out. ** most interesting problem.
   4. MCS Problem 15.13. Again, give formulas, explain why, work them out. There are a variety of ways to do this. You might read through the following (and pages it links to): https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
   5. MCS Problem 15.30. ** tied for most interesting. PROOF. For the definition of multinomial coefficients, see https://en.wikipedia.org/wiki/Multinomial_theorem#Multinomial_coefficients
   6. MCS Problem 15.35. What is the answer for each, and explain why.

General comments based on everyone's initial submissions...

• You don't get to decide what sets are in these proofs. You need to give an argument that works for any sets, not just showing it works for some particular examples. So you start with something like, "let A and B be any sets"...
• You need to explain what is going on - use sentences, make sure each thing follows from the previous.
• Proof that intersection is associative: You need to show that given any sets A, B, and C, (A n B) n C = A n (B n C).
• In real life, you need to be able to know if you have the right answer or not. I want this for the assignments as well - if you aren't sure about what you have, you should say so; if you think you are right up to a certain point, you should say so.
• If you turn in handwritten work, I have to be able to read it. Since math needs to be very precise, I need to be able to read every single letter.
• The sets could be anything, not just numbers.
• Use the notation correctly. For example, if you are asked for the size of a set, and are dealing with sets X and Y, then |X| |Y| makes sense as a potential answer, but X x Y (X cross product Y) does not because X x Y is a set and is not a number. Similarly, if you mean to give the answer of 10 choose 5, write it properly and not as a fraction and not as 5 choose 10.