# How do you prove the equivalence of different positional numeral systems?

It seems intuitively true that it does not matter what radix is used in mathematical operations, it is always possible to translate answers calculated in one system into structurally identical answers in another system. This is because numerals are just notation, symbols that denote abstract objects whose properties are identical.

Yet I am mentally stuck. I have trouble accepting that it is unnecessary to show that e.g. the base-2 numeral system is equivalent to the base-10 numeral system, that both systems reflect the correct algebraic and arithmetic structure of the numbers (I am aware that computers are a proof of concept).

For example, suppose that $A(n,b_1, b_2)$ is an algorithm that converts the representation of any number $n$ from base $b_1 \in \mathbb{R}$ to base $b_2 \in \mathbb{R}$. Then it appears to be true that, given any abitrary operation $\circ : X_{base_b} \times X_{base_b} \rightarrow X_{base_b}$, $$A(n_1 \circ n_2,b_1, b_2) = A(n_1,b_1, b_2) \circ A(n_2,b_1, b_2) \quad \forall n_1, n_2 \in X_{base_{b_1}}$$ and $$A(n_1 \circ n_2,b_2, b_1) = A(n_1,b_2, b_1) \circ A(n_2,b_2, b_1) \quad \forall n_1, n_2 \in X_{base_{b_2}}.$$

Why isn't it necessary to prove a property such as the one above? Why isn't it necessary to prove the existence of an algorithm which satisfies certain properties and converts between different positional systems?

Do I simply need to accept this as self-evident?

• What do you mean with "arbitary operation" ? The usual operations (addition,subtraction,multiplication,division,exponentiating $\cdots$) or also for example taking the sum of the digits of the numbers $n_1$ and $n_2$ ? – Peter Dec 20 '17 at 12:00
• @Peter I was only thinking about the usual operations you mention. I have no intuition if and how digit sums or sum of factors (perfect numbers etc.) translate between different numeral systems. – user245312 Dec 20 '17 at 13:21

Numbers vs. Representation

It is important to be clear about the distinction between a number and its representation. The two are not the same. Imagine you are in ancient Rome, using Roman numerals. You are certainly using the same numbers that we use today (e.g., seven, twelve, etc.), even though you would have no knowledge of decimal notation.

For example, the twelfth positive integer, which has the direct name "twelve", also has the Roman numeral representation XII, the binary representation 1100, the ternary representation 110, the decimal representation 12, the unary representation 111111111111, and many others. None of these representations is really the number itself. The number itself is hard to get a hold on — we can only manipulate representations of the number.

People often refer to the representation of a number as if the representation is the number. So if you hear "How many zeros are in the number one billion?", remember that this is sloppy shorthand for the more precise question "How many 'zero' digits are in the decimal representation of the number one billion?"

Mathematical Functions Operate on Numbers

Functions like addition operate on numbers. They are mappings from numbers to numbers. Seven plus twelve is nineteen. The answer does not depend on what representation a person prefers to use, or what language they use to refer to those numbers, or how they like to figure out the answers to addition problems.

Even a mathematical function like "the sum of the digits" should be thought of as "the sum of the digits in the decimal representation of the number" (or whatever representation you assumed was understood when you referred to "the digits"). This way we can see that it is a mapping from numbers to numbers, which could be communicated even to an ancient Roman or to a computer or to a person who does not think about numbers in terms of their decimal representation.

Algorithms Operate on Representations

To do operations on numbers, we need to use some representation of the number and some algorithm that operates on that representation, constructing a representation of the result.

The most common representation these days is decimal representation. We learn it in school, use it in commerce, and generally tend to forget that it is just one of many options. In school we learn algorithms for addition, subtraction, multiplication, division, and perhaps other operations, all using the decimal system of representation for the inputs and outputs of the algorithms.

With a different representation, such as Roman or unary, you would need different algorithms. The mathematical functions would be the same, but the algorithms would be very different. Two plus seven is nine in any system, but the algorithm, the way to compute it, is rather different for Roman vs. decimal vs. binary vs. unary.

Formalism

Your notation is not keeping clear the difference between numbers and their representations, or between functions and algorithms. The "$\circ$" operation appears to have a representation-independent meaning, but it is operating sometimes on representations (the outputs of the algorithm) and sometimes on numbers ($n_1, n_2$). Let's try to write these things in a more precise way.

Let $A_{b \rightarrow c}$ be an algorithm that converts a base-$b$ representation to a base-$c$ representation. Clearly its input should be a base-$b$ representation, and its output will be a base-$c$ representation. It can be defined using a formalism for expressing algorithms, such as a programming language.

We can also have an algorithm $A_{f,b}$ for finding the result of some mathematical function $f$, given the function arguments in a base-$b$ representation.

Let $r_b(n)$ be the base-$b$ representation of the number $n$.

What We Want To Prove

Now we can rewrite your equation, which is saying that a base-change can be done either before or after performing an operation, i.e., it doesn't matter what base you do the operation in:

$$A_{b \rightarrow c}(A_{f,b}(r_b(n),r_b(m))) \tag{1} = A_{f,c}(A_{b \rightarrow c}(r_b(n)),A_{b \rightarrow c}(r_b(m)))$$

To prove this, all that you really need to be sure of is that the algorithms you use are correct. (Equations (2)-(4) below.) It is indeed important that the algorithms work correctly! Once we know (or assume) they work correctly, then we can prove equation (1).

What it means for the algorithms to be correct

We can express correctness of the algorithm $A_{f,b}$ by saying that it should output the correct representation of the mathematical result: $$A_{f,b}(r_b(n),r_b(m)) = r_b(f(n,m)) \tag{2}$$ The algorithm for base $c$ is a different algorithm from the base-$b$ one; its correctness corresponds to: $$A_{f,c}(r_c(n),r_c(m)) = r_c(f(n,m)) \tag{3}$$

Also, the base-conversion algorithm should work correctly: $$A_{b \rightarrow c}(r_b(n)) = r_c(n) \tag{4}$$

We will assume that you can prove that your algorithms do give the right answer for the given representation, i.e., that you can prove equations (2)-(4). If you are using traditional algorithms, this was proved ages ago, by the people who came up with the algorithms.

Proof

Now, assuming our algorithms are correct (equations (2)-(4)), we can prove your equation (1).

We can use (2) to simplify (1), so it becomes $$A_{b \rightarrow c}(r_b(f(n,m))) \tag{5} = A_{f,c}(A_{b \rightarrow c}(r_b(n)),A_{b \rightarrow c}(r_b(m)))$$ and then we can use (4) to simplify this in several places, to get $$r_c(f(n,m)) \tag{6} = A_{f,c}(r_c(n),r_c(m))$$ which is true by equation (3).$\tag*{$\blacksquare$}$

TL;DR

In summary, you don't have to show that the base-2 numeral system is equivalent to the base-10 numeral system. All you have to show is that your base-2 algorithms give the right answer, given the definition of the base-2 representation. (And similarly for your base-10 algorithms.) If they both give the right answer, then that's why it doesn't matter which ones you use.

The numbers $n\in{\mathbb N}_{\geq0}$, together with the arithmetic operations, "exist" as individuals without any reference to a positional notation system; e.g., you can speak of $$(1+1)^{1+1+1},\quad (1+1+1+1+1+1)!,\quad{\rm etc.}$$ Given a preferred $b\geq2$ you can prove by means of the Euclidean algorithm and induction that any $n\in{\mathbb N}$ has a unique representationas a $b$-adic "decimal" $D_b(n)\in\{0,1,2,\ldots,b-1\}^*$. Furthermore the way we compute with these decimals, using carries, etc., is completely enforced by the laws of arithmetic. Therefore, if you replace base $b$ by some other base $b'$ you do not change the values of sums and products (these are "God given"). Instead you replace one "simulation" of arithmetic by another one. It is then obvious that a correct algorithm converting $D_b(n)$ to $D_{b'}(n)$ has the properties you desire.