After watching Numberphile´s video with Jared Litchman about primitive sets I started playing around with this notion (in case you didn't see it: a set $S\subset \mathbb{N}$ is a primitive set if no number in the set divides another one) and I thought about the following statement that I believed to be true:

Given a set $S\subset \mathbb N$ let $P(S)=\{p\in\mathbb P:\;\exists a\in S\;\;\text{such that}\;\;p\mid a\}$ (with $\mathbb P$ the set of prime numbers). The claim is that given a primitive set $S$ such that $P(S)$ is finite, then $S$ is finite. The thing is that I could only give a proof for this if $P(S)=2$, I'll put my proof below (it isn't really elegant or anything though), but I couldn't generalize it for bigger cases (not even if $P(S)=3$); so I'd really appreciate if someone notices how to generalize it, or if you have a proof for bigger cases.

My proof:

The idea is to suppose that $S\subset \mathbb N$ is an infinite set such that $P(S)$ has two elements, and prove that $S$ can't be a primitive set. Let $P(S)=\{p,q\}$, then we can describe $S$ as follows $S=\{p^\alpha q^\beta:\;(\alpha,\beta)\in I\}$ for some $I\subset \mathbb N^2$ (notice that there is a trivial one-to-one correspondence between $S$ and $I$, so I might use alternatingly $p^\alpha q^\beta$ and $(\alpha, \beta)$).

Let $\alpha_0=\min\{\alpha\in \mathbb N/\;\exists \beta\in \mathbb N:\;(\alpha,\beta)\in S\}$, and $\beta_0$ be such that $(\alpha_0,\beta_0)\in S$, and consider $S'=S\setminus\{(\alpha_0, \beta_0)\}$.

Now, given $(\alpha,\beta)\in S'$, if $\beta\geq \beta_0$, the problem is finished since we know that $\alpha\geq \alpha_0$, and then we'd have that $p^{\alpha_0}q^{\beta_0}\mid p^\alpha q^\beta$, and then $S$ isn't primitive; so, by way of contradiction let us assume that for all $(\alpha, \beta)\in S'$ we have that $\beta<\beta_0$.

Lemma: given $N\in \mathbb N$ there exists $\alpha>N$ and $\beta\in\mathbb N$ such that $(\alpha,\beta)\in S'$. Let's assume that there is an $N\in \mathbb N$ such that the statement isn't true, then, given $(\alpha, \beta)\in S'$ we have that $\alpha_0\leq\alpha\leq N$ and $0\leq \beta<\beta_0$, and this implies that $\#S'\leq (N+1)\beta_0$, which is absurd since the set is infinite, so the lemma is true.

Going back to what we are trying to prove, let $\beta_1=\min\{\beta\in\mathbb N/\;\exists\alpha:\;(\alpha, \beta)\in S'\}$ and let $\alpha_1$ be such that $(\alpha_1,\beta_1)\in S$. Then by the lemma there exists $\alpha>\alpha_1$ and $\beta\in\mathbb N$ such that $(\alpha,\beta)\in S'$. Lastly, as $\alpha>\alpha_1$ and $\beta\geq \beta_1$ we have that $p^{\alpha_1}q^{\beta_1}\mid p^\alpha q^\beta$, which proves that $S'$ isn't primitive, and therefore $S$ neither.

  • 1
    $\begingroup$ In your definition of $P(S)$, what is $\mathbb P$? Is that the set of prime numbers? $\endgroup$
    – John Douma
    Aug 25, 2022 at 18:17
  • 1
    $\begingroup$ Yes, I mean the prime numbers $\endgroup$ Aug 25, 2022 at 18:18

1 Answer 1


Note that what you want follows from showing that for $A\subset \mathbb{N}^k$, with the latter ordered by the product order can only have a finite set of minimal elements. The set of exponents of your $S$, for $S$ to be primitive, would have to be such a subset in which all elements are minimal.

You can do this by induction on $k$.

Let $p:\mathbb{N}^k\to\mathbb{N}^{k-1}$ be the projection onto the first $k-1$ coordinates, and $p_k:\mathbb{N}^k\to\mathbb{N}$ the projection onto the last component.

For $k=1$, the well-order of $\mathbb{N}$ gives one minimal elements, or no minimal if $A$ is empty.

Assume the statement is true for $k-1$. By induction, $p(A)$ has finitely many minimal elements $a_1,a_2,...,a_r$. Note that we cannot have two minimal elements $x,y$ of $A$ projecting to the same $a_i$, since one of them would have the $k$-th component larger than the other and wouldn't be minimal.

Let $n$ be the maximum of $\{p_k(p^{-1}(a_i))\}$, the $k$-th components of the original minimal elements of $A$ that project onto the $a_1,a_2,...,a_r$. Since this is a maximum of a finite set of natural numbers, it exists.

Let $B_s\subset \mathbb{N}^k$ be the set of elements of $A$ with $k$-th component $s=1,2,...,n$. The sets of minimal elements of each $B_s$ is finite, by induction applied to $p(B_s)$. Their union contains the minimal elements of $A$. In fact, if $a\in A$ is minimal, and $p_k(a)>n$, then we would need $p(a)$ to be among the $a_1,a_2,...,a_r$. Otherwise, there is $a_i\leq p(a)$ and since also $p_k(p^{-1}(a_i))<p_k(a)$, then $p^{-1}(a_i)\leq a$, contradicting that $a$ is minimal.

Compare the structure of this proof with some proofs of Hilbert basis theorem. It is the same idea.

  • $\begingroup$ I'll have to give a second read to your proof, but I liked what I understood, I just gotta read more carefully the last parts. One question though, in the second to last sentence when it says $p_k(a)>p_k(a_i)$, didn't you really mean $p_k(a)>p_k(p^{-1}(a_i))$, I ask since $a_i$ belongs to $\mathbb N ^{k-1}$, and it wouldn't make sense what is in there in terms of domain I believe. Btw, I don't really have any ideas about the Hilbert basis theorem because I haven't taken algebra courses hehe, next year I have Groups and Galois Theory, and Ring and Modules, two subjects in my university. $\endgroup$ Aug 25, 2022 at 20:32
  • 1
    $\begingroup$ @MarianoRodriguez Yes, $p_k(p^{-1}(a_i))$, abusing the notation by thinking of the set $p^{-1}(a_i)$ as the single element that it contains. $\endgroup$
    – plop
    Aug 25, 2022 at 20:42
  • $\begingroup$ Okay, thank you!! I never would have thought of the problem this way $\endgroup$ Aug 25, 2022 at 20:53
  • $\begingroup$ one more question, perhaps I misunderstood the proof, but does it imply that if $p(A)$ has $r$ minimal elements, then $A$ has the same amount? $\endgroup$ Aug 25, 2022 at 22:28
  • $\begingroup$ @MarianoRodriguez No. For example $A=\{(1,2),(4,1)\}\subset\mathbb{N}^2$. The projection to the first coordinate is $\{1,4\}$ that has only $1$ as minimal(minimum). But $A$ has two. What we can say is that all minimal elements of $A$ have second coordinate $\leq2$, which is the second coordinate of the minimal element $(1,2)$ that projected onto $1$. $\endgroup$
    – plop
    Aug 25, 2022 at 23:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .