Determine an infinite subset $X \subseteq \mathbb{Z}_{\gt 1}$ such that $S \cap (X \times X)$ is a total order on $X$ Let $R$ be a binary relation on $\mathbb{Z}_{\gt 1}$ such that $xRy \iff y=x^2$. Let $S$ be the transitive closure of $R$.
The first problem was to describe $S$. I came up with $S=\{(x,y) \in \mathbb{Z}_{\gt 1} \times \mathbb{Z}_{\gt 1} : \exists n \in \mathbb{N}(y=x^{2^n})\}$. Although I didn't prove it, I think $S$ is antisymmetric, but not reflexive. It is transitive by construction.
Now, the problem is to find an infinite subset $X \subseteq \mathbb{Z}_{\gt 1}$ such that the restriction of $S$ to $X$ is a total order, i.e. $S \cap X \times X$ is a total order on $X$. So what remains is to determine an $X$ that makes $S \cap X \times X$ reflexive and every element of $X$ comparable, right?
I'm stuck on how to find this set. Any hints on how to determine $X$?
 A: First, a clarification.
As suggested by @J.-E. Pin in his comment, I guess that for $S$ you mean the reflexive-transitive closure of $R$, and not the transitive closure of $R$.
Indeed, only the reflexive-transitive closure of $R$ is an order (i.e. a reflexive, transitive, and antisymmetric binary relation), because $R$ and so its transitive closure are not reflexive.
The transitive closure of $R$ is
$$
S' = \left\{(x,y) \in \mathbb{Z}_{\gt 1} \times \mathbb{Z}_{\gt 1} : \exists \, n \in \mathbb{N}_{>0} \, (y=x^{2^n})\right\}
$$
and not
$$
S = \left\{(x,y) \in \mathbb{Z}_{\gt 1} \times \mathbb{Z}_{\gt 1} : \exists \, n \in \mathbb{N} \, (y=x^{2^n})\right\}
$$
as wrongly written in the OP
(I assume $\mathbb{N} =\{0,1,2,3,\dots\}$ and $\mathbb{N}_{>0} = \mathbb{N} \smallsetminus \{0\}$).
In fact, $S$ is the reflexive-transitive closure of $R$. The difference between $S$ and $S'$ is that if you take $n = 0$ in the definition of $S$ (you cannot take $n = 0$ in $S'$), you get $y = x^{2^0} =x$.
But $x^{2^n} \neq x$ for all $n > 0$ and $x \in \mathbb{Z}_{>1}$, hence $S'$ is irreflexive.

The reflexive-transitive closure $S$ of $R$ is antisymmetric (I assume that being antisymmetric means that if $xSy$ and $y S x$ then $x = y$). Indeed, if $y =x^{2^n}$ and $x= y^{2^m}$ then $x = (x^{2^n})^{2^m} = x^{2^{n+m}}$, which is always impossible for $x \in \mathbb{Z}_{>1}$, except when $n = 0 = m$, and in that case $y = x^{2^0} = x$.
(Note that $S'$ is (vacuously) antisymmetric, because $S'$ does not include the case $n = 0$ in its definition and so it is impossible that $xS'y$ and $y S'x$ simultaneously. Said differently, you can prove that $S'$ is asymmetric, that is, if $xS'y$ then it is impossible that $y S'x$.)
By construction, $S$ is reflexive and transitive. Therefore, $S$ is an order.
Clearly, $S$ is not total on $\mathbb{Z}_{>1}$ because $2$ and $3$ are incomparable.

To determine an infinite $X \subseteq \mathbb{Z}_{>1}$ such that $S \cap 
(X \times X)$ is a total order on $X$, just take a natural number greater than $1$ and the sequence of its subsequent squares. For instance,
$$
X = \{2^{2^n} : n \in \mathbb{N}\} = \{2, 4, 16, 256, \dots\}
$$
and more generally, for any $k \in \mathbb{Z}_{>1}$,
$$
X_k = \{k^{2^n} : n \in \mathbb{N}\} = \{k, k^2, k^4, k^8, \dots\}.
$$
The proof that $S$ is total on $X_k$ (for any $k \in \mathbb{Z}_{>1}$) is the following and relies on the fact that $\mathbb{N}$ is totally ordered.
If $x, y \in X_k$, then $x = k^{2^n}$ and $y = k^{2^m}$ for some $n,m \in \mathbb{N}$. We know that $n \leq m$ or $m \leq n$.

*

*If $n \leq m$ then $m = n +p$ for some $p \in \mathbb{N}$. Hence, $y = k^{2^{n+p}} = k^{2^n \cdot 2^p} = (k^{2^n})^{2^p} = x^{2^p}$ and so $xSy$.


*Otherwise, $m \leq n$ and we can conclude similarly that $y S x$.
Therefore, if $x, y \in X_k$ then $x S y$ or $y S x$.
