5
$\begingroup$

Let f be a function $f:\mathbb{Z} \to \mathbb{Z}$ where $|f(x)-f(y)|=|x-y|$

prove that the set of all such functions forms a group under composition.

I think this is the set of all linear functions, yes? since $f(x)=x+z$, $z\in \mathbb{Z}$, satisfies this property. It just 'shifts' this 'gap' in some direction along the number line. I assume this works:

Let $a,b \in \mathbb{Z}$ then $|f(x)-f(y)|=|a+z-(b+z)|=|a-b+(z-z)|=|a-b|$

I think this has closure since the composition $f(g(x))=f(x+z)=x+2z$ where $2z \in \mathbb{Z}$ since $(Z,+)$ is itself a group.

I am not really sure how to identify and prove the existence of the identity here since this is dealing with a set of functions. Any guidance/hints?


And as a note - If you've noticed me posting abstract alg. questions over the past day or two it is because I am doing ever problem/exercise/proof given by our prof. over the course of the last month to prepare myself for an exam! None of these are assigned for grading.

$\endgroup$
  • 1
    $\begingroup$ Functions of the form $f(x)=a-x$ also satisfy the codition. $\endgroup$ – Henning Makholm Feb 22 '15 at 16:26
  • $\begingroup$ There are other functions, like $f(x)=-x$, so that isn't enough. $\endgroup$ – Thomas Andrews Feb 22 '15 at 16:26
  • $\begingroup$ It's not because the linear functions satisfies this property that every function that satisfy this property is a linear function $\endgroup$ – Tryss Feb 22 '15 at 16:27
  • $\begingroup$ If your operation is composition of functions, then there is only one possible identity element, and that is the aptly named identity function $f_e(x) = x$. $\endgroup$ – Arthur Feb 22 '15 at 16:29
  • $\begingroup$ So consider $z=0$. Then x can be any value from the integers. Then I have covered $f(x)=x$ and $f(x)=-x$ , yes? Since $a,x \in \mathbb{z}$ then I have also covered $f(x)=a-x$. Or so I thought. If not, why not? Should I explicitly state these things? $\endgroup$ – 123 Feb 22 '15 at 16:30
5
$\begingroup$

Note that functions of the form $f(x)=a-x$ also satsify the contition.

But it seems to be a detour to want to describe exactly which functions are in the group. It's not too hard to show that it is exactly the functions of the form $a-x$ and $a+x$, but it's still a detour, and could be viewed as inelegant to have to split everything into these two cases (which multiply into four for composition) instead of working directly from the definition and avoiding the splitting completely.

If you can suppress your desire to know which functions you're talking about, it is easy to prove directly from the defining property that it $f$ and $g$ both have it, then $f\circ g$ has the same property -- and that if $f$ has the property then it is bijective, and its inverse must have the same property.

Aside proving that $f$ must be bijective: First, if $f(x)=f(y)$ then $|f(x)-f(y)|=0$ so $|x-y|=0$ which means that $x=y$. Thus we have shown that $f$ has to be injective. Now to show that $f$ is surjective, let $y$ be arbitrary and we must show that $y$ is in the range of $f$. Let $m=|f(0)-y|$. If $m=0$ then $y=f(0)$ and we're done. Otherwise each of $m$ and $-m$ must map to one of $f(0)+m$ and $f(0)-m$; since $f$ is injective they can't both map to the same one, so $f(0)+m$ and $f(0)-m$ are both in the range of $f$; one of them must be $y$ and we're done.

As always when we're talking about composition of functions, the identity element must be the identity function $f(x)=x$. (You'll need to show that it is in the group as defined, of course).

In principle you should also check that the operation is associative, but you get that for free when the operation is function composition; that is always associative no matter which functions we're speaking of.

Incidentally the group in question is known as the infinite dihedral group.

$\endgroup$
  • $\begingroup$ Henning - I am only about 4 weeks into this subject. Perhaps you might show how you would write a piece of this proof (proving the inverse, ident. etc.) and then I can use that to try and complete the proof? I follow your reasoning but sometimes proving things despite them seeming obvious is still a challenge for me. $\endgroup$ – 123 Feb 22 '15 at 16:38
  • $\begingroup$ @mathtastic: BigM has given some of it. I've amended my answer with a sketch of the difficult part, namely showing that $f$ is necessarily bijective. $\endgroup$ – Henning Makholm Feb 22 '15 at 16:52
  • $\begingroup$ Henning - I completely forgot to mention this earlier - I identified the functions because the practice question asked me to first identify these functions and then prove that the set of functions is a group under composition! I think first identifying them just blinded me. I started working with the functions I found rather than taking a more general approach like the one your outlined here. Thanks for the great answer. $\endgroup$ – 123 Feb 22 '15 at 21:12
1
$\begingroup$

Call that set with composition $G$. Note that each element of $G$ must be a bijection in order to have well-defined operation. Obviously identity function belongs to $G$.if $f,g\in G$ then $$|f\circ g(x)-f\circ g(y)|=|f(g(x))-f(g(y))|=|g(x)-g(y)|=|x-y|$$ so $f\circ g\in G$. $$|x-y|=|f\circ f^{-1}(x)-f\circ f^{-1}(y)|=| f^{-1}(x)-f^{-1}(y)|$$

$\endgroup$
  • $\begingroup$ Oh - this is great! Thanks! $\endgroup$ – 123 Feb 22 '15 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.