# How interpret the notation $f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\}$, $N$ is a number of the form $2^n$? [closed]

I need help how to interpret the following notation for $$f$$:

Zeroes and ones form a binary number which can be converted to decimal notation. Thus, we may think of the computer as calculating a function $$f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\},$$ where $$N$$ is a number of the form $$2^n$$, and $$n$$ is the number of bits in the computer memory. In this description, $$f$$ must be a function because the computer cannot generate two or more different outputs from the same input. We assume without loss of generality that the domain and codomain of $$f$$ are of the same size. In other words, we assume that both the input and the output of the computer have the same number of bits.

Update:

I understand the function notation \begin{align} f&:\mathbb R \rightarrow \mathbb R_+ \\ x& \mapsto f(x) \end{align} so if $$x\in \mathbb R$$ we have $$f(x)\in\mathbb R_+$$. So far so good.

However I don't follow the meaning (mapping) of $$\{0, \dots, N-1\}$$ in this case.

Attempt 1:

Say I have the decimal number $$5$$, so $$N= 5$$. I guess "of the form $$2^n$$" means a binary number, i.e. $$5_{10}=(0101)_2$$ and thus $$n=4$$. So I have the function $$f: \{0, 1, 2, 3, 4\} \rightarrow \{0, 1, 2, 3, 4\}$$

Is this correct?

Attempt 2:

Is the domain and codomain of $$f$$ a binary number? I.e. no commas in the sets $$f: \{0101\} \rightarrow \{0101\}$$

• – D.W. Apr 14 '20 at 21:17
• I’m voting to close this question because it was cross-posted. – D.W. Apr 14 '20 at 21:20

A function $$f\colon \{0,\ldots,N-1\} \to \{0,\ldots,N-1\}$$ accepts an input from $$\{0,\ldots,N-1\}$$ and outputs something from $$\{0,\ldots,N-1\}$$. Just like any function $$f\colon A \to B$$.

In this case, we are interested in $$N$$ of the form $$2^n$$. That is, we are interested in values of $$N$$ such that $$N = 2^n$$. For example, $$N = 256$$. We identify the set $$\{0,\ldots,N-1\}$$ with the set of binary strings of length $$n$$, using binary notation. For example, if $$N = 8$$, then the interpretation works as follows:

• 0 is interpreted as 000.
• 1 is interpreted as 001.
• 2 is interpreted as 010.
• 3 is interpreted as 011.
• 4 is interpreted as 100.
• 5 is interpreted as 101.
• 6 is interpreted as 110.
• 7 is interpreted as 111.

As an example, the complementation function $$f\colon \{0,\ldots,7\} \to \{0,\ldots,7\}$$ is given by $$f(x) = 7-x$$. You can check that it corresponds to complementing the binary representation of the input.