Notations: Formalizing Place-Value

Notation matters.

In my last post I called prime factorization a "notation" for the natural numbers. It is a formal way of representing them. Mathematically speaking, a notation is just a correspondence between 2 sets: the notation set, and the objective set. Every member of the objective set has a corresponding notation.

For example, take place-value notation, which is a notation for all whole numbers including zero. The whole numbers are defined one way, and they are the objective set. The place-value notation is defined another, and let's call it the notation set. We can place a correspondence between the two, which is just an "onto" function from the notation set to the objective set.

First, let's define the set of whole numbers using the following 5 rules. These 5 rules are a derivation of Peano's Axioms for Whole Numbers.

0 is a whole number.


For every whole number n, there is a whole number n', the increment of n.

Let X be a subset of the whole numbers. If 0 is in X and for every n in X, n' is also in X, then X contains all whole numbers. This is the principle of mathematical induction.

Equality:
For all whole numbers n, the increment n' is not equal to 0.


For all whole numbers n and m, n' = m' implies that n = m.

Using the principle of mathematical induction, these 2 rules for equality sufficiently define equality on all whole numbers. With these 5 rules, we can prove everything that we know about whole numbers. This includes the rules for addition, subtraction, multiplication, division, as well as the properties of prime numbers and number theory. They will also be the basis for one day proving or disproving the twin prime conjecture.

Now that the whole numbers have been straightened out, we'll take a look at our place-value notation. In this version of place-value, zero is represented not by 0, but by [], the empty list of digits, and 12:3 is equivalent to 123, just so that we have some notation for meaning "append onto".

Let D be the set of digits in this place value system, and for arguments sake let it contain 10 digits, with a correspondence to the first 10 whole numbers. This correspondence will be mapped by the function f.


f(0) = 0
f(1) = 0'
f(2) = 0''
...
f(9) = 0'''''''''

Of course, we can let this contain d digits and make this more general. I wrote down some basic rules for place-value notation.

[] is in the place-value notation.


For every value n in the place-value notation, n:d is also in the place-value notation, where d is a digit.

Let X be a subset of the place-value notation. If [] is in X and for every n in X and every digit d, n:d is also in X, then X contains all of the place-value notation.

Equality:

For all place-value n and digit d, n:d is equal to [] if and only if n=[] and d=0.

For all place-values and and digits and .


Now that place-value notation has been defined, with 5 rules that look strikingly similar to the 5 rules of whole numbers, we may define a correspondence between the 2. Every place-value gets mapped to a whole number. We'll call this function g.


g([]) = 0
g(n:d) = 10*g(n) + f(d)

First of all, note that this function is now properly defined for everything in the place value notation because of its version of the induction principle. Furthermore, and this would require a formal proof, we can show that equal inputs produces equal outputs.

The multiplication and addition operators on whole numbers can be defined on whole numbers using the axioms we have, even though I haven't done it explicitly here.

Now in order to prove that the function g specifies a notation (that is, it's onto), we need to show that for each whole numbers n, there exists some place value m such that g(m) = n.

Once that is proven (and it can be) then place-value notation can be used as a substitute for W and in fact we can write whole numbers using place-value notation and not have to worry about converting between the two because we know that there is a correspondance.