CSTBC: Theory Bridge Course

Instructor: Kevin Milans (milans@uiuc.edu)

Newsgroup: news.cs.uiuc.edu/class.i2cs.theory-bridge

Photo by Bryan Clark

Lecture 1, Homework 1

Q: I don't know what {0,1}^n means in set notation.
A: The notation {0,1}^n means we take the Cartesian Product of {0,1} with itself n times. Specifically, {0,1}^n is the set of all bit strings (b_1, b_2, ..., b_n) of length n. For example, {0,1}^2 = { 00, 01, 10, 11 }. The Cartesian Product of two sets is defined with an example in Lecutre 1, on page 9.1. The notation A^n, where A is a set (in our case, A={0,1}) is defined on page 9.2, right before the section "Functions".
Q: Hints on HW1, problems 3-5?
A: 3. This question asks for us to define a function f from the set of all subsets of {1,2,...,n} which have size k to the set of all ordered lists (a_1,a_2,...,a_k) of length k whose elements are in {1,2,...,n}. (Take a look at the notes from lecture 1, pages 9.5 and 9.6, for an example of a bijection between the set of all subsets of {1,2,...,n} and the set of all ordered bitstrings (b_1,b_2,...,b_n) of length n.) If you have a good understanding of the two sets involved and a good understanding of the concept of an injection, I hope you'll find this a relatively easy problem. 4. Again, much of the difficulty of this problem is in understanding what the problem is asking for. Reviewing Lecture 1, pages 10 and 11 introduces the concept of a pairwise intersecting family of sets. A pairwise disjoint family is similar. Part (2) is asking for you to give n+1 subsets of {1,2,...,n} which are pairwise disjoint -- that is, for every pair of subsets A,B that you pick, it should be the case that A and B do not share any common elements. For example, a pairwise disjoint family cannot include both {1,2,7} and {2,3,4} because both of these sets have a common element: 2. 5. Review Lecture 1, pages 10 and 11. In particular, make sure you understand each and every word of the proof on page 11. Then, have another look at the example at the bottom of page 11. Do you see how the proof applies to the specific case n=3 ? Every pairwise intersecting family of size 2^{n-1} must include exactly one set from each complementary pair. How can you make these choices so as to ensure that property (3) holds? This is perhaps the most difficult problem on HW1.
Q: In the solutions to HW1.2(4), it should be surjective but it says neither.
A: In order for this function f to be surjective, then something in A would have to map to the element 2 in B. So for f to be surjective, there would have to be an integer n such that n*n = 2. Because there is no such integer n, f is not surjective.
Q: In the solutions to HW1.4(1), how can |B| be greater than |A|-1 as shown at line 2 of the solution where it says |B| greater or equal |A|-1?
A: Good question... the reason why we write that |B| is greater than or equal to |A| - 1 is to take care of the case that the emptyset was not in our original set A. In that case, setting B = A - {emptyset} is the same as setting B = A, so in this case, B and A would have the same size. It is exactly this kind of critical, careful attention to the details of a proof which we want to establish in this course.
Q: Regarding HW1.2(6): I got the question right because I pictured that for a set A = {a, b} that P(A) = { {}, {a}, {b}, {a, b} } and f(A) = { {a, b}, {b}, {a}, {} } which made it bijective. Was that the correct visualization? In this case, B does appear to equal A.
A: I apologize again for using 'A' to represent an input to the function f; I think your question above might be a result of that mistake. Do you still have this question with the updated hw1? If U = {1,2}, then A = B = { {}, {1}, {2}, {1,2} } and the function f : A -> B is given by this table: S f(S) ------------ {} {1,2} {1} {2} {2} {1} {1,2} {} Because every set in B appears in the right column of this table, f is surjective. Because every set in B appears at most once in the right column of this table, f is injective. Because f is both injective and surjective, f is bijective.
Q: Regarding HW1.2(7): If A = {1, 2} and thus P(A) = { {}, {1}, {2}, {1, 2} } it appears that f(A) = { {1}, {1, 2} }. However in this case, B != A. Is that why this is neither? It seems it is surjective in this example. If not, why is this neither injective nor surjective?
A: Yes, I think you have the idea. Just to be clear -- If U = {1,2} and A = B = { {}, {1}, {2}, {1,2} }, then our function f : A -> B in part 7 is given by this table: S f(S) ------------ {} {1} {1} {1} {2} {1,2} {1,2} {1,2} Because there are some sets in B (e.g. {}) which do not appear at all in the right column, f is not surjective. Because there are some sets in B (e.g. {1}) which appear more than once in the right column, f is not injective.
Q: Regarding HW1.2(8): If A = {1, 2} and thus P(A) = { o, {1}, {2}, {1, 2} } it appears that f(A) = { {1}, {}, {1, 2}, {2} }. In this case, B = A and it appears bijective. Is this the correct interpretation? I am checking the reasoning not just the answer here.
A: Yes, I think you've got it figured out. Again, just to be very clear -- Similarly to parts 6 and 7, we set U = {1,2} and A = B = { {}, {1}, {2}, {1,2} }. In part 8, our function f : A -> B is given by this table: S f(S) ------------ {} {1} {1} {} {2} {1,2} {1,2} {2} Because every element in B appears exactly once in the right column, f is bijective.