In Rudin's principle of mathematical analysis or other books, they often write that pick $x_1$ and suppose we have chosen $\{x_1,\dots,x_n\}$, then choose $x_{n+1}$, and says by induction, we have construct a sequence $\{x_n \}_{n=1}^\infty$
For example, if I want to prove: Let $X$ be a metric space and $K \subseteq X$. If every infinite subset of $K$ has an accumulation point in $K$, then $K$ is totally bounded.
Prove it by contradiction. $\exists r \gt0$ s.t. $K$ can not be covered by finitely many open balls centered in $K$ with radius $r$.
Choose an arbitrary point $x_1\in K$, then $K$ can not be covered by $B(x_1,r)$. So $$\exists x_2\in K-B(x_1,r)$$ and $K$ can not be covered by $$B(x_1,r)\cup B(x_2,r)$$
Suppose we have choose $x_1,\dots x_n$, hence $K$ can not be covered by $$B(x_1,r)\cup \dots \cup B(x_n,r)$$, choosing $$x_{n+1}\in K- \Bigl( B(x_1,r)\cup \dots \cup B(x_n,r) \Bigr)$$
By inaction, we have constructed a sequence $\{x_n \}_{n=1}^\infty$ in $K$ s.t. $$x_i\neq x_j \;\;\forall i\neq j \text{ and } d(x_i,x_j)\geqslant r $$ , then $\dots \dots$ (skip the whole proof)
If I want to write it more formally, let $$S=\{n \in N \;| \; \{x_k \}_{k=1}^n\in K \text{ such that } d(x_i,x_j)\geqslant r\;\; \forall i\neq j \text{ and } x_k\in K- \Bigl( B(x_1,r)\cup \dots \cup B(x_{k-1},r) \Bigr) \} \;\;\;\color{red}{(\star)}$$
First, choosing an arbitrary point $x_1\in K$. Suppose we have chosen $\{ x_1,\dots,x_{n-1}\}$ satisfying that $$d(x_i,x_j)\geqslant r \;\; \forall i\neq j \text{ and } x_k\in K- \Bigl( B(x_1,r)\cup \dots \cup B(x_{k-1},r) \Bigr)\text{, }\forall k=1,\dots,n-1$$
Now, choose $$x_n \in K- \Bigl( B(x_1,r)\cup \dots \cup B(x_{n-1},r) \Bigr)$$, then $$d(x_n,x_k)\geqslant r \;\;\forall k=1,\dots,n-1$$
Hence, $S=\Bbb N$, which means $\{x_n \}_{n=1}^\infty$ is constructed and $d(x_i,x_j)\geqslant r \;\; \forall i\neq j$
$\color{blue}{\textrm{My question :}}$ I thinks the set $S$ in $\color{red}{(\star)}$ for induction looks weird, since I have never write this for construction. Could someone help me to write it more formally, thanks a lot!!
Best Answer
More formally, the kind of construction you're outlining actually boils down to a combination of an application of the Axiom of Choice and a construction by recursion.
In particular, one of the formulations of the Axiom of Choice is: for every set $K$, there is a function $c : P(K) \setminus \{ \emptyset \} \to K$ such that for every $S \subseteq K$ with $S \ne \emptyset$, we have $c(S) \in S$. Now, suppose we choose such a function $c$ (where this "choose" is actually not a reference to the Axiom of Choice, it stands for an application of the formal proof rule of existence elimination, $\exists E$). Then under the given hypotheses, we can recursively construct a sequence where $x_n = c\left( K \setminus \bigcup_{i < n} B(x_i, r) \right)$.
To illustrate the gap in the argument you're trying to make, it does not follow just from the fact that a finite sequence of any arbitrary length exists satisfying some property that an infinite sequence exists satisfying that property. For example, in $\mathbb{N}$, for any $k$ there exists a finite sequence in $\mathbb{N}$ of length $k$ which is strictly decreasing -- namely $(k, k-1, k-2, \ldots, 2, 1)$. However, it does not follow from this that there exists an infinite sequence in $\mathbb{N}$ which is strictly decreasing -- which does not exist since $\mathbb{N}$ is well-ordered.