Recently I was reading the errata for J.Lee's Introduction to smooth manifolds , and I encountered an interesting algorithm (used in a lemma for Theorem 17.32 in this pdf)) Unfortunately I know nothing about algorithms, so I would appreciate it if someone tells me the name of this algorithm.
From now on, we will fix an arbitrary symmetric relation $R$ on $\mathbb{N}$.
A few terminology: (I improvised them, so it might be different from the standard usage; forgive me in that case.)
Let $A\subset \mathbb {N}$. Then:
- The elements in $A$ are called its vertices;
- We say that two vertices $v,w\in A$ are associated in $A$ (or $v$ is associated with $w$ in $A$) if there is a finite sequence $v_1,\cdots ,v_n\in A$ such that $v=v_1$, $w=v_n$, and $(v_j, v_{j+1})\in R$ for each $j$.
- We say $A$ is connected if every pair of vertices in $A$ are associated in $A$. A maximal connected subset of $A$ is called the component of $A$ The algorithm concerns with the following problem.
Suppose that $\mathbb {N}$ is connected, and suppose that for each $v\in \mathbb N$, there exist at least one, but only finitely many, vertices $w\neq v$ such that $(v,w)\in R$. Then there is a partition $\{A_j\}_{j=1}^{\infty}$ of $\mathbb{N}$ into connected subsets, satisfying the following properties:
- Each $A_j$ is finite.
- For each $j$, there is some $k>j$ such that there are $v_j\in A_j$ and $v_k\in A_k$ with $(v_j,v_k)\in R$ .
The algorithm proceeds as follows:
- We set $A_0=\emptyset$ for convinience.
- Supposing that $A_0,\cdots, A_{n-1}$ are defined, we define $A_{n}$ to be the union of $\{m\}$ and all the finite components of $\mathbb N\setminus (\bigcup_{i<n}A_i \cup \{m\})$, where $m= \min \left(\mathbb N\setminus (\bigcup_{i<n}A_i )\right)$.
- Voila! The resulting sequence $\{A_j\}_{j=1}^{\infty}$ has the desired properties!
Thanks in advance!