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)