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

Photo by Bryan Clark 
(1,1) is not part of this permutation which means it is not injective, and thus, not bijective. What am I doing wrong here?n = 2 U = {1,2} A = [n] X [n1] A = [2] X [1] A = {1,2} X {1} A = {(1,1) (2,1)} Permutations of U: 1,2 2,1
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) 21Of course, can equally well define a bijection g : A > B like this:
S f(S)  (1,1) 21 (2,1) 12The 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.
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?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}
\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} . . .
A is a subset of {1,2,...,n} of size k, \sigma is a permutation of [k], and \tau is a permutation of [nk].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 nk elements of \pi_0. The resulting permutation \pi is the output of the function.
A = {2,4,5} \sigma = 213 \tau = 54321our 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 13678Now 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.