January 14, 2017
In general, a numeral system could be said to be a mapping \(v\) from a set \(\mathcal{A}\) of human readable symbols, or numerals, to a set of numbers \(S\). We can call this mapping \(v\) a valuation function since it takes a numeral and returns its value.
$$v:\mathcal{A}\rightarrow S$$In most conventional numeral systems which map into the reals, the elements of \(\mathcal{A}\) take on the following form:
$$ A = a_{-m}(\ldots) a_{-1}a_0.a_1a_2a_3(\ldots) $$Where each of the \(a_i\) are non-negative integers called digits and the "." character is called the radix point.
In a base-\(b\) numeral system, where \(b\) is is usually a positive integer, the valuation function is given by
$$ v(A) = \sum_{k = -m}^{\infty}{\frac{a_k}{b^{k}}} $$A natural generalization of this kind of system would be to consider a system which has multiple bases \(b_i\). This is called a mixed radix system. The valuation function for this kind of system is given by
$$ v(A) = \sum_{k= - m}^{0}{a_k\prod_{i = k+1}^{0}{b_i}} + \sum_{k=1}^{\infty}{\frac{a_k}{\prod_{i=1}^{k}{b_i}}} $$where the first term represents the sum of the digit values left of the radix point, and the second term represents the sum of the digit values to the right of the radix point.
As a final generalization, consider a system where each numeral is assigned it's own set of bases $$ B(A) = \{\ldots, b_{-1}, b_0, b_1, b_2, \ldots \} $$
and the valuation function is otherwise the same as before. In this article, we will be considering numeral systems of this type, with the added restriction that we will only be considering numerals of the form $$A = 0.a_1a_2a_3(\ldots)$$ simply because it seems easier to formalize.
Let \(\mathcal{A}\) be a nonempty set of numerals of the form \(A = 0.a_1a_2a_3(\ldots)\), where the \(a_i\) are non-negative integers.
For every \(A \in \mathcal{A}\), let \(B(A)\) be of the form \(\{b_1,b_2,b_3,\ldots\}\) where the \(b_i\) are positive integers.
Define the partial valuation function
$$ v_n(A) = \sum_{k=1}^{n}{\frac{a_k}{\prod_{i=1}^{k}{b_i}}} $$and the valuation function
$$ v(A) = \sum_{k=1}^{\infty}{\frac{a_k}{\prod_{i=1}^{k}{b_i}}}. $$If \(m > n\) then \(v_m(A) \geq v_n(A) \).
Since each term in the summation is non-negative, the sequence of partial values is monotone increasing.
Suppose \( A \in \mathcal{A} \), \(A = 0.a_1a_2a_3(\ldots)\), and \(B(A) = \{b_1,b_2,b_3,\ldots\}\).
Then for every \( i \in \mathbb{N}\), \(a_i < b_i\).
Essentially, every digit must be less than its corresponding base. A numeral system that follows this axiom shall be said to be well-bounded.
Suppose \( A \in \mathcal{A} \), \(A = 0.a_1a_2a_3(\ldots)\), and \(B(A) = \{b_1,b_2,b_3,\ldots\}\).
Then for every \(m > n\), \(v_m(A) < v_n(A) + \frac{1}{\prod_{i=1}^{n}{b_i}} \).
\(v(A) \leq v_n(A) + \frac{1}{\prod_{i=1}^{n}{b_i}} \)
Since the sequence of partial values of \(A\) is monotone increasing and bounded above, it converges to its supremum value. So, as the least-upper-bound of \(\{v_n(A)\}\), \(v(A)\) is less than or equal to any other upper bound.
Let \( A^{(1)},A^{(2)} \in \mathcal{A} \)
Suppose that for some \(k \in \mathbb{N} \), \( a^{(1)}_i = a^{(2)}_i \) for every \( i < k \).
Then \( b^{(1)}_i = b^{(2)}_i \) for every \( i \leq k \).
This axiom allows each base to be precisely determined by the preceding digits.
A numeral \(A\) is said to be terminating if for some \(N \in \mathbb{N} \), \(a_i = 0\) for ever \(i > N \).
Otherwise, a numeral is said to be non-terminating.
A numeral \(A\) is terminating if and only if \(v(A) = v_n(A)\) for some \(n \in \mathbb{N} \).
Let \(A^{(1)}, A^{(2)} \in \mathcal{A}\)
Suppose that \(v(A^{(1)}) = v(A^{(2)}) \), but \(A^{(1)} \neq A^{(2)} \).
Then one of \(A^{(1)}\) and \(A^{(2)}\) is terminating and the other is non-terminating.
Since \(A^{(1)} \neq A^{(2)} \), there must be some least \(k\) such that \(a^{(1)}_k \neq a^{(2)}_k \)
Without loss of generality, assume \(a^{(1)}_k < a^{(2)}_k\).
By Axiom 3, since \(A^{(1)}\) and \(A^{(2)}\) share their first \(k-1\) digits in common, \(A^{(1)}\) and \(A^{(2)}\) share their first \(k\) bases in common, which we shall notate as \(b_i \).
$$ \begin{align} v_k(A^{(2)}) & = v_{k-1}(A^{(2)}) + \frac{a^{(2)}_k}{\prod_{i=1}^{k}{b_i}}\\ & \geq v_{k-1}(A^{(1)}) + \frac{a^{(1)}_k+1}{\prod_{i=1}^{k}{b_i}}\\ & = v_{k}(A^{(1)}) + \frac{1}{\prod_{i=1}^{k}{b_i}}\\ & \geq v(A^{(1)})\\ & = v(A^{(2)})\\ & \geq v_k(A^{(2)}) \end{align} $$All of the above expressions must be equivalent, so \(v(A^{(2)}) = v_k(A^{(2)}) \), meaning \(A^{(2)}\) is terminating.
Also, as a consequence of Lemma 2, \(v_n(A^{(1)}) < v_{k}(A^{(1)}) + \frac{1}{\prod_{i=1}^{k}{b_i}} = v(A^{(1)}) \) for all \(n \in \mathbb{N}\), meaning \(A^{(1)}\) is non-terminating.
No more than two distinct elements in \(\mathcal{A}\) can share the same value.
If a third element were found to have the same value, then by virtue of having the same value as a terminating element, it would have to be non-terminating. But since it is would also has the same value as a non-terminating element, it must also be terminating. This would be a contradiction.
Let \(A^{(1)} \in \mathcal{A}\), \(k \in \mathbb{N}\).
Then for every \(a < b_k \) there exists some \(A^{(2)} \in \mathcal{A}\) such that \(a_i^{(2)} = a_i^{(1)}\) for every \(i < k\), and \(a_k^{(2)} = a\).
Let \(A = 0.a_1a_2a_3(\ldots)\).
Suppose for every \(k \in \mathbb{N} \) there exists an \(A^{(k)} \in \mathcal{A}\) such that \(a_i^{(k)} = a_i\) for every \(i \leq k\).
Then \(A \in \mathcal{A}\).
This axiom guarantees that any numeral that can reasonably be constructed by appending successive digits is part of the numeral system.
Let \(A \in \mathcal{A} \).
Then for every \(N \in \mathbb{N} \) there exists an \( i > N \) such that \( b_i > 1 \).
Let \(r \in (0,1) \).
Define \(v_1^{-1}(r) = 0.a_1a_2a_3(\ldots)\) where
$$ a_n = \sup{\{a : a\leq b_nr_n\}}, $$ $$ r_n = \begin{cases} r & n=1 \\ b_{n-1}r_{n-1}-a_{n-1} & n > 1 \end{cases} $$
and \(b_n\) is well-defined as a consequence of Axiom 3.
Similarly, define \(v_2^{-1}(r) = 0.a_1a_2a_3(\ldots)\) where
$$ a_n = \sup{\{a : a < b_nr_n\}}, $$ $$ r_n = \begin{cases} r & n=1 \\ b_{n-1}r_{n-1}-a_{n-1} & n > 1 \end{cases} $$
and \(b_n\) is again well-defined as a consequence of Axiom 3.
Then \(v_1^{-1}(r) , v_2^{-1}(r) \in \mathcal{A} \), and \(v(v_1^{-1}(r)) = v(v_2^{-1}(r)) = r \).
In order to show that \(v_1^{-1}(r) , v_2^{-1}(r) \in \mathcal{A} \), we need to prove that they can reasonably be constructed in \( \mathcal{A} \). In otherwords, we must show that \(0\leq a_k < b_k \) for every \(k \in \mathbb{N} \). I leave it as an exercise to the reader to verify that this is true. Use the fact that \(0 \leq r_n < 1\) for \(v_1^{-1}(r)\) and \(0 < r_n \leq 1\) for \(v_2^{-1}(r)\).
Let \(A = v_1^{-1}(r)\) or \(A = v_2^{-1}(r)\).
By applying induction to the definition of \(r_n\), we find that
$$ r_n = r \prod_{i=1}^{n-1}{b_i}-\sum_{k=1}^{n-1}{a_k\prod_{i=k+1}^{n-1}{b_i}}. $$Dividing both sides gives
$$ \frac{r_n}{\prod_{i=1}^{n-1}{b_i}} = r-\sum_{k=1}^{n-1}{\frac{a_k}{\prod_{i=1}^{k}{b_i}}}, $$which can be rewritten as
$$ \frac{r_n}{\prod_{i=1}^{n-1}{b_i}} = r-v_{n-1}(A). $$So \( \frac{r_n}{\prod_{i=1}^{n-1}{b_i}} \) is essentially an error term.
As a consequence of Axiom 5, and the fact that \(r_n\) is bounded, \( \frac{r_n}{\prod_{i=1}^{n-1}{b_i}} \) converges to 0.
So \(r = v(A) \)
\(v_1^{-1}(0)\) and \(v_2^{-1}(1)\) are also elements of \(\mathcal{A}\).
\(v_2^{-1}(r)\) is always non-terminating.
This is because \(r_n > 0\), so the error term \( \frac{r_n}{\prod_{i=1}^{n-1}{b_i}} \) for any given partial valuation is always non-zero.
If \(v(A) = 0\), then \(A = v_1^{-1}(0)\).
If \(v(A) = 1\), then \(A = v_2^{-1}(0)\).
Suppose \(v(A) = 0\), \(A \neq v_1^{-1}(0)\).
Then since \(v_1^{-1}(0) = 0.000(\ldots)\) is terminating, by proof of Theorem 1, \(a_k < 0 \) for some \(k\in \mathbb{N}\), contradicting Axiom 1.
Suppose \(v(A) = 1\), \(A \neq v_2^{-1}(1)\).
Then since \(v_2^{-1}(1) = 0.[b_1-1][b_2-1][b_3-1](\ldots)\) is non-terminating, by proof of Theorem 1, \(a_k > b_k-1 \) for some \(k\in \mathbb{N}\), contradicting Axiom 2.
Let \(r \in [0,1] \), \(A \in \mathcal{A} \).
Then \(v(A) = r \) if and only if \(A = v_1^{-1}(r) \) or \(A = v_2^{-1}(r). \)
We have already proven that if \(A = v_1^{-1}(r) \) or \(A = v_2^{-1}(r) \), then \(v(A) = r \).
We have already proven that \(v(A) = 0 \) only if \(A = v_1^{-1}(0)\), and \(v(A) = 1 \) only if \(A = v_2^{-1}(1)\).
Suppose then that \( v(A) = r \), where \(r \in (0,1) \).
Suppose that \(A\) is non-terminating.
Then by Theorem 1, since \(v_2^{-1}(r) \in \mathcal{A}\) is non-terminating, \(A = v_2^{-1}(r)\).
Suppose then that \(A\) is terminating.
Then let \(A^{(1)} = v_1^{-1}(r) \) and \(A^{(2)} = v_2^{-1}(r) \).
\(A \neq A^{(2)}\) so there is a least \(k \in \mathbb{N} \) such that \(a_k > a^{(2)}_k\), and \(A\), \(A^{(1)}\), and \(A^{(2)} \) share the first \(k\) bases and the first \(k-1\) digits.
So the error term \(\frac{r^{(2)}_{k+1}}{\prod_{i=1}^{k}{b_i}}\) is given by
$$ \begin{align} \frac{r^{(2)}_{k+1}}{\prod_{i=1}^{k}{b_i}} & = r - v_{k}(A^{(2)}) \\ & = v_{k}(A) - v_{k}(A^{(2)})\\ & = \frac{1}{\prod_{i=1}^{k}{b_i}} \end{align} $$So \(r^{(2)}_{k+1} = 1 \).
But \(r^{(1)}_{k+1} < 1 \), so it must be that \(a^{(1)}_k \neq a^{(2)}_k \).
So \(A^{(1)} \neq A^{(2)} \)
Since there can at most be two distinct elements of \(\mathcal{A}\) having the same value, then \(A\) must be either of \(A^{(1)}\) or \(A^{(2)}\), but it can't be \(A^{(2)}\), so \(A = A^{(1)}\).
So far we have defined a class of numeral systems that map numerals with positive integer bases and non-negative integer digits onto the closed unit interval. We have shown that each point on the open unit interval has up to two representations, either of which can found by the use of the division algorithms outlined in Lemma 3.
In the next post we will add another axiom and discuss the problem of whether or not rational numbers have repeating representations and vice versa.