Mex - minimum excluded value

Question

We have $\operatorname{mex} S= \min \{n \in \mathbb{N}| n \notin S\}$ and $a \oplus b= \operatorname{mex}\{x\oplus b;a \oplus y,\forall x,y \in \mathbb{N}:x<a,y<b\}.$ Let $n,a \in \mathbb{N},a<2^n$ Prove that $$\{x \oplus a \mid x <2^n\}=\{0;1;\cdots;2^n-1\}.$$ I prove by induction for $n$, but I'm not sure about the induction step. From my research, it seems that the operation $\oplus$ involved is the sum nim, and its properties support the proof. Therefore, do not equate the sum nim with the operation $\oplus$ (or provide me with a proof for their equivalence if possible).

Answer 1

$\newcommand\t{\oplus}\newcommand{\mex}{\operatorname{mex}}$In general, it is a bit tricky to prove things about $\t $ directly from its inductive definition. I will assume the following results have already been proved:

• $a\t a=0$ for all $a$, and $a\t b\neq 0$ when $a\neq b$. [easy]

• $a\t 0=a$ for all $a$. [easy]

• $\t$ is commutative. [easy]

• $\t $ is associative. [this is not easy to prove, as it requires a clever insight].

I will use $\newcommand{\i}[2]{[#1\,.\!.#2]}\i ab$ to refer to the integer interval $\{a,a+1,\dots,b\}$.

Lemma: If $a\neq b$, then $a\t c\neq b\t c$.

Proof: WLOG, $a > b$. Note that $a\t c=\mex \big(\{a'\t c\mid a'<a\}\cup \{a\t c'\mid c'<c\}\big)$. Letting $a'=b$, we see that $a\t c$ is the $\mex$ of a set which contains $b\t c$, which implies $a\t c\neq b\t c$. $\tag*{$\square$}$

Theorem: Let $a,b, n\in \mathbb N$, so that $a<2^n$ and $b<2^n$.

1. $a\t 2^n=a+2^n$
2. $a\t b<2^n$.

First, we prove $a\t 2^n=a+2^n$. By definition,$$a\t 2^n=\mex \{a'\t2^n\mid a'<a\}\cup \{a\t b\mid b<2^ n\}$$

• By induction, we know that $a'\t 2^n=a'+2^n$ for all $a'<a$. This means that $\{a'\t 2^n\mid a'<a\}=\i {2^n}{\,2^n+a-1}$.
• Also by induction, we know that $a\t b<2^n$ for all $b<2^n$. Applying the Lemma, we see that $\{a\t b\mid b<2^n\}$ is a set of $2^n$ distinct natural numbers which are all less than $2^n$, which implies that $\{a\t b\mid b<2^n\}$ is the set of all the natural numbers less than $2^n$. That is, $\{a\t b\mid b<2^n\}=\i 0{2^n-1}$.

We have shown that $$ a\t 2^n=\mex\big(\i 0{2^n-1} \cup \i {2^n}{2^n+a-1}\big)=\mex \i 0{2^n+a-1}=a+2^n. $$

Second, we prove that $a\t b<2^n$. We prove this in three cases:

• Suppose that $a<2^{n-1}$ and $b<2^{n-1}$. By induction, we know $a\t b<2^{n-1}<2^n$.

• Suppose $a<2^{n-1}$ and $2^{n-1}\le b<2^n$. Let $c=b-2^{n-1}$. Since $c<2^{n-1}$, by induction we have $c\t 2^{n-1}=c+2^{n-1}=b$. Therefore, $a\t b=a\t (c\t 2^{n-1})=(a\t c) \t 2^{n-1}$. Since $a,c<2^{n-1}$, we have $a\t c<2^{n-1}$ by induction, so then we have $(a\t c)\t 2^{n-1}=(a\t c)+2^{n-1}<2^n$, again by induction.

• Suppose $2^{n-1}\le a<2^n$ and $2^{n-1}\le b<2^n$. Let $a'=a-2^{n-1}$ and $b'=b-2^{n-1}$. As before, we have $a=a'\t 2^{n-1}$ and $b=b'\t 2^{n-1}$, so $$ a\t b=(a'\t 2^{n-1})\t (b'\t 2^{n-1})=(a\t b)\t (2^{n-1}\t 2^{n-1})=a\t b<2^{n-1}<2^n. $$

Corollary: $\{a \t x\mid x<2^n\}=\i 0{2^n-1}$.

Proof: Using the Theorem, we know that $a\t x<2^n$. Since $ \{a \t x\mid x<2^n\}$ is a set of $2^n$ distinct numbers in the range $\i 0{2^n-1}$ (using the Lemma), it must be the case that $\{a \t x\mid x<2^n\}$ is the entire interval $\i0{2^n-1}$.

---

Let me be clear why this proof by induction is valid. Let $S_1(n,a)$ be the statement that $a<2^n$ implies $a\t 2^n=a+2^n$, and let $S_2(n,a,b)$ be the statement that $a<2^n$ and $b<2^n$ implies $a\t b<2^n$. Here is the dependency structure that my proof uses.

• In order to prove $S_1(n,a)$, I had to assume $S_1(n,a')$ for all $a'<a$, and I had to assume $S_2(n,a,b)$ for all $b<2^n$.

• In order to prove $S_2(n,a,b)$, I had to assume $S_2(n-1,a',b')$, for all $a'<2^{n-1}$ and $b'<2^{n-1}$, and I had to assume $S_1(n-1,c)$ for all $0\le c<2^{n-1}$.

You can check that this dependency structure does not have any cycles (statements that indirectly depend on themselves), so that this is a valid proof by induction.