# What's the name for a bijection where pairs of elements map to each other?

First, a bit of context. About a quarter of an hour ago I came across one of those "Internet math puzzles" on Facebook that stated:

If 1 = 5, 2 = 10, 3 = 15, and 4 = 20, then 5 = ?

The answer was supposed to be 1, as we had already stated. But of course, assuming the rule is x = 5x, then 5 is equal to both 1 and 25, as well as 125, 625, 3125, etc.

This got me thinking, can we define a relation like the one the question asks for so that 5 isn't mapped to 25, but x is still mapped to 5x in general? What I got was the following:

$x = \left\{ \begin{matrix} 5x & \text{the prime factorization of } x \text{ has an even power of 5} \\ x/5 & \text{the prime factorization of } x \text{ has an odd power of 5} \end{matrix} \right.$

I'm pretty sure this is a bijection. But if it is, I don't know if there's a special name for bijections like this, that map pairs of values to each other.

Basically, what's the name for the type of bijection $f: D \to D$, such that for any $a, b \in D$, if $f(a) = b$, then $f(b) = a$, and $a \neq b$?

-
This comment doesn't address your question directly but you may be intersted in the Garsia-Milne involution principle if you don't already know about it - particularly the discussion in Wilf's "Lectures on integer partitions" –  alancalvitti Dec 27 '12 at 21:02

Such a bijection is called an involution. It is a bijection $f$ such that $f(f(x))=x$.

Note that the premise $f(f(x))$ is only true for a bijection - that is, if $f$ is any function such that $f(f(x))=x$ then $f$ is naturally a bijections, since its left- and right-inverse is itself.

I don't think there is a name for an involution that has no fixed points - that is, where $f(x)\neq x$ for all $x$, so that you always get a pair.

You might want to call it a "free involution." In involution can be seen as a group action of $\mathbb Z_2$ on a set $X$. A "free" group action is one with no stabilizers - that is, for each $x\in X$, $\{g:gx=x\}=\{1\}$.

-
I had a hunch that it might have been an involution; I looked it up, but it wasn't exactly what I was looking for. It seems like "fixed-point-free involution" is the closest we have so far. –  Joe Z. Dec 27 '12 at 19:56
The basic non-fixed involution is in boolean algebra, where we send a set $A$ to it's complement $A^c$. –  Thomas Andrews Dec 27 '12 at 20:04
So the "complement" operator is the same as the "conjugate" operator in that case? –  Joe Z. Dec 27 '12 at 20:05
Yeah, maybe I misremembered "complement" as "conjugate." Never mind. Edited my comment above to remove that wrongness. :) –  Thomas Andrews Dec 27 '12 at 20:08
You might want to call it a "free involution." An involution can be seen as a group action of $\mathbb Z_2$ on a set $X$. A "free" group action is one with no stabilizers - that is, for each $x\in X$, $\{g:gx=x\}=\{1\}$. –  Thomas Andrews Dec 27 '12 at 20:13

A map such that $f(f(a))=a$ for every $a$ is sometimes called an involution, and an involution certainly has the property that whenever $f(a)=b$, $f(b)=a$.

I am not requiring $f$ to be a bijection, but it turns out to be one anyway, since it is its own inverse function.

Involutions are well-studied in ring theory, where rings with involutions pop up naturally, especially in operator algebras. One such involution is given by the transposition map on a full ring of square matrices. Another good example is the complex conjugate mapping in the ring of complex numbers.

Update: as for your addition to the question of having no fixed points, I haven't heard a special name used for them. As you can see from the two examples I listed, it's quite common and unalarming for an involution to have fixed points. What is interesting is that the involution is the identity map when restricted to the fixed points.

-
By definition, the restriction of any map to fixed points is the identity: $f(x)=x$, so not just involutions, but also idempotents (where the fixed point set is often called normal form) etc. –  alancalvitti Dec 27 '12 at 21:00
@alancalvitti Yes, that's a good comment. I did not mean to make it look like this was a special property of involutions. –  rschwieb Dec 27 '12 at 21:09