Bridge

CSTBC: Theory Bridge Course

Instructor: Kevin Milans (milans@uiuc.edu)

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

Photo by Bryan Clark

Lecture 2, Homework 2

Q: On page 4, it asks for proving that there exists a bijection f:A->B. Here is my example to try to prove that: 
n = 2
U = {1,2}
A = [n] X [n-1]
A = [2] X [1]
A = {1,2} X {1}
A = {(1,1) (2,1)}

Permutations of U:
1,2
2,1
(1,1) is not part of this permutation which means it is not injective, and thus, not bijective. What am I doing wrong here?
A: For the case that n=2, you have correctly identified 
	A = [2] x [1] = { (1,1), (2,1) }
	B = { 12, 21 }
It is true that the sets A and B are not the same. The key point for us though, is that they have the same size. That means that we can define a bijection f : A -> B like this: 
        S       f(S)
        -----------
        (1,1)   12
        (2,1)   21
Of course, can equally well define a bijection g : A -> B like this: 
        S       f(S)
        ------------
        (1,1)   21
        (2,1)   12
The important part is that we map each element in A to an element in B in such a way that each element in B is used exactly once. In both f and g above, each element in B = {12, 21} appears exactly once in the right column, so these functions are bijections.

We can have bijections between two unequal sets. In fact, if two sets A and B are finite, there is a bijection between them if and only if they have the same size.

Q: On page 6, it says that f(A) = A complement is a bijection. Here is my example: 
n = 5
k = 2

A = {1,2}
A = {1,3}
A = {1,4}
A = {1,5}
A = {2,3}
A = {2,4}
A = {2,5}
A = {3,4}
A = {3,5}
A = {4,5}

B = {1,2,3}
B = {1,2,4}
B = {1,2,5}
B = {1,3,4}
B = {1,3,5}
B = {1,4,5}
B = {2,3,4}
B = {2,3,5}
B = {2,4,5}
B = {3,4,5}
First problem is that A has 2 elements in it whereas B has 3 elements. Second problem is that even if I take {1,2} from A then I have got two sets in B with {1,2} in them. Please explain how is this bijection possible?
A: Perhaps one source of confusion is this: this theorem uses two different fonts. There is a cursive, fancy capital 'A' (in latex, it is written \mathcal{A}) and there is a regular, roman 'A'. The same goes for 'B'. So in the case that you mention, 
	\mathcal{A} = { {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4},
			{3,5}, {4,5} }
Similarly, we can write out the set \mathcal{B}. In order to define a bijection f : \mathcal{A} -> \mathcal{B}, what is important is that \mathcal{A} and \mathcal{B} have the same size. It does not matter if the elements in \mathcal{A} and \mathcal{B} are radically different (in our case, elements in \mathcal{A} are sets of size 2 and elements in \mathcal{B} are sets of size 3) -- it is the job of the bijection f to make the connection between the elements in \mathcal{A} and the elements in \mathcal{B}.

Relative to the universe U={1,2,3,4,5}, complementation transforms a set of size 2 into a set of size 3. So complementation is a method of starting with a set A in \mathcal{A} and obtaining a set B in \mathcal{B}.

The claim is, that if you write out \mathcal{A}, \mathcal{B}, and then write out the function table for f(A) = complement(A), you'll find that each set in \mathcal{B} appears exactly once in the right column. To get you started: 

        A       f(A)
        ------------
        {1,2}   {3,4,5}
        {1,3}   {2,4,5}
        .
        .
        .
Q: On page 13: two functions (or symbols) have been used to map a1a2.....ak and b1b2.....bn-k. Why? Why does it say permutation (symbol) with index 0 on the left of = sign?
A: To construct the bijection f, we must map an element (A, \sigma, \tau), where 
        A is a subset of {1,2,...,n} of size k,
        \sigma is a permutation of [k], and
        \tau is a permutation of [n-k].
to a permutation of [n].

So however this function is going to operate on the input (A, \sigma, \tau), we would expect it to use the permutations \sigma and \tau somehow. The overview of what happens is that the function constructs a permutation \pi_0 as an intermediate step in its computation, then it applies \sigma to the first k elements of \pi_0, and finally it applies \tau to the last n-k elements of \pi_0. The resulting permutation \pi is the output of the function.

Q: On page 15: since I don't understand page 13 correctly, I fail to understand the example also.
A: For the case that n=8 and k=3, and our input to f is the triple (A, \sigma, \tau) with 
	A = {2,4,5}
	\sigma = 213
	\tau   = 54321
our function first says to write out the intermediate step \pi_0. To do this, we sort the elements in A and then sort the elements not in A and write them in a list: 
        \pi_0 = 245 13678
Now we permute 245 according to \sigma and 13678 according to \tau. Because \sigma = 213, \sigma says that we should but the second element first, the first element second, and the third element third. So 245 becomes 425. Similarly, because \tau = 54321, \tau says we should put the fifth element first, the fourth element second, the third element stays in place, the second element goes fourth, and the first element goes last -- that is, \tau tells us to reverse the order. So 13568 becomes 86531. Putting both pieces together, the final output of the function when given the example input is the permutation \pi = 4,2,5,8,7,6,3,1.