CSTBC: Theory Bridge CourseInstructor: Kevin Milans (milans@uiuc.edu) Newsgroup: news.cs.uiuc.edu/class.i2cs.theorybridge 

Photo by Bryan Clark 
(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".
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^{n1} 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.
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.
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.
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.