mex, ニム和

対偶を取ると難しくない. 今 \(\mex S \not\in T\) を仮定すると, \[\begin{align*} \mex T & = \min ( \mathbb N \setminus T ) \\ & = \min ( (\mathbb N \setminus T) \cup \{ \mex S \} ) \\ & = \min \{ \min(\mathbb N \setminus T) , \mex S \} \\ & \leq \mex S \end{align*}\]

\(t = \mex T\) と置くと, これが \(T\) の最小除外数であることから, \[t \not\in T.\] 今 \(S \subset T\) を仮定すると, \[t \not\in S.\] mex-1 を使うと \[t \geq \mex S.\]

\(x=0\) のときは実際に計算すれば確かに成り立っている.

\(x \oplus 0\) について, \(x' \oplus 0 = x'\) がすでに成り立っているとする (\(x'\) で \(x\) 未満の自然数全てを表すのであった). このとき, \[x \oplus 0 = \mex \{ x' \oplus 0 \} = \mex \{ x' \} = x.\]

以上より示された.

\(x=0\) のときは成立.

\(x'\oplus x'=0\) を仮定して \(x \oplus x = 0\) を示す.

各 \(a < x\) について \[a \oplus x = \mex \{ a' \oplus x, a \oplus x' \}\] であるが, \(0 = a \oplus a \in \{ a' \oplus x, a \oplus x' \}\) なので, \(a \oplus x > 0\) である. (これは特に紹介した性質を使ったわけじゃないけど, \(0\) を含んでればその最小除外数が \(0\) ではないのは明らかでしょう.)

今度は \[x \oplus x = \mex \{ x' \oplus x \}\] を考えると, 今さっき \(x' \oplus x > 0\) であることを示したから, \(0 \not\in \{ x' \oplus x \}\). mex-1 より, \(0 \geq x \oplus x\). \(0\) 未満の数は無いのでもちろん \(0 = x \oplus x\).

まず \(k\) に関して, 更にその中では \(x,y\) に関する帰納法で示す.

すなわち, \((k,x,y)\) の場合を示すのに次の2つを同時に仮定する.

1. \(\forall 0 \leq x',y' < 2^{k-1}\),
   • \(x' \oplus (y' + 2^{k-1}) = (x' \oplus y') + 2^{k-1}\)
   • \((x' + 2^{k-1}) \oplus (y' + 2^{k-1}) = x' \oplus y'\)
   • \(\{ x' \oplus z \mid 0 \leq z < 2^{k-1} \} = \{0,1,\ldots,2^{k-1}-1\}\)
2. \(\forall 0 \leq x' < x\) OR \(\forall 0 \leq y' < y\),
   • \(x' \oplus (y' + 2^k) = (x' \oplus y') + 2^k\)
   • \((x' + 2^k) \oplus (y' + 2^k) = x' \oplus y'\)

この仮定の下で \(x \oplus y, x \oplus (y + 2^k), (x + 2^k) \oplus (y + 2^k)\) を考える.

基本的に最小除外数の対象となる集合を考えて分解して帰納法の仮定が使えるところを使えば示される.

\(S = \{ x' \oplus y, x \oplus y' \}\) と置くと \(x \oplus y = \mex S\). \(r = x \oplus y\) と置けば \[\{0,1,\ldots,r-1\} \subset S \land r \not\in S\] (mex-0).

次に \(T = \{ x' \oplus (y+2^k), x \oplus (y+2^k)' \}\) と置けば \(x \oplus (y+2^k) = \mex T\) である. この \(T\) を更に調べると

\[\begin{align*} T & = \{ x' \oplus (y+2^k), x \oplus (y+2^k)' \} \\ & = \{ x' \oplus (y+2^k), x \oplus (y'+2^k) \} \cup \{ x \oplus z \mid 0 \leq z < 2^k \} \\ & = \{ (x' \oplus y) + 2^k, (x \oplus y') + 2^k \} \cup \{0,1,\ldots,2^k-1\} \\ & = \{ s + 2^k \mid s \in S \} \cup \{0,1,\ldots,2^k-1\} \\ \end{align*}\]

ということまで分かる. \(\{0,1,\ldots,r-1\} \subset S\) だったので, これらに \(+2^k\) して \(\{2^k,2^k+1,\ldots,2^k+r-1\} \subset T\) である.

したがって \(\{0,1,\ldots,2^k,2^k+1,\ldots,2^k+r-1\} \subset T\) まで言える.

また \(r \not\in S\) だったので, \(2^k + r \not\in T\).

以上から \(\mex T = 2^k + r = 2^k + (x \oplus y)\) が分かった.

次に \((x + 2^k) \oplus (y + 2^k)\) について考える. \(U = \{(x+2^k)' \oplus (y+2^k), (x+2^k) \oplus (y+2^k)'\}\) と置けば \((x + 2^k) \oplus (y + 2^k) = \mex U\) であるわけだが

\[\begin{align*} U & = \{(x+2^k)' \oplus (y+2^k), (x+2^k) \oplus (y+2^k)'\} \\ & = \{(x'+2^k) \oplus (y+2^k), (x+2^k) \oplus (y' + 2^k) \} \cup \{ z \oplus (y+2^k), (x+2^k) \oplus z \mid 0 \leq z < 2^k \} \\ & = \{x' \oplus y, x \oplus y' \} \cup \{ z \oplus (y+2^k), (x+2^k) \oplus z \mid 0 \leq z < 2^k \} \\ & = \{x' \oplus y, x \oplus y' \} \cup \{ (z \oplus y)+2^k, (x \oplus z) + 2^k \mid 0 \leq z < 2^k \} \\ & = S \cup \{ z+2^k \mid 0 \leq z < 2^k \} \\ \end{align*}\]

というわけでやはり \(\{0,1,\ldots,r-1\} \subset U\) かつ \(r \not\in U\) がわかるので \(\mex U = r = x \oplus y\) であることがわかる.

最後に. \[\begin{align*} \{x \oplus z \mid 0 \leq z < 2^k \} & = \{ x \oplus z \mid 0 \leq z < 2^{k-1} \} \cup \{ x \oplus z \mid 2^{k-1} \leq z < 2^k \} \\ & = \{ x \oplus z \mid 0 \leq z < 2^{k-1} \} \cup \{ x \oplus z + 2^k \mid 0 \leq z < 2^{k-1} \} \\ & = \{0,1,\ldots,2^{k-1}-1\} \cup \{2^{k-1}, 2^{k-1}+1,\ldots,2^k-1\} \\ & = \{0,1,\ldots,2^k-1\} \end{align*}\]

以上から全て示された.

\[x \oplus y = ((x-2^k)+2^k) \oplus ((y-y_k 2^k)+y_k 2^k) = ((x-2^k) \oplus y- y_k2^k) + (1-y_k) 2^k\]

\((x-2^k) \oplus y- y_k2^k) = (x-2^k) \wedge y- y_k2^k)\) であると仮定すれば, \[\begin{align*} x \oplus y & = (1-y_k) 2^k + ((x-2^k) \wedge y- y_k2^k)) \\ & = (x_k \wedge y_k) 2^k + \sum_{i=0}^{k-1} (x_i \wedge y_i) 2^i \\ & = x \wedge y \end{align*}\] というわけでビットに関する帰納法で示される.