The proof to this Lemma is already given by Tao. The reason why I'm reviewing it is that some statements aren't as easy and self-evident to me as the author's remarks might suggest. The outline of the proof is as follows: It is first shown that $X$ is non-empty and in a following step a function $g$ is introduced -- an inspired guess -- which turns out to be a bijection from the set $\{ i \in \mathbb{N} : i \in [1, n-1] \}$ to $X - \{x\}$, qualifying $n-1$ as the cardinality of $X$. Following are the statements that troubled me:

(1)

This is true since the empty function $f:\emptyset \rightarrow Y$ is an injection. It is surjective iff the range is empty, too.

Why is the empty function an injection? Because $$ (\forall x_1, x_2 \in X) \: x_1 \neq x_2 \rightarrow f(x_1) \neq f(x_2) $$ is vacuously true since there are no $x_1, x_2$ in $X$ (this holds for

Lacking the bijection b/w $\emptyset$ and $X$ (where $X$ has cardinality $n \ge 1$) both sets have different cardinality from Def. 3.6.1. Causing $X$ to be different from the empty set (whatever the cardinality of the empty set might be).

(2)

Note that $$ g \text{ is a bijection} \leftrightarrow g \text{ is invertible}. $$ A proof for the equivalence can be found here. I.e. if we are able to find an inversion of $g$, $g$ is invertible and a bijection. Hence, there exists a bijection from $X - \{x\}$ to $\{ i \in \mathbb{N} : 1 \le i \le n-1 \}$ . Which, by definition of cardinality, requires $X - \{x\}$ to have cardinality $n-1$.

Consider the following candidate $h:\{ i \in \mathbb{N} \rightarrow 1 \le i \le n-1 \}\rightarrow X-\{x\}$ for an inverse of $g$: $$ h(z) = \begin{cases} f^{-1}(z) & \text{if } z < f(x) \\ f^{-1}(z++) & \text{if } z \ge f(x). \end{cases} $$ Now $h$ is the inverse of $g$ if the following holds: $$ g \circ h = \text{id}_{\{ i \in \mathbb{N} : 1 \le i \le n-1 \}} \wedge h \circ g = \text{id}_{X - \{x\}}, $$ where $\text{id}$ is the identity function on the indexed set. This is equivalent to saying that $$ \underbrace{(\forall z \in \{ i \in \mathbb{N} : 1 \le i \le n-1 \}) \: g(h(z)) = z}_{(i)} \qquad \text{and} \qquad \underbrace{(\forall y \in X - \{ x \}) \: h(g(y)) = y}_{(ii)}. $$ ad (i): Given a number $z < f(x)$. Then we have, since $z = f(y) < f(x)$, $$ g(h(z)) = g(f^{-1}(z)) = f(f^{-1}(z)) = z. $$ If, in turn, $z \ge f(x)$, then $f(y) = z++ > f(x)$, such that $$ g(h(z)) = f(f^{-1}(z++)) - 1 = z. $$ Which allows for the following statement: $$ (\forall z \in \{ i \in \mathbb{N} : 1 \le i \le n-1 \}) \: g(h(z)) = z \qquad \longleftrightarrow \qquad g \circ h = \text{id}_{\{ i \in \mathbb{N} : 1 \le i \le n-1 \}}.$$ ad (ii): Given an object $y \in X - \{x\}$ such that $z = f(y) < f(x)$, the following holds: $$ h(g(y)) = f^{-1}(f(y)) = y. $$ If the object $y$ has a numbering greater than that of the missing element $f(y) > f(x)$, then $z = g(y) = f(y) - 1 \ge f(x)$ and the definitions of $g$ and $h$ yield: $$ h(g(y)) = f^{-1}((f(y) - 1)++) = y. $$ Summarizing the above: $$ (\forall y \in X - \{x\}) \: h(g(y)) = y \qquad \longleftrightarrow \qquad h \circ g = \text{id}_{X - \{x\}}. $$ Rolling backwards, the definition of the inverse $g^{-1} = h$ is satisfied, $g^{-1}$ exists, $g$ is a bijection and the cardinality of $X - \{x\}$ is $n-1$.

Contact me: m.herrmann followed by an -at- followed by blaetterundsterne.org.

This document created with the help of MathJax (Thank you guys!)