位取り記数法を
現在多くのヒトが使用している10進法は次のように表現できます。
任意の非負整数
が成立する。 ただし、有限個の
また、時間の表現が60進法になっているという話もありますが、それは次のように表現できます。
上の例では
非負整数
そして、正の整数
と書かれる整数について考えます。
さらに、位取り記数法の性質を次のように定めます。
任意の非負整数
ならば
完全性は任意の非負整数が位取り記数法で表記できるということであり、一意性は表記できるならばやり方はただ一つということであり、そして単調性は桁の増え方が10進法と同様ということです。
それでは、性質を満たしたり満たさなかったりする例を見てみます。
(1)
(2)
(3)
また、次のような例も考えられます。
(4)
n | 位取り記数法 | 短縮記法 |
---|---|---|
となり、完全性と単調性を満たさないが一意性を満たす。
(5)
このとき、
従って完全性も一意性も単調性も満たさない。
以上の例では次のような性質の満たし方が存在することがわかりました。
例番号 | 完全性 | 一意性 | 単調性 |
---|---|---|---|
(1) | |||
(2) | |||
(3) | |||
(4) | |||
(5) |
これ以外の例は存在するのでしょうか。
実は上の表以外の例が存在しないことが示せます。
まずは必要な補題を示します。
(1)整数
(2)単調性
(1)
(2)
で
完全性と一意性を満たすとき,任意の非負整数
10進法でいえば、99の次が100であり、999の次が1000であるというようなことです。
帰納法を用いて示す.
整数
また,完全性より整数
よって
左辺と右辺を比較すると
すなわち
このとき,整数
と表記できる.同様に整数
が成立すると仮定すると,整数
と表記できる.よって一意性から
が従い,完全性から
と表記すると,補題1の(1)より
だから
となる.従って,
が従い,
となり,
整数
そして次の命題を示します。
(1)完全性と一意性を満たせば単調性を満たす.
(2)単調性を満たせば一意性を満たす.
(1)補題2より,
(2)
となるから単調性より
となる.同様の議論をすれば
以上の命題から、
完全性 | 一意性 | 単調性 |
---|---|---|
が排除され、先に述べた例のような場合しか存在しないことが示されました。
ここでは特に完全性、一意性、単調性のすべてを満たす位取り記数法を正則な位取り記数法とし、次の形に限られることを示します。
正則な位取り記数法は,任意の整数
を満たすものに限る.
補題2を用いて帰納法で示す.
逆にこの等式を満たすならば正則性が従うので、正則性と同値であることがわかります。
実際に10進法では
正則性という条件ではいわゆる