Can You Prove the Existence of a Specific Permutation in P(X)?

[thom]

Sorry I am not used to using the tex code, but will learn and explain in words for now!

I am trying to prove that for all distinct x and y in a finite set X, there exists a function f in P(X) (the permutation group) such that f(x)=x' and f(y)=y'. Note: x' and y' are also distinct.

I have started by letting P(X) = the symmetry group and have shown that there exists a cycle (x y) which takes two distinct values and returns 2 distinct values. I am pretty sure x can equal y'. Now I am stuck! I have been told that a case-by-case analysis will probably be required. Can somebody point me in the right direction?

 

[AKG]

What are x' and y'? Do you mean to say that for all x, y, x' and y' in a finite set X, where x and y are distinct from one another, and x' and y' are distinct from one another, there exists a permutation f of X such that f(x) = x' and f(y) = y'? What do you mean "a cycle (x y) which takes two distinct values and returns 2 distinct values"? You should regard your cycle as a permutation of X, that is, it's domain is all of X, and it's range is also all of X. I can't see where you'd get stuck on this problem, but anyways, what's the first f that comes to mind? In which cases does this not work? What can you make work in these cases?

 

[thom]

Yes, your second sentence in the reply is what I meant.
Thank you for your response.

The cycle (x y) refers to a permutation which maps x to y and y to x. Here of course, f(x) = y and f(y) = x. This is the simplest bijection I can think of that holds the required conditions.
Basically I am thinking that the only bijections that don't 'work' are those that fix ANY points in the set X, the most trivial of these being the identity function. Hence, in the case of the symmetry group of the set X={1,...,n}, any n-cycle would satisfy f?
Even so, the trouble lies in extending this argument from a symmetry group to any permutation group of a nonempty finite set.

I can kind of see why you think this may seem a bit trivial, but this question is worth almost 25% of the weighting and my argument doesn't seem strong enough.

 

[thom]

Ah, no worries. I'm pretty sure I can prove this without using the symmetry group after all. I have acquired a paper on derangements which seems to suffice!

 

[matt grime]

How can you prove it 'without using the symmetry group' when it is a question about the symmetry group (but not a very hard one)? I am assuming that 'symmetry group' of a finite set is 'the permutation' group. Why on Earth would you want to use derangements, since it is trivial to find solutions fixing all but x,y,x',y' which are definitely not derangements. Indeed, If I were to ask this as a question about a 3 element set asking you to send 1 to 2 and 2 to 1 then it is impossible to do this with a derangement since 3 is necessarily fixed (and the element you require is (12)).

 

[AKG]

Yes, your second sentence in the reply is what I meant.
Thank you for your response.

The cycle (x y) refers to a permutation which maps x to y and y to x. Here of course, f(x) = y and f(y) = x. This is the simplest bijection I can think of that holds the required conditions.

I know what a I cycle is, my point was that (x y) does more than just map x to y and y to x. If z is different from both x and y, then it also maps z to z.

Basically I am thinking that the only bijections that don't 'work' are those that fix ANY points in the set X, the most trivial of these being the identity function.

You mean EVERY point? There is only one function which fixes every point. Or do you mean the only bijections that won't work are those which fix SOME point in X? No, most bijections that work fix many points in X.

Hence, in the case of the symmetry group of the set X={1,...,n}, any n-cycle would satisfy f?

No, not any n cycle would satisfy f.

Even so, the trouble lies in extending this argument from a symmetry group to any permutation group of a nonempty finite set.

Do you mean to say that you have trouble extending the argument from the group of bijection of the set {1,...,n} to an arbitary set with n elements? This is not difficult, in fact it's so trivial, one hardly ever bothers to distinguish arbitrary sets of n elements from the set {1,...,n} in this context. Of course, it can be proved, and it is very, very simple.

Okay, first suppose x, y, x', and y' are all distinct. What's the most basic function that will satisfy the desired criteria? Will this work if x, y, x' and y' are not all distinct? In particular, what if x' $\neq$ y, but y' = x (of course, we still have x $\neq$ y and x' $\neq$ y'). Why won't your previous solution work? What changes can you make to get a function that does work? Now, what other possible cases are there?