[proofplan] We construct by recursion a sequence of vertices $x_1, x_2, \ldots \in \mathbb{N}$ and a nested descending sequence of infinite sets $\mathbb{N} = S_0 \supseteq S_1 \supseteq S_2 \supseteq \cdots$, together with colours $c_1, c_2, \ldots \in \{\text{red}, \text{blue}\}$, such that $x_i \in S_{i-1}$, $S_i \subseteq S_{i-1} \setminus \{x_i\}$ is infinite, and every edge from $x_i$ to $S_i$ has colour $c_i$. At the induction step, $x_i$ has infinitely many edges to $S_{i-1} \setminus \{x_i\}$ (two colours, infinitely many edges, so one monochromatic neighbourhood is infinite); this forces existence of $S_i$. By construction, for every $i < j$ the edge $x_i x_j$ has colour $c_i$ since $x_j \in S_i$. Finally, since the sequence $(c_i)$ takes two values infinitely often, one colour $c_\ast$ appears for infinitely many indices $i_1 < i_2 < \cdots$; the subset $X = \{x_{i_1}, x_{i_2}, \ldots\}$ is infinite and every edge within $X$ has colour $c_\ast$. [illustration:infinite-ramsey-nested-sequence] [/proofplan] [step:Construct the nested sequences $(x_i)$, $(S_i)$, $(c_i)$ by recursion] We construct sequences $x_1, x_2, \ldots \in \mathbb{N}$, infinite sets $S_0 \supseteq S_1 \supseteq S_2 \supseteq \cdots$, and colours $c_1, c_2, \ldots \in \{\text{red}, \text{blue}\}$ by recursion on $i \geq 0$, maintaining the invariant: $(\ast)$ For each $i \geq 1$: $x_i \in S_{i-1}$; $S_i \subseteq S_{i-1} \setminus \{x_i\}$; $S_i$ is infinite; and for every $y \in S_i$ the edge $x_i y$ has colour $c(\{x_i, y\}) = c_i$. **Base.** Set $S_0 = \mathbb{N}$, which is infinite. **Inductive step.** Suppose $S_{i-1} \subseteq \mathbb{N}$ is an infinite set for some $i \geq 1$. Pick any $x_i \in S_{i-1}$ (possible since $S_{i-1}$ is non-empty), and consider the partition of $S_{i-1} \setminus \{x_i\}$ by the colour of the edge to $x_i$: \begin{align*} R_i &= \{y \in S_{i-1} \setminus \{x_i\} : c(\{x_i, y\}) = \text{red}\}, \\ B_i &= \{y \in S_{i-1} \setminus \{x_i\} : c(\{x_i, y\}) = \text{blue}\}. \end{align*} Then $R_i \sqcup B_i = S_{i-1} \setminus \{x_i\}$, which is infinite (the set $S_{i-1}$ is infinite and removing one element preserves infinity). A union of two sets is infinite only if at least one of them is infinite, hence at least one of $R_i$, $B_i$ is infinite. Define \begin{align*} (S_i, c_i) &= \begin{cases} (R_i, \text{red}) & \text{if } R_i \text{ is infinite}, \\ (B_i, \text{blue}) & \text{otherwise (so } B_i \text{ is infinite)}. \end{cases} \end{align*} Then $S_i$ is an infinite subset of $S_{i-1} \setminus \{x_i\}$ such that every $y \in S_i$ satisfies $c(\{x_i, y\}) = c_i$. This preserves the invariant $(\ast)$ at index $i$, completing the recursion. [guided] The core difficulty of the infinite problem is that we cannot pigeonhole on a finite set. Instead we build an infinite object — a nested sequence of infinite sets $S_{i-1} \supseteq S_i$ — where at each stage we have a choice of infinitely many successors. **Why a nested sequence of infinite sets?** Because at each step we want to extract a single vertex $x_i$ together with its monochromatic neighbourhood, and still leave enough material to continue. The right notion of "enough" is that the remaining neighbourhood is infinite. **The recursion, carefully.** *Base.* Set $S_0 = \mathbb{N}$. *Inductive step.* Given an infinite $S_{i-1}$, choose any $x_i \in S_{i-1}$. Consider the edges from $x_i$ to the other elements of $S_{i-1}$. These edges are in bijection with $S_{i-1} \setminus \{x_i\}$, which is still infinite (removing one point from an infinite set leaves it infinite). Each such edge has one of two colours, so the partition \begin{align*} S_{i-1} \setminus \{x_i\} = R_i \sqcup B_i \end{align*} where $R_i, B_i$ collect the vertices joined to $x_i$ by red, resp. blue, edges, has at least one infinite part: otherwise, $|S_{i-1} \setminus \{x_i\}| = |R_i| + |B_i| < \infty + \infty$ would be finite. Contradiction. Pick whichever is infinite (break ties by picking $R_i$), call it $S_i$, and call the corresponding colour $c_i$: \begin{align*} (S_i, c_i) &= \begin{cases} (R_i, \text{red}) & R_i \text{ infinite}, \\ (B_i, \text{blue}) & \text{otherwise}.\end{cases} \end{align*} The invariants all hold by construction: $S_i \subseteq S_{i-1} \setminus \{x_i\}$, $S_i$ is infinite, and for every $y \in S_i$, $c(\{x_i, y\}) = c_i$ by the definition of $R_i$ / $B_i$. **Why this uses countable choice.** At each step we pick $x_i$ and pick one of $R_i, B_i$; the countable sequence of choices is captured formally by the axiom of dependent choice (a weak form of the axiom of choice). We do not need the full axiom of choice since each choice is from a non-empty, definable set. [/guided] [/step] [step:Verify that the edge colour $c(x_i x_j)$ depends only on the smaller index $i$] We claim that for any $i < j$ in $\mathbb{N}_{\geq 1}$, \begin{align*} c(\{x_i, x_j\}) = c_i. \end{align*} Indeed, by the nesting $S_{i} \supseteq S_{i+1} \supseteq \cdots \supseteq S_{j-1}$ from invariant $(\ast)$, and since $x_j \in S_{j-1} \subseteq S_i$, we have $x_j \in S_i$. The invariant states that every $y \in S_i$ satisfies $c(\{x_i, y\}) = c_i$; applying this with $y = x_j$ gives $c(\{x_i, x_j\}) = c_i$. [guided] The construction is useful because the colour of any edge in the sequence $(x_1, x_2, \ldots)$ is determined by the smaller index. This is what converts the infinite problem into a pigeonhole on colours. **Why $x_j \in S_i$ for $j > i$.** The sequence $(S_n)$ is nested decreasing: $S_{i} \supseteq S_{i+1} \supseteq \cdots \supseteq S_{j-1}$. The invariant $(\ast)$ says $x_{j} \in S_{j-1}$, and $S_{j-1} \subseteq S_i$ by nesting, so $x_j \in S_i$. **Why this forces $c(\{x_i, x_j\}) = c_i$.** The invariant at stage $i$ says every $y \in S_i$ satisfies $c(\{x_i, y\}) = c_i$. Setting $y = x_j \in S_i$ gives $c(\{x_i, x_j\}) = c_i$. This is the payoff of the construction: the colour of the edge $x_i x_j$ depends only on the smaller of the two indices. In particular, among the vertices $\{x_1, x_2, \ldots\}$, the colouring of the edges reduces to the colouring of the indices themselves — each index $i$ gets the colour $c_i$, and $c(\{x_i, x_j\}) = c_{\min(i,j)}$. [/guided] [/step] [step:Extract a monochromatic infinite subset via pigeonhole on the colour sequence $(c_i)$] The sequence $(c_i)_{i \geq 1}$ is an infinite sequence of elements of $\{\text{red}, \text{blue}\}$. Since an infinite set cannot be the finite union of finite sets, \begin{align*} \{i \geq 1 : c_i = \text{red}\} \cup \{i \geq 1 : c_i = \text{blue}\} &= \mathbb{N}_{\geq 1} \end{align*} implies at least one of the two index sets is infinite. Let \begin{align*} c_\ast &\in \{\text{red}, \text{blue}\} \end{align*} be a colour with $I_\ast := \{i \geq 1 : c_i = c_\ast\}$ infinite, and enumerate $I_\ast = \{i_1 < i_2 < i_3 < \cdots\}$. Set \begin{align*} X &= \{x_{i_k} : k \geq 1\} \subseteq \mathbb{N}. \end{align*} First, $X$ is infinite. The $x_i$'s are pairwise distinct: $x_j \in S_{j-1} \subseteq S_i$ and $x_i \notin S_i$ (by $(\ast)$, $S_i \subseteq S_{i-1} \setminus \{x_i\}$), so $x_j \neq x_i$ for $j > i$. Hence $k \mapsto x_{i_k}$ is injective from the infinite set $I_\ast$ into $X$, so $X$ is infinite. Second, $X^{(2)}$ is monochromatic of colour $c_\ast$. Let $\{x_{i_k}, x_{i_\ell}\} \in X^{(2)}$ be an edge in $X$, with (WLOG) $k < \ell$, so $i_k < i_\ell$. By the previous step, \begin{align*} c(\{x_{i_k}, x_{i_\ell}\}) = c_{i_k} = c_\ast \end{align*} since $i_k \in I_\ast$. Hence every edge in $X$ has colour $c_\ast$, and $X \subseteq \mathbb{N}$ is the desired infinite monochromatic subset. [guided] We have a sequence of colours $(c_1, c_2, c_3, \ldots)$, each red or blue, one per index. Having reduced to a 2-colouring of an infinite *index set* $\mathbb{N}_{\geq 1}$, we finish by pigeonhole. **Pigeonhole on colours.** An infinite set partitioned into two classes must have at least one infinite class: otherwise the infinite set would be a union of two finite sets, which is finite — contradiction. So at least one of $\{i : c_i = \text{red}\}$, $\{i : c_i = \text{blue}\}$ is infinite. Pick one and call it $I_\ast$, and let $c_\ast$ be the corresponding colour. **Extracting $X$.** Enumerate $I_\ast = \{i_1 < i_2 < \cdots\}$ (possible because $I_\ast$ is an infinite subset of $\mathbb{N}$). Define $X = \{x_{i_k} : k \geq 1\}$. *Why $X$ is infinite.* We need the $x_{i_k}$ to be distinct; equivalently, the map $k \mapsto x_{i_k}$ is injective. In fact all the $x_i$'s are distinct: for $i < j$, the invariant $(\ast)$ gives $x_j \in S_{j-1} \subseteq S_i$ and $x_i \notin S_i$ (since $S_i \subseteq S_{i-1} \setminus \{x_i\}$), so $x_j \neq x_i$. Hence the restriction to $I_\ast$ is also injective, and $|X| = |I_\ast| = \infty$. *Why $X^{(2)}$ is monochromatic.* Take any edge $\{x_{i_k}, x_{i_\ell}\}$ in $X$ with $k < \ell$, so $i_k < i_\ell$. By the previous step the colour of this edge is $c_{\min(i_k, i_\ell)} = c_{i_k}$. But $i_k \in I_\ast$, so by definition $c_{i_k} = c_\ast$. Thus every edge in $X$ has colour $c_\ast$. This completes the proof: $X \subseteq \mathbb{N}$ is infinite with $X^{(2)}$ monochromatic of colour $c_\ast$. [/guided] [/step]