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.