# Bijective function proof

• Apr 19th 2009, 03:27 AM
MrSplashypants1
Bijective function proof
Hey guys, just a bit lost with this proof

Let x and y be distinct numbers in the set {1, 2, . . . , n}, (n positive integer) and let  $\alpha \in$ Sn be the transposition (x y). Define
W = {  $\beta \in$ Sn | $\beta$(x) > $\beta$(y) },
Z = { $\beta \in$ Sn | $\beta$(x) < $\beta$(y) }.

Prove that W and Z are complementary subsets of Sn and that f( $\beta$) = $\beta\alpha$ defines a bijective function from W to Z.
• Apr 23rd 2009, 08:40 AM
ZeroDivisor
Hi Mr.

let a = beta(x), b=beta(y).

Then a neq b and 1\le a ,b \le n.

If a < b then beta is in Z. If a < b then beta is in W. Thus
W and Z partition S_n.

Note that beta alpha(x) = beta(y) = b
and beta alpha(y) = beta(x) = a.
Thus,
beta in W
iff
beta(x) > beta(y)
iff
a > b
iff
beta alpha(y) = a > b = beta alpha(x)
\iff
beta alpha in Z

Thus, the map f that takes beta to beta alpha sends
everything in W to Z.
Since f applied twice is the identity, it follows that f also sends
everything in Z back to W.
I.e., f is a bijection between W and Z.

Best,

ZD
• Apr 23rd 2009, 04:35 PM
MrSplashypants1
thank you very much :)