Tree

• 集合 S に対して，S の元の有限列全体の集合を S^* とする．S^* は空な列εを含む．
  • S^* を自由モノイドという．これはモノイドの圏から集合の圏への忘却関手の左随伴を与える．
• S^* 上に σ≤στ によって順序を定義する．
• A⊂S^* が prefix 閉であるとは，στ∈A ならば σ∈A であること．
• S^* の prefix 閉部分集合 A は，εを root とする tree と見なせる．
  • A の元を頂点とし，σ，σ s ( σ∈S^*, s∈S ) を辺で結ぶ．
• σ∈S^* に対し，σ↓ = { στ | τ∈S^* } とおく．
• rooted tree の頂点σに対し，価数 val(σ) を root から離れる方の辺の個数とする．
• {0, 1}^* の prefix 閉有限部分集合を 二分木 という．