# Statement about primitive sets

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.

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

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)), 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.

• 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. Aug 25, 2022 at 20:32
• @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.
– plop
Aug 25, 2022 at 20:42
• Okay, thank you!! I never would have thought of the problem this way Aug 25, 2022 at 20:53
• 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? Aug 25, 2022 at 22:28
• @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$.
– plop
Aug 25, 2022 at 23:32