サクセッサーを指標で定義する

指標に関しては、「指標と不完全インスタンス」の最初の2節を参照。抽象的な概念を簡潔・正確に伝達するには指標が便利。

無限ホテルのような構造の抽象的定式化として Successor という名前の指標を定義する。この指標は、構成素名〈役割ラベル〉として s と p を導入する。

signature Successor {
  0-mor X in Set
  0-mor a in X // 0-圏の0-射の宣言
  let Y := X\{a} // 便宜上の名前 Y を導入
  1-mor s : X → Y in Set
  1-mor p : Y → X in Set

  2-mor s-p-id :: s;p ⇒ id_X : X → X in Set
  2-mor p-s-id :: p;s ⇒ id_Y : Y → Y in Set
}

キーワードをより馴染みやすいものにするなら:

signature Successor {
  sort X in Set
  element a in X
  let Y := X\{a} // 便宜上の名前 Y を導入
  operation s : X → Y in Set
  operation p : Y → X in Set

  equation s-p-id :: s;p = id_X : X → X in Set
  equation p-s-id :: p;s = id_Y : Y → Y in Set
}

モデル〈インスタンス〉は、指標により定義された一般概念の具体例。

// サクセッサーの典型例
model NatSucc of Successor {
  X := Nat
  a := 0
  s := λn∈Nat.( n + 1 ∈(Nat\{0}) )
  p := λm∈(Nat\{0}).( m - 1 ∈Nat )

  s-p-id := (∀n∈Nat.( p(s(n)) = n ) の証明)
  p-s-id := (∀m∈(Nat\{0}).( n(p(m)) = m ) の証明)
}

用語法の定義。

vocabulary Successor {
  "サクセッサー" :=> Successor // 抽象的概念の名称
  "サクセッサー" :=> a model of Successor
  "サクセッサー" :=> the s of (a model of Successor)
  "サクセッサー" :=> the s of (the model NatSucc of Successor)
  "プレデセッサー" :=> the p of (a model of Successor)
  "プレデセッサー" :=> the p of (the model NatSucc of Successor)
}

抽象的概念の名称は、Peano とでもしておいたほうが良かったかも知れないが、次がオーバーロードされる例として Successor にした。

  1. 抽象的に定義された構造の名前(一般名)
  2. 抽象的な構造の構成素の名前(名前空間を持つ一般名)
  3. 抽象的な構造のモデルの構成素の名前(相対的固有名になる)
  4. 抽象的な構造の特定されたモデルの構成素の名前(絶対的固有名になる)

プログラミングとのアナロジーで言えば:

  1. インターフェイスの名前
  2. インターフェイス内の型やメソッドの名前
  3. インターフェイスの実装一般について語るときのメタ構文の一部
  4. 具体的な実装に備わる具体的な型やメソッドの名前

さらに、次のような言い回しも使う。

  • s は X 上のサクセッサー
  • X はサクセッサー s を持つ。
  • p は サクセッサー s に対するプレデセッサーである。
  • サクセッサーはプレデセッサーを持つ。

サクセッサー構造(指標 Successor で定義される構造)が重要なのは、無限集合の特徴付けに使えること。

  • 集合 X 上にサクセッサー構造が存在する ⇒ 集合 X は無限集合

待遇をとれば:

  • 集合 X は有限集合 ⇒ X 上にサクセッサー構造が存在しない

逆向きの命題:

  • 集合 X は無限集合 ⇒ 集合 X 上にサクセッサー構造が存在する

も言える。次の事実を使えばよい。

  1. 集合 $`{\bf N}`$ 上にサクセッサー構造が存在する。
  2. 任意の無限集合は $`{\bf N}`$ と同型な部分集合を持つ。