Lemma 3.6.9. Suppose that $n \ge 1$ and let $X$ be a set with cardinality $n$. Then $X$ is not empty, and if $x$ is any element of $X$, $X - \{ x \}$ has cardinality $n-1$.

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) There's no bijection from the empty set to a non-empty set.

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 any statement after the qualifier). If the range is not empty it is not surjective since $$ f \: onto \: \leftrightarrow (\forall y \in Y)(\exists x \in X) \: y = f(x) $$ and $X$ being empty we have that $$ (\forall x) \: x \notin X \leftrightarrow \neg((\exists x) \: x \in X) \rightarrow \neg((\exists x \in X) \: y = f(x)),$$ or, in short, $(\exists x \in X)$ is a false statement, whatever statement (depending on $x$) follows.

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) It is easy to check that $g$ is also a bijection.

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$.
2015 MAR 17 (v1.0)
Contact me: m.herrmann followed by an -at- followed by blaetterundsterne.org.

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