集合 — 知識ノート

ものの集まり。 数学のほぼすべての定義がこの上に載る。

A = {1, 2, 3}, B = {x | x > 0}

演算#

確率の事象はまさに集合で、和事象・積事象・余事象がそのままこれらに対応する。

$A$ の部分集合すべての集合がべき集合 $2^{A}$ 。 $| A | = n$ なら $| 2^{A} | = 2^{n}$ 。

各要素を「入れる／入れない」で決めるので $2^{n}$ 通り。 QUBO の $x \in {0,1}^{n}$ が $2^{n}$ 個の候補を持つのと同じ数え方。組合せ最適化の難しさの出発点。

自然数と同じ濃度（可算無限）と、実数の濃度（非可算）は違う。 Cantor の対角線論法がこれを示す。計算可能な関数は可算個しかないのに関数は非可算個ある、という形で計算理論にも効いてくる。