遺伝的記法とグッドスタインの定理

  • 昨日のMIKU
  • n進法というのがある。n^kとその係数との和で自然数を表す方法
  • n進法表記だと、n^kとすることで、k+1個の0,1,...,(n-1)の数値の並びで大きな自然数が表せるのだが、k+1個の並びというのを考えるときにk>nとなって、気持ち悪い、とも感じられる
  • この気持ち悪さを解消するのが、遺伝的記法。k乗のkを0,1,...,n-1の数だけで表しましょうというやり方
  • たとえば、35=2^5+2^1+2^0=2^(2^2+2^1)+2^1+2^0のように
  • このような遺伝的表記から作り出される数列がグッドスタイン数列で必ず0に収束する
  • その証明をするのに、『もっとも大きい自然数より大きい数w』というのを導入した(0,1,2,...,w+0,w+1,w+2,...,w+w+0=2w,2w+1,...,w^2,w^2+1,...,w^w^w,w^w^w+1,...)という無限に長い自然数の列よりもっと長い順序のある数の列を用いた証明がある
  • これは「決定不明な命題」「公理の取り方によって決定できたりできなかったりする命題」の例として取り上げられる、という話があった
  • この遺伝的記法とかって、いかにもハスケル的、と思ったら、書いている方がいらっしゃいました(こちら)