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

Question

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:

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?

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

Thanks in advance!

Answer 1

Each decimal number $x\in\{0,1,\ldots,2^n-1\}$ can be represented as $$x = x_02^0 + x_12^1 + x_22^2 +\ldots+ x_{n-1}2^{n-1},$$ where $x_0,\ldots,x_{n-1}\in\{0,1\}$. In this way, $x$ can be represented in binary format $x_{n-1}\ldots x_0$ with most significant position at front.

Answer 2

Just as in "$\{0,1,2,3,4\}$", the commas in "$\{0,\ldots,N-1\}$" separate elements of a set. The "$\ldots$" suggests filling in all the elements between $0$ and $N-1$. This set and ellipsis notation is standard and separate from any discussion of binary or computers.

For example, if $n$ is $3$, so that $N=2^3=8$ and $N-1=7$, we have $\{0,\ldots,N-1\}=\{0,1,2,3,4,5,6,7\}$.

There are many functions $f:\{0,1,2,3,4,5,6,7\}\to\{0,1,2,3,4,5,6,7\}$. For example, one of those functions sends each of $0,2,4,6$ to $5$, and sends $1$ and $3$ to $6$, and sends $5$ to $3$, and sends $7$ to $0$.