型の定義
べき集合から型 (type)を作り出して、さらにそのべき集合のそのまたべき集合を型と見なして階層的に作りだしていく。
Xのべき集合をP(X)と書くこととする。
例えば、集合Xに対して、
X := {a, b, c}
A型 := P(X) = { ∅, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c} }
B型 := P(P(X))
A型はXのべき集合P(X)である。べき集合の定義により、型は必ずべき集合を作り出すきっかけとなった集合を含む。便宜上、これを台と呼ぶことにする。例えば、P(X)の台はXである。
このとき、自己を含む集合からなる集合、すなわち,
{x | x∈x}
さらに、自己を含まない集合からなる集合、すなわち、
{x | x∉x}
これら二つは型を集めた集合から排除される。
型のブール数変換
ブール数集合をBとおくと、それぞれa0, a1, b0, b1, c0, c1... ω0, ω1がBの元であるとする。このとき、任意の集合Xに対して、
- x∈Xならば、x1∈X'
- x∉Xならば、x0∈X'
- X := X'
この1,2,3の条件を満たす集合X'をつくる。
さて、べき集合P(Y)の元に着目してみよう。例えば、Y = {a, b, c}ならば、
P(Y) = { ∅, {a}, {b}, {c}, {a, b}, {b, c}, {a, c}, {a, b, c} }
これを先ほどのブール数集合で変換していく。
∅ := {a0, b0, c0}
{a} := {a1, b0, c0}
{b} := {a0, b1, c0}
{c} := {a0, b0, c1}
{a, b} := {a1, b1, c0}
{b, c} := {a0, b1, c1}
{a, c} := {a1, b0, c1}
{a, b, c} := {a1, b1, c1}
さらに、次のように、a0を0、a1を1として、{a0, a1}の集合を01というように表記していくと、二進数ができあがる。
∅ := {a0, b0, c0} = 000
{a} := {a1, b0, c0} = 100
{b} := {a0, b1, c0} = 010
{c} := {a0, b0, c1} = 001
{a, b} := {a1, b1, c0} = 110
{b, c} := {a0, b1, c1} = 011
{a, c} := {a1, b0, c1} = 101
{a, b, c} := {a1, b1, c1} = 111
つまり、P(Y) = {000, 001, 010, .... 111}は自然数集合の有限部分集合である。この二進数(自然数集合の元）は一意*1である。
8ビット符号なし整数型はべき集合
8ビット符号なし整数型Aはべき集合である。ビット列から逆変換をしていく。なお、集合Z{a, b, c, d, e, f, g, h}はべき集合の台である。
A := {0, 1, ... 256} = {00000000, 00000001, ... 11111111}
:= { {a0, b0, c0, d0, e0, f0, g0, h0}, {a0, b0, c0, d0, e0, f0, g0, h1}, ... {a1, b1, c1, d1, e1, f1, g1, h1} }
:= { ∅, {h}, ... {a, b, c, d, e, f, g, h} } = P(Z)
このように、ビット数で表記できるものはべき集合に変換が可能である。
