PS

Free monoid

定義

Finite set

n 個の元をもつ集合は、全て本質的に等しいので、一つ選んで

  • n

と書く。特に、

  • 0 = \emptyset

n-tuple

集合 S と n \in \mathbb{N} について、 n-tuple とは、

  • S^{n} := \lbrace a \mid a : n \rightarrow S \rbrace

の元:

  • (a _ i \in S) _ {i \in n} = (a _ 1,\ldots,a _ n)

のこと。

特に、

  • S ^ {0} = \lbrace \emptyset \rbrace

つまり、 0-tuple は、定義により \emptyset : \emptyset \rightarrow S のことだが、特別に、 \epsilon と書く。

Free monoid

集合 S について、monoid (S ^ {\ast}, \ast, \epsilon) を次のように定義できる。

  • S ^{\ast} = \bigcup\limits _ {n \in \mathbb{N}} S ^ n
  • (a _ 1, \ldots ,a _ n) \ast (b _ 1, \ldots, b _ m) = (a _ 1, \ldots, a _ n, b _ 1, \ldots, b _ m)

これをfree monoid over S という。 なぜfreeという形容詞なのかが分からない。

参考文献