# Cyclic group of permutations. f_n(x) = x + n

Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• Oct 20th 2012, 02:36 PM
pirateboy
Cyclic group of permutations. f_n(x) = x + n
Problem Statement:
For each integer $\displaystyle n$, define $\displaystyle f_n$ by $\displaystyle f_n(x) = x + n$
Let $\displaystyle G = \{f_n: n\in\mathbb{Z}\}$
Prove that $\displaystyle G$ is cyclic. (Indicate a generator of $\displaystyle G$).

Attempt at a solution (brainstorming of where to begin):

I know that all subsets of $\displaystyle \mathbb{Z}$ can be generated by 1 under modulo addition (except, zero, right?). Also, I believe it is true that the $\displaystyle \mathbb{Z}_n$ can be generated by $\displaystyle n-1$ under modulo additon (I think I read that on the internet somewhere, so it must be true).

My inclanation is to go the modulo addition route. However, I'm getting hung up on the $\displaystyle x$. If $\displaystyle x$ is some arbitrary element, then $\displaystyle x$ could very well be irrational, correct? In which case, does modulo addition even work with non-integers? When considering $\displaystyle G$, do I take $\displaystyle x$ to be a fixed element?

Is this one one those cases where I'm going to have to make some assumptions about $\displaystyle x$ in my proof? For example say something like "Suppose $\displaystyle x\in\mathbb{Z}$..."

Or maybe I don't even need to go the modulo addition route at all? Should I be working a different angle?

Any hints on where to start on this, would be awesome!

Thanks!
• Oct 20th 2012, 03:07 PM
Plato
Re: Cyclic group of permutations. f_n(x) = x + n
Quote:

Originally Posted by pirateboy
Problem Statement:
For each integer $\displaystyle n$, define $\displaystyle f_n$ by $\displaystyle f_n(x) = x + n$
Let $\displaystyle G = \{f_n: n\in\mathbb{Z}\}$
Prove that $\displaystyle G$ is cyclic. (Indicate a generator of $\displaystyle G$).

My goodness, you left out a great deal of information.
What is the domain of each function $\displaystyle f_n~?$

You told us about the set part of the group: $\displaystyle G = \{f_n: n\in\mathbb{Z}\}$
BUT NOT anything about the operation defined on that set.
What is the operation?

Have you even shown that this pair does forms a group?
• Oct 20th 2012, 03:26 PM
ILikeSerena
Re: Cyclic group of permutations. f_n(x) = x + n
I believe it does not matter what the domain of fn is.

What is its operation?
What do you get if you combine 2 of its elements? For instance f1 and f1?
• Oct 20th 2012, 03:34 PM
Plato
Re: Cyclic group of permutations. f_n(x) = x + n
Quote:

Originally Posted by ILikeSerena
I believe it does not matter what the domain of fn is.

On the contrary. Surely we are meant to assume that the domain each function has the same domain. But if that is not the case, then the group operation becomes problematic. So domain should be stated.
• Oct 20th 2012, 03:40 PM
ILikeSerena
Re: Cyclic group of permutations. f_n(x) = x + n
Quote:

Originally Posted by Plato
On the contrary. Surely we are meant to assume that the domain each function has the same domain. But if that is not the case, then the group operation becomes problematic. So domain should be stated.

The problem statement implies that G is a group (it would have been nice if that was explicit).
Therefore the operation is meaningful.
Therefore each fn has the same domain, which could be anything, as long as its domain supports addition with an integer, after which we have to get the same set.

Either way, these details are not really relevant for the problem at hand.
We can just assume everything is in order and work from there.
• Oct 20th 2012, 03:47 PM
pirateboy
Re: Cyclic group of permutations. f_n(x) = x + n
Ah! Sorry! I gave as much information as the book gave! If your curious, the question comes from Charles C. Pinter's "A Book of Abstract Algebra". ...more like "A Book of Abstract Problem Statements"
Anyways, some of the other questions of the section are:

For each integer $\displaystyle n$, define $\displaystyle f_n$ by $\displaystyle f_n(x) = x + n$.

* Prove: For each integer $\displaystyle n, f_n$ is a permutation of $\displaystyle \mathbb{R}$, that is $\displaystyle f_n \in S_{\mathbb{R}}$

* Let $\displaystyle G = \{f_n : n\in \mathbb{Z}\}$ Prove that $\displaystyle G$ is a subgroup of $\displaystyle S_{\mathbb{R}}$

Soo...from context, I'd assume that the domain is $\displaystyle \mathbb{R}$.
• Oct 20th 2012, 03:54 PM
ILikeSerena
Re: Cyclic group of permutations. f_n(x) = x + n
Quote:

Originally Posted by pirateboy
Soo...from context, I'd assume that the domain is $\displaystyle \mathbb{R}$.

That seems to be a reasonable assumption. ;)

Actually, to be really proper, the introduction of the book or chapter should state that all functions should be assumed to have domain $\displaystyle \mathbb{R}$.

So... any answer to our questions?
• Oct 20th 2012, 04:15 PM
pirateboy
Re: Cyclic group of permutations. f_n(x) = x + n
Hmm, well if i combine $\displaystyle f_1$ and $\displaystyle f_1$ I'd get $\displaystyle (x + 1) * (x + 1)$ where $\displaystyle *$ is some arbitrary operation.

Now I can think of a few operations that would make $\displaystyle G$ a group. Addition is one, the identity being 0. In which case, -x would also have to be in the group if x is not an integer.

Multipication would be another one, right? G then have to contain $\displaystyle (x+n)^{-1}, x+n \neq 0$.

But neither of these are cyclic, are they? I don't know that I'm answering the questions.

If the operation were multiplication, $\displaystyle f_1 * f_1$ would give $\displaystyle x^2 + 2x + 1$ ...well, I'd have to assume G was abelian for that, though, right?
• Oct 20th 2012, 04:17 PM
ILikeSerena
Re: Cyclic group of permutations. f_n(x) = x + n
What is f1(f1(x))?
• Oct 20th 2012, 04:17 PM
pirateboy
Re: Cyclic group of permutations. f_n(x) = x + n
oh, wait, do you mean $\displaystyle f_1 \circ f_1$? That'd be $\displaystyle f_1(f_1) = f_1(x+1) = x + 1 + 1$
• Oct 20th 2012, 04:18 PM
ILikeSerena
Re: Cyclic group of permutations. f_n(x) = x + n
Sounds good!

So...
• Oct 20th 2012, 04:24 PM
Plato
Re: Cyclic group of permutations. f_n(x) = x + n
Quote:

Originally Posted by pirateboy
Ah! Sorry! I gave as much information as the book gave! If your curious, the question comes from Charles C. Pinter's "A Book of Abstract Algebra". ...more like "A Book of Abstract Problem Statements"
Anyways, some of the other questions of the section are:
For each integer $\displaystyle n$, define $\displaystyle f_n$ by $\displaystyle f_n(x) = x + n$.
* Prove: For each integer $\displaystyle n, f_n$ is a permutation of $\displaystyle \mathbb{R}$, that is $\displaystyle f_n \in S_{\mathbb{R}}$
* Let $\displaystyle G = \{f_n : n\in \mathbb{Z}\}$ Prove that $\displaystyle G$ is a subgroup of $\displaystyle S_{\mathbb{R}}$
Soo...from context, I'd assume that the domain is $\displaystyle \mathbb{R}$.

Thank you for answering. I knew Pinter through his work in set theory and logic.
I did not know that he did an algebra text. Frankly, I do not find those examples useful. I hope that someone here has a copy of that textbook.

If I were to guess, I would say that "$\displaystyle f_n$ is a permutation of $\displaystyle \mathbb{R}$" means to shift "x to x+n".
So the operation is function composition.
Thus $\displaystyle f_m*f_n=f_{m+n}$ [That is a guess]
What is the identity of this group?
Then what is $\displaystyle \left(f_n\right)^{-1}~?$.

Can you guess a generator?
• Oct 20th 2012, 04:28 PM
pirateboy
Re: Cyclic group of permutations. f_n(x) = x + n
Then consider the inverses?

$\displaystyle f_n \circ f_{-n} = f_n(x - n) = x - n + n = x$
so
$\displaystyle f_n \circ f_{-n} = e(x)$ (e is the identity).

Also $\displaystyle f_n \circ f_{-n}$ associative and abelian, since the operation is addition.

Is that it, then? G is cyclic and f_n is the generator?
• Oct 20th 2012, 04:30 PM
ILikeSerena
Re: Cyclic group of permutations. f_n(x) = x + n
I suspect you intended fn and fm to be associative and abelian instead of fn and f-n?
Then yes. Those first parts sound correct!

But... suppose f_n is the generator.
Which elements can you generate then?

Btw, if I start nitpicking, you should really say something like:
$\displaystyle \forall x \in \mathbb R: (f_n \circ f_m)(x) = ... = x + n + m = f_{n+m}(x)$
Therefore $\displaystyle f_n \circ f_m = f_{n+m}$

Note that you either compose functions without their argument, or you should mention the argument consistently.
• Oct 20th 2012, 04:33 PM
pirateboy
Re: Cyclic group of permutations. f_n(x) = x + n
Side note: the book is actually quite inexpensive. \$11 new on amazon (paperback).
Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last