Haskellで超現実数1&2

「数学ガールの秘密ノート／数を作ろうを読み進めて、自然数→整数→有理数、と勉強してきた。
参考書の中で面白そうなのがあったので調べてみると、Knuth博士が書いた「Surreal Numbers」という本があった。超現実数とは、実数を拡張し、無限小や無限大も含む新しい数構造らしい。本書の中では、無人島にたどり着いた男女二人が岩に書かれた数式を解いていくというミステリーになっていて、まるで不思議の国のアリス第二弾という感じだ。
本書は、もちろん日本語版の「超現実数―数学小説」もある。
参考書にコンウェイの「On Numbers and Games」も超現実数とゲームに関する本で面白そうだが高額すぎて買えない。

備忘録として書いていく。

超現実数は前の数から次の数が作られる。
全ての超現実数は、$$x=(X_L,X_R)$$のように超現実数の集合$X_L,X_R$として再帰的に定義される。イメージとしては、どんどんと階層的な集合が出来上がっていく感じだ。

ルール(1)とルール(2)

$$X_L\ngeq X_R　ならば、x=(X_L,X_R)\qquad(1)$$

$$x\leq y　の意味は　X_L\ngeq y　かつ\ x\ngeq Y_R\qquad(2)$$

$(2)$の不等式が$\leq$ではなく、$\ngeq$となっているのは、$X_L,Y_R$のどちらかが空集合$\phi=\{\}$になった時に真になるというのがミソようだ。
日を追うごとに少しずつ数を増やしていくというストーリーの流れになっている。

初日

空集合を$\phi=\{\}$とすると、最初の数ゼロは$$0=(\phi,\phi)$$となる。

二日目

二日目は最初の数ゼロをつかって、二つの数$-1と1$をつくる。

$$-1 = (\phi,\{0\})　かつ　1 = (\{0\},\phi)$$

$-1$について証明すると、どんな空集合の要素も$0$より大きくも等しくもならない。
$1$について証明すると、要素$0$は空集合のどんなような要素に対しても大きくも、等しくもならない。

Haskellでルール1

-- Haskell
isSurreal (a, b) = not (or [x >= y| x <- a, y <- b])   -- Rule (1)
zero = ([],[])          -- 0
one = ([],[zero])       -- 1
minusOne = ([zero],[])  -- -1
ghci> isSurreal zero
True
ghci> isSurreal minusOne
True
ghci> isSurreal one
True
ghci> isSurreal ([zero],[zero])    -- ({0},{0})
False

ちなみに$(\{0\},\{0\})$は偽となり、超現実数にならない。