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.


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

Thanks in advance!


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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.