1
$\begingroup$

I'm trying to solve this but I haven't seen syntax like this before. Can someone please explain the syntax?

http://i.imgur.com/GO1Ki.png

The image is

Show that the one-to-one function $f^{-1} : N_{10} \Rightarrow N_b $ is the inverse of $f: N N_{b} \Rightarrow N_{10}$.

Hint: Show that $f^{-1} (f (n_b) ) = n_b$

I'm not sure how to format math on stackexchange either, so if someone could add what's in the png that would be great as well.

This is from a worksheet of things I should know before entering an assembly language class next semester.

Thanks!

  • 0
    Hmmm. I'm not sure how to go about showing that besides with an example, but I'm guessing it's not looking for an example. Thank you both for the explanation of what it's asking for though, which is a big help and step in the right direction.2012-12-31

2 Answers 2

1

When you define a function $f$ in higher mathematics, you first write $f:A\rightarrow B$ Here $A$ will denote the set the function is from (the domain) and $B$ will denote the section the function is going to (the codomain).

After this, you (generally) give a formula expressing how the function is defined. For example we could write "$f:\mathbb{N}\rightarrow\mathbb{N}$ defined by $f(n)=n+1$."

In the image you've attached, you've got a function called $f^{-1}$ which goes from whatever $N_b$ is (probably the natural numbers in base $b$) to $N_{10}$ (probably the natural numbers in base $10$). I would imagine that they have given you a definition for $f$ in a previous problem, or in the preceding chapter, or something.

It seems like there is a mistake in the problem - an extra $N$ before $N_b$ in the definition of $f$.

The problem should be very easy. If $f$ is one-to-one, then there is a unique element of $N_{10}$ associated with each element of $N_{b}$ in the image of $f$. (Which is probably all of $N_b$, as if not $f^{-1}$ is not well defined.)

0

To prove this statement, let's clarify what it means for $f_{a \rightarrow b}: \mathbb{N_{a} } \rightarrow \mathbb{N_{b}}$ (arbitrary integer bases). If $n_a = \overline {a_k a_{k-1} \ldots a_0}_a$ and $0 \leq a_m < a$ (i.e. in base a expansion, $n_a = a_k a^ k + a_{k-1} a^{k-1} + \ldots + a_0$), then $f(n_a) = \overline{b_j b_{j-1} \ldots b_0}_b$, where $a_k a^ k + a_{k-1} a^{k-1} + \ldots + a_0 = b_j b^j + b_{j-1} b^{j-1} + \ldots + b_0 b^0$ and $0\leq b_m < b$

Now, the map $f^{-1} _{a \rightarrow b} f_{a\rightarrow b}(n_a)$ would yield $\overline{c_i c_{i-1} \ldots c_0}_a$, where $b_j b^j + b_{j-1} b^{j-1} + \ldots + b_0 b^0 = c_k a^ k + c_{k-1} a^{k-1} + \ldots + c_0 $ and $0 \leq c_m < a$. To prove the function is actually an inverse, it remains to show that $a_m = c_m$, which is left to you.

  • 0
    @AlexanderGruber I was basing that assumption off of OP's response to my comment in the original problem. Of course, as in your solution, $f$ could have been some weird funky function defined in the paragraph before his image.2012-12-31