2
$\begingroup$

This is a question on the test review packet I have for discrete mathematics.

Given: $f = \{(a, b), (b, a), (c, b)\}$ a function from $X = \{a, b, c\}$ to $X.$

(a) Write $f \circ f$ and $f \circ f \circ f$ as sets of ordered pairs.

(b) Define $f^n = f \circ f \circ \ldots \circ f$ to be the $n$-fold composition of $f$ with itself. Write $f^9$ and $f^{623}$ as sets of ordered pairs.

For part (a), I believe: $ f(a) = b\\ f(b) = a\\ f(c) = b\\ f(f) = \{(a, a), (b, b), (c, a)\} \\ f(f(f)) = \{(a, b), (b, a), (c, b)\}$

I think there is a pattern here with even exponents being equal to $ f(f) = \{(a, a), (b, b), (c, a)\}$ and odd being equal to $f(f(f)) = \{(a, b), (b, a), (c, b)\}.$

So how do we define $f^n = f \circ f \circ \ldots \circ f$ to be the $n$-fold composition of $f$ with itself?

Also I believe, $f^9$ and $f^{623}$ would both be $\{(a, b), (b, a), (c, b)\}.$

  • 0
    Yes, I mistyped it on accident, corrected thanks. How does part b look?2012-04-01

1 Answers 1

2

Hints:

  1. From your solution, note that: $f^3 = f.$

  2. Property of composition: $f^{n} = f \circ f^{n-1} = f^{n-1} \circ f$

  3. $f^9 = f^3 \circ f^3 \circ f^3$

  4. Think about modular arithmetic. $3 \equiv 1 \pmod{\color{red}{??}}$ and $9 \equiv 1 \pmod{\color{red}{??}}.$ Figure out $\color{red}{??}$ and think about $623 \equiv\ \color{blue}{??} \pmod{\color{red}{??}}$

  5. The general form should be apparent: $f^n = f^{n\pmod{\color{red}{??}}}$

  • 0
    Yea that is easier for me. Thanks for the help. Do you mind editing your answer? (I'm going to note this and continue on with the packet before coming back and correcting it.)2012-04-01