帰納的に定義された構造2

半群

集合 T を、以下の条件をみたす写像が存在する最小のものとします。
  1. var: V→T
  2. +: T×T→T
  3. r: var(V)→V, r(var(x)) = x
  4. p: +(T×T)→T, p(x + y) = x
  5. q: +(T×T)→T, q(x + y) = y
T' = T+V+{0} として、p', q': T'→T'
  1. p': T'→T', x∈+(T×T) のとき p'(x)=p(x), それ以外のとき p'(x)=0
  2. q': T'→T', x∈+(T×T) のとき q'(x)=q(x), それ以外のとき q'(x)=0
と定義します。 S を p', q' で生成される T'→T' の部分集合とします。 x∈T に対して、dom(x)={f∈S|f(x)∈var(V)} と定義します。 x∈T に α: dom(x)→V, α(f)=r(f(x)) を対応させます。

≦: S×S→Boolean を fp'≦fq', f≦g ⇒ fh≦gk (f, g, h, k∈S) と定義します。 ≦ は全順序になります。 n を dom(x) の元の数とするとき、 ≦ によって小さいほうから i 個めの元に i を対応させるよとにより、 dom(x) を N(m)={1, 2, …, m} に対応させることができます。 m, n をそれぞれ dom(x), dom(y) の元の個数、 この対応によって x, y がそれぞれ α: N(m)→V, β: N(n)→V に対応している とすると、 x + y には γ: N(m + n)→V, γ(i)=α(i) (i≦m), γ(m + i)=β(i) (i≦n) が対応することになります。 この対応によって、(x + y) + z = x + (y + z) が成り立ちます。

可換半群

x が α: N(m)→V に対応しているとき、 α-1: V→N(m)→2 と同一視することができます。 x に f: V→N, f(x) は α-1(v) の元の個数, を対応させることができます。 この対応によって x, y がそれぞれ f: V→N, g: V→N に対応している とすると、 x + y には h: V→N, h(v) = f(v) + g(v) が対応することになります。 この対応によって、x + y = y + x が成り立ちます。

べき等律をみたす可換半群

x が f: V→N に対応しているとき、 x に g: V→{0, 1}, f(v)=0 のとき g(v)=0, そうでないとき g(v)=1, を対応させることができます。 この対応によって x, y がそれぞれ f: V→{0, 1}, g: V→{0, 1} に対応している とすると、 x + y には h: V→{0, 1}, f(v)=1 かつ g(v)=1 のとき h(v)=1, そうでないとき h(v)=0, が対応することになります。 この対応によって、x + x = x が成り立ちます。