計算理論の基礎(列と組)

[計算理論]計算理論の導入2(列と組について)

計算理論を学ぶ為に列と組についてまとめる。

語句

・列(sequence)：ものをある順序で並べたもの
Example (5, 21, 4)
・組(tuple)：有限な列
k個組(k-tuple)；k個の要素からなる列
・対(pair)：2個組
・冪(べき)集合(power set)：すべての部分集合を含む集合
Example:
\[ A = {0, 1} \]
\[Aの冪集合は\{ \emptyset, \{0\}, \{1\},\{0, 1\} \}\]
・直積(cross product),Cartesian積(Cartesian product)：二つの集合AとBについて、Aの要素を
最初の要素とし、Bの要素を2番目の要素とした対の全体の集合
Example1:
\[A=\{1, 2\}, B=\{x, y, z \} \]
\[A \times B = \{(1,x), (1,y), (1,z), (2,x), (2,y), (2,z) \} \]

・同じ集合の直積
\[A \times A \times A\times ... \times A = A^k \]