Here's a question that popped up in my head recently (while solving some exercise problem regarding permutation groups):
Suppose $A$ is a finite set. Then for every $|A|>1$, there exists a bijection $f:A\to A$ such that $f(x)\ne x$ for every $x\in A$.
I tried a proof by induction on $|A|$.
Base case: Let $A=\{1,2\}$. Construct a mapping $f:A \to A$ such that $f(1)=2$ and $f(2)=1$. Clearly $f$ is bijective and $f(x)\ne x$ for every $x\in A$.
Inductive hypothesis: Let $|A|=k$ for some $k \in \mathbb{N}$. Assume that there exists a bijection $f:A\to A$ such that $f(x)\ne x$ for every $x\in A$.
Let $y$ be some element which is not in $A$. Define a new set $B:=A\cup \{y\}$. Clearly, $|B|=k+1$. Now, we will show there is a bijection $g: B\to B$ such that $g(x)\ne x$ for every $x\in B$.
Now, let's construct a mapping $g$. Pick some $a \in A$ (we can do so since $A$ is not empty). Define $g(a)=y$ and $g(y)=f(a)$. Also define $g(x)=f(x)$ for every $x\in A\setminus\{a\}$. It can now be easily shown that $g$ is bijective and $g(x)\ne x$ for every $x\in B$. $\blacksquare$
I'm suspicious about introducing an element $y$ from nowhere. Would that be right? Overall, Is my proof correct and what are some alternative ways to show this?
Your proof is correct.
A straightforward way to construct such a bijection is to put the elements of $A$ in some order - they might as well be called $1, 2, 3, \ldots, n$. Then cycle things around: let $f(k) = k+1$ when $k < n$ and $f(n) = 1$.
If you are studying permutation groups you should recognize this as the cycle $(12 \ldots n)$.