For the sake of contradiction,assume such a sequence $\{a_i\}_{i=1}^{\infty}$ of integers exists such that only finitely many primes,say $\{p_1,p_2,\dots,p_r\}$ divides atleast one of $a_i$.Also consider an example of such sequence such that $r$ is minimal. For each $a_i$ consider a $r$-tuple $$\bold {v_i}=(v_{p_1}(a_i),v_{p_2}(a_i),\dots,v_{p_r}(a_i))$$ By the given condition,for any 2 distinct $\bold {v_i},\bold {v_j}$ there is a $m\in\{1,2,\dots,r\}$ such that $m$-th entry of $\bold {v_j}$ is smaller than the $m$-th entry of $\bold {v_i}$ Comparing with $\bold {v_1}$, and by $\emph{PHP infinite version}$ there is a $m\in \{1,2,\dots,r\}$ and a sequence of positive integers $\{x_i\}_{i=1}^{\infty}$ such that the $m$- th entry of $\bold {v_{x_i}}$ is smaller than the $m$-th entry of $\bold {v_1}$. Since each entry is a non-negative integers, hence,again using $\emph{PHP infinite version}$ we get a subsequence $\{y_i\}_{i=1}^{\infty}$ of $\{x_i\}_{i=1}^{\infty}$ such that the $m$-th entry of each $\bold {v_{y_i}}$ are equal.Let $c$ be the common entry. Divide each of $a_{y_i}$ by $p_m^{c}$.We get another example of sequence $\{\frac{a_{y_i}}{p_m^c}\}_{i=1}^{\infty}$ such that only $r-1$ primes divide atleast one term of the sequence.Also since this sequence $\{a_{y_i}\}_{i=1}^{\infty}$ is a subsequence of the original sequence that's why this sequence has also had the property that no 2 terms divide one another,so $\{\frac{a_{y_i}}{p_m^c}\}_{i=1}^{\infty}$ too have the property .But this contradicts the minimality of $r$. $\blacksquare$

So what's IMOC?

Actually, this is Dic(k)son's lemma, saying that in every set $S$ consisting of ordered $n$ tuples of natural numbers there are finitely many minimal elements. Particularly, it means if $S$ is infinite then there exists $s_1,s_2\in S$ with $s_1\prec s_2$. One may also see this Bulgarian TST problem which is similar.

Can someone provide a solution with Kobayashi here ,if possible?

primesarespecial wrote: Can someone provide a solution with Kobayashi here ,if possible? I doubt it. The "truth" about this problem does not lie in number theory. This is pure combinatorics. Primes, etc. are involved only for a disguise. We do not need them, we don't need an algebraic operation like addition or multiplication to be defined on the given set/sequence. What it boils down is that in any infinite set of lattice points in $\mathbb{N}^d$ there is an infinite chain. For $x=(x_1,\dots,x_d)\in \mathbb{N}^d$ and $y=(y_1,\dots,y_d)\in \mathbb{N}^d$, we say $x\le y$ if $x_i\le y_i, i=1,\dots,d$. This means that even a stronger claim holds. It's enough to require that there is no infinite subsequence $\{a_{i_k}\}_{k\ge 1}$ of $\{a_i\}_{i\ge1}$ with $a_{i_k}\mid a_{i_{k+1}},k=1,2,\dots$. That is, we allow $a_i\mid a_j$ but only for a finite chain, any two consecutive ones satisfying this condition. Then, the same result holds. On the other hand, Kobayashi is a NT theorem, we have a structure that has addition and multiplication.