# Prime basis is a vector space

Just an interesting fact. The prime basis (the system Gödel used for his incompleteness theorem) is a vector space over the integers.

The prime basis encodes sequences of nonzero integers into single natural numbers. I’ve used it to check units at compile time using C++. It’s like a base representation for the integers, except that each digit can be as high as you like. You construct the sequence by raising each consecutive prime to the power of the element in the sequence. For example, the sequence (1,4,0,3,6) is represented by the integer 21345073116 = 98438558526. This is a unique representation of this sequence by the fundamental theorem of arithmetic.

This can be extended to a vector of integers (as opposed to nonnegative integers) by allowing the representaton to be a positive rational. Just take the numberator, decompose it, and subtract the decomposition of the denominator.

I’ll now show that this is a vector space over the field of integers. Take u and v to be vectors, and u and v to be their rational representations. Let a and b be integers.

• u + v := uv
• a u := ua
• 0 = 1 := 1 (that is, the zero vector and the scalar identity are both 1)
• Closure, additive associativity, and additive commutivity trivially hold by the definitions above.
• If u is any vector then u + v = 0 and v = 1/u.
• Multiplicitave associativity: (va)b = v(ab).
• Distributivity of multiplication: (uv)a = uava.
• Distributivity of scalar addition: va + b = vavb.

## 4 thoughts on “Prime basis is a vector space”

1. :( says:

Sadly, integers do not form a field under +,x.

2. Anonymous says:

It is a module over the integers, not a vector space. The integers are a ring, but not a field.