Mex function - Lemma 23

Question

We have $\operatorname{mex} S=\min \{n \in \mathbb{N} \mid 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\}$. Prove that $$\operatorname{mex}\left\{d, c \oplus z, \forall z<a \oplus b\right\}=\operatorname{mex}\left\{d, c \oplus\left(x \oplus b\right), c \oplus\left(a \oplus y\right),\forall x<a,y<b\right\}.$$ I attempted to prove it using induction but was unsuccessful. Upon further reading, I found it in lemma 23 of the document below enter link description here However, when the author states "At the same time we know that all values for $x^{\prime} \oplus y$ and $x \oplus y$ bigger than $x \oplus y$ yield different values when added to $z$, so that means that we must have equality", I don't understand why the equation holds.

Answer 1

First of all, what they are trying to prove is false. To see this, let $a=b=1$, and let $c=d=0$.

$$ \newcommand{\t}{\oplus} \newcommand{\mex}{\operatorname{mex}} \mex\left\{d, c \oplus z\mid z<a \oplus b\right\}=\mex\{0,0\oplus z\mid z<0\}=\mex\{0\}=1, \\\,\\\text{but}\\\,\\ \operatorname{mex}\left\{d, c \oplus\left(x \oplus b\right), c \oplus\left(a \oplus y\right)\mid x<a,y<b\right\} \\=\mex\{0,0\oplus (x\oplus 1),0\oplus (1\oplus y)\mid x<1,y<1\}\\=\mex \{0,1\}=2. $$

---

Here is what you can prove, which allows you to prove that $\oplus$ is associative.

Lemma: Let $a,b\in \mathbb N$. Let $A,B\subseteq \mathbb N$ be sets such that $\mex A=a$ and $\mex B=b$. Then $$ a\oplus b=\mex\{a^*\oplus b,a\oplus b^* \mid a^*\in A,b^*\in B\} $$

Proof: Since $\{0,1,\dots,a-1\}\subseteq A$ and $\{0,1,\dots,b-1\}\subseteq B$, we have $$ \{a'\oplus b,a\oplus b'\mid a'<a,b'<b\} \subseteq \{a^*\oplus b,a\oplus b^* \mid a^*\in A,b^*\in B\} $$ This implies that the $\mex$ of the left hand set is at most the $\mex$ of the right hand set. The mex of the LHS is $a\oplus b$, by definition, so we have proved $$a\oplus b\le \mex \{a^*\oplus b,a\oplus b^* \mid a^*\in A,b^*\in B\}.$$To prove the reverse inequality, note that since $a^*\neq a$ for all $a^*\in A$, and $b^*\neq b$ for all $b^*\in B$, we have that $$ a^*\oplus b\neq a\oplus b \qquad \text{and} \qquad a\oplus b^*\neq a \oplus b $$ This shows that $a\oplus b\notin \{a^*\oplus b,a\oplus b^* \mid a^*\in A,b^*\in B\}$, which implies that $a\oplus b\ge \mex \{a^*\oplus b,a\oplus b^* \mid a^*\in A,b^*\in B\}$. (Since $a\oplus b$ is an excluded element, it is at least as big as the minimum excluded element).$\tag*{$\square$}$

The authors made the mistake of trying to turn this Lemma into a more general statement, but in the process they made it false.

Theorem: $\oplus$ is associative.

Proof: Let $x,y,z\in \mathbb N$. In the first equality below, we apply the Lemma, with $a=x,b=y\t z$, $A=\{0,1,\dots,x-1\}$, and $B=\{y'\t z,y\t z' \mid y'<y, z'<z\}$. In the last equality, we again apply the Lemma. For the middle equality, we inductively apply associativity. $$ \begin{align} x\t (y\t z) &=\mex\{x'\t (y\t z),x\t (y'\t z),x\t (y\t z')\mid x'<x, y'<y, z'<z \} \\ &=\mex\{(x'\t y)\t z,(x\t y')\t z,(x\t y)\t z'\mid x'<x, y'<y, z'<z \} \\ &= (x\t y)\t z. \end{align} $$$\tag*{$\square$}$