2

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)\}.$

wazy
  • 127
  • You made a mistake. $f = {(\color{red}{a}, \color{blue}{b}), (\color{red}{b}, \color{blue}{a}), (\color{red}{c}, \color{blue}{b})}$ means that $f(\color{red}{a}) = \color{blue}{b}, f(\color{red}{b}) = \color{blue}{a}, f(\color{red}{c}) = \color{blue}{b}.$ –  Apr 01 '12 at 05:30
  • But, your expressions for $f(f)$ and $f(f(f))$ are correct. –  Apr 01 '12 at 05:35
  • Yes, I mistyped it on accident, corrected thanks. How does part b look? – wazy Apr 01 '12 at 05:40

1 Answers1

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}{??}}}$

  • 3≡1 (mod 2) 9≡1 (mod 2) 623≡1 (mod 2)? I don't really understand modular arithmetic very well to be honest. – wazy Apr 01 '12 at 06:06
  • @wazy That's corrent. Alternatively, in your original post your said there are two patterns: odd and even. Do you know programming? In programming, we often use $\pmod{2}$ to test for odd/even. –  Apr 01 '12 at 06:08
  • So part b would be f^n=f^n(mod 2). I wrote f^623 and f^9 as sets of ordered pairs already and I know some MIPS programming with the HI storing the remainder or I guess the mod. – wazy Apr 01 '12 at 06:16
  • No. Because an even number mod 2 = 0. You want to say even $n \to 2$, odd $n \to 1.$ –  Apr 01 '12 at 06:22
  • If you're not comfortable with modular arithmetic. You can just write it as two cases. –  Apr 01 '12 at 06:23
  • 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.) – wazy Apr 01 '12 at 06:26