Base Representation

Suppose that

m, k \in ℕ_{1}

and

(a_{k}, a_{k - 1}, \dots, a_{1}) \in {0, 1, 2, \dots, m - 1}^{k}

. Then we define

n : = \sum_{i = 0}^{k - 1} a_{i} m^{i}

and we say that the string

a_{k} a_{k - 1} \dots a_{1}

is the representation of

n

in the base

m

and define

base_repr (n, m) : = a_{k} a_{k - 1} \dots a_{1}

Isn't this Circular?

In the above definition nothing seems to out of the ordinary until you try $b = 10$ or any fixed number, and start thinking about what this even means.

Understanding the Structure of Numbers: Beyond Base 10 Representation

When we write a number like ${(a b c d)}_{10}$ in base 10, we typically understand it as the expression $a \times 10^{3} + b \times 10^{2} + c \times 10^{1} + d$ . Here, $a$ , $b$ , $c$ , and $d$ are digits ranging from 0 to 9, and the number 10 represents the base. This interpretation seems straightforward until we consider the deeper implications of what the "10" on the right-hand side truly represents. If we claim that this "10" is also written in base 10, we encounter a circular argument: how can we define numbers using the very system we are trying to explain?

The Circularity of Base 10 Representation

The circularity arises because we are using the base 10 system to define itself. The digits $a$ , $b$ , $c$ , and $d$ are combined according to the powers of 10 to produce a number in base 10, but this assumes that the concept of "10" is already understood. This reliance on the same base for both the number and its construction suggests that there is more to numbers than just their syntactical representation in a given base.

A Deeper Approach: Numbers as Abstract Entities

To avoid this circularity, we need to step away from the idea of numbers as simply sequences of digits and instead view them as abstract entities defined by a set of fundamental principles. This leads us to the concept of the Successor function in mathematics, a foundational approach rooted in set theory and logic. The idea is simply that numbers are not syntactical objects, they are things which can never actually see or touch, but they have certain properties about them, and when we create symbols to represent them that's about as close as we can get.

Numbers Through the Successor Function

In this framework, we begin with a single element, typically denoted as $0$ . We then define the successor of $0$ as $S (0)$ , which we call 1. Continuing this process, we define:

$2 : = S (1)$
$3 : = S (2)$
and so on...

Here, each number is not defined by its relationship to a base, but rather as the successor of the previous number. This method builds the entire number system from the ground up, without relying on a predefined base like 10.

Defining Base $b$ Numbers Safely

With this successor-based approach, we can define numbers in any base $b$ without falling into circular reasoning. A number in base $b$ can be expressed as:

${(abcd)}_{b} = a \times b^{3} + b \times b^{2} + c \times b^{1} + d$

Here, the number $b$ is understood as $S (S (\dots S (0) \dots))$ (with $b$ applications of $S$ ). This understanding is independent of any base system and is built solely on the Successor function and the concept of $0$ .

Conclusion: Numbers as Abstract Constructs

The exploration of the circularity in base 10 representation reveals that numbers, when abstracted from their syntactical form, are better understood as constructs built on the Successor function and the element $0$ . This perspective allows us to define numbers safely in any base, avoiding the pitfalls of circular reasoning and providing a more fundamental understanding of numerical systems.

Every Number has a Base

b

Representation

Let

b \in ℕ_{2}

and

n \in ℕ_{0}

then there exists a

k \in ℕ_{1}

and

a_{1}, \dots, a_{k} \in [0, \dots, b - 1]

such that

n = {(a_{k} \dots a_{1})}_{b}

Let $b \in ℕ_{2}$ and we continue with induction. In the base case when $n = 0$ then the representation ${(0)}_{b}$ works. Now let $j \in ℕ_{0}$ and and let $i \in [0, \dots, j]$ and assume that it holds for $i$ , now we'll show it holds true for $j + 1$ .

What we will try to do is extract the largest $b^{m}$ we can from $j + 1$ and then use the induction hypothesis. So let $J : = {m \in ℕ_{1} : b^{m} \leq j + 1}$ , this set has a maximum element because $j + 1$ is an upper bound, it is because we know that $1 \leq j + 1 \leq 2^{j + 1} \leq b^{j + 1}$ therefore $j + 1$ is indeed an upper bound to $J$ , let $l$ be the max element of $J$ and then by the quotient remainder theorem we have some $q, r \in ℤ$ such that $j + 1 = q b^{l} + r with 0 \leq r < b^{l}$ since $r < b^{l} \leq j + 1$ then the induction hypothesis holds on $r$ so that $r$ has a base $b$ representation so that $r = \sum_{i = 0}^{p} c_{i} b^{i}$ where $p < l$ , because if $p \geq l$ then that makes $r = \sum_{i = 0}^{p} x_{i} b^{i} \geq b^{l}$ which is a contradiction since we know that $r < b^{l}$ this means that the representation is exactly ${(q c_{p} \dots c_{0})}_{b}$

Every Base

b

Representation is Unique

For any

b \in ℕ_{2}

and

n \in ℕ_{0}

there is exactly one base

b

representation of

n

Let $b \in ℕ_{2}$ and perform induction on $n$ . So for $n = 0$ we know that the representation ${(0)}_{b}$ and for any other representation where $a \neq 0$ then ${(a)}_{b} \neq 0$ there is exactly one representation as needed.

Now suppose that $n \in ℕ_{0}$ and that for any $k \in [0, \dots n]$ has a unique base $b$ representation, let's prove that $n + 1$ has a unique base $b$ representation, for the sake of contradiction suppose that it has two different representations, which implies that $\sum_{i = 0}^{m} a_{i} b^{i} = n + 1 = \sum_{i = 0}^{k} c_{i} b^{i}$ firstly we claim that $m = k$ for if that were not the case then without loss of generality $m < k$ and note the following $\begin{matrix} \sum_{i = 0}^{m} a_{i} b^{i} & \leq \sum_{i = 0}^{m} (b - 1) b_{i} \\ \leq (b - 1) \sum_{i = 0}^{m} b_{i} \\ \leq (b - 1) \frac{b^{m + 1} - 1}{b - 1} \\ = b^{m + 1} - 1 < b^{m + 1} \end{matrix}$ Note that since $m < k$ we know that $m + 1 \leq k$ then we know that $b^{m + 1} \leq b^{k} \leq \sum_{i = 0}^{k} c_{i} b^{i}$ which is a contradiction because chaining the last few inequalities we obtain $n + 1 = \sum_{i = 0}^{m} a_{i} b^{i} < \sum_{i = 0}^{k} c_{i} b_{i} = n + 1$ thus we deduce that $m = k$ .

Now we additionally claim that $a_{m} = c_{k}$ for if that were not the case then without loss of generality we assume that $a_{m} < c_{k}$ and therefore $(n + 1) - a_{m} b^{m} = \sum_{i = 0}^{m} a_{i} b^{i} - a_{m} b^{m} = \sum_{i = 0}^{m - 1} a_{i} b^{i}$ but also $\begin{matrix} (n + 1) - a_{m} b^{m} & = \sum_{i = 0}^{k} c_{i} b^{i} - a_{m} b^{m} \\ = c_{k} b^{k} + \dots + (c_{m} - a_{m}) b^{m} + \dots + c_{0} b^{0} \end{matrix}$ and since $c_{m} - a_{m} > 0$ this is valid base $b$ representation of $(n + 1) - a_{m} b^{m}$ , but clearly they differ as $a_{k} \neq 0$ and so the length of the two representations are different. This a contradiction because by our induction hypothesis they must have the same base $b$ representation, therefore our assumption that $n + 1$ has two different base $b$ representations is false and therefore by strong induction the original statement is true.

Decimal Representation

The decimal representation of a number

n

is the representation of

n

in the base

10

The decimal representation of a number is the usual way you've most likely dealt with numbers so far, for example when you write

123

you are referring to the number

1 \cdot 10^{2} + 2 \cdot 10^{1} + 3 \cdot 10^{0}

. Note

binary representation

The binary representation of a number

n

is the represetnation of

n

in the base

2

Binary Natural Numbers

We define the following:

𝔹 : = base_repr (ℕ_{0}, 2)

Number of Digits Required in a Base 2 Representation

Given any

n \in ℕ_{0}

prove that the number of digits in it's base 2 representation is given by

⌊ \log_{2} (n) ⌋ + 1

Let $n \in ℕ$ , suppose $n$ requires $d$ digits in it's base 2 representation, we'd like to show that $d = ⌊ \log_{2} (n) ⌋ + 1$ .

At most we have $n = 1 \dots 1$ , that is $d$ 1's in a row. But we know that is

\sum_{i = 0}^{d - 1} 2^{i} = 2^{d} - 1

At a minimum the first digit is a 1 and the rest are zeros (since the powers start at 0 right to left, this is $2^{d - 1}$ ).

We now have the following bound on $n$ .

2^{d - 1} \leq n \leq 2^{d} - 1

Taking log base 2 on on the above inequality yields: (Call this inequality $β$ )

d - 1 \leq \log_{2} (n) \leq \log_{2} (2^{d} - 1)

*Note*: Taking the log respects the inequalities because $\log_{2} (\cdot)$ is a strictly increasing function (check it's derivative)

We will attempt to take the floor of $β$ . Since $d - 1$ is an integer $⌊ d - 1 ⌋ = d - 1$ , as for $\log_{2} (2^{d} - 1)$ , we must look a little closer.

Since $2^{d - 1} \leq 2^{d} - 1 < 2^{d}$ and , we know that

d - 1 = \log_{2} (2^{d - 1}) \leq \log_{2} (2^{d} - 1) < l o g_{2} (2^{d}) = d

Therefore $⌊ \log_{2} (2^{d} - 1) ⌋ = d - 1$ and so the result of taking the floor of $β$ yields

d - 1 \leq ⌊ \log_{2} (n) ⌋ \leq ⌊ \log_{2} (2^{d} - 1) ⌋ = d - 1

In other words

d - 1 \leq ⌊ \log_{2} (n) ⌋ \leq d - 1

d - 1 = ⌊ \log_{2} (n) ⌋ \Leftrightarrow d = ⌊ \log_{2} (n) ⌋ + 1

Base Plus Minus One To a Power is Congruent to Plus Minus One

For any

b \in ℕ_{2}

and for any

n \in ℕ_{1}

and let

x

be the character we use to represent

b - 1

then

{(10^{n})}_{b} = (x \dots x) + 1

Division by 9 Rule

Suppose that

n = (a_{k} \dots a_{0})

then

9 | n

if and only if

9 | \sum_{i = 0}^{k - 1} a_{i}

We know that

10^{n} \equiv 1^{n} (\mod 10)

and therefore

\begin{matrix} n & = \sum_{i = 0}^{k} a_{i} 10^{i} \\ \equiv \sum_{i = 0}^{k} a_{i} (\mod 9) \end{matrix}

Understanding the Structure of Numbers: Beyond Base 10 Representation

The Circularity of Base 10 Representation

A Deeper Approach: Numbers as Abstract Entities

Numbers Through the Successor Function

Defining Base b Numbers Safely

Conclusion: Numbers as Abstract Constructs

Defining Base $b$ Numbers Safely