can we describe every integer $\gt 1$ using only prime numbers, but not in the way you expect?

Question

for $a,b \in \mathbb{N}^+$, define: $$ a \circ b = a^b $$ and for any positive integer $n$ define its quadratfrei radical $n^{\sqrt{}}$ (the product of all distinct primes dividing n) by $$ n^{\sqrt{}}= max \{k \in \mathbb{N}^+ \mid (k \mid n) \land (\forall j \lt k, \; j^2 \not \mid k \} $$ we note that: $$ a^{\sqrt{}} = (a \circ b)^{\sqrt{}} $$

let $\mathfrak{P}$ denote the set of primes of $\mathbb{N}$ and define the set of numbers $P$ by the following three rules.

(a) $\mathfrak{P} \subset P$

(b) if $\mathfrak{p} \in \mathfrak{P}$ and $b \in P$ then $\mathfrak{p} \circ b \in P$

(c) if $a,b \in P$ and $(ab)^{\sqrt{}}=a^{\sqrt{}}b^{\sqrt{}}$ then $ab\in P$

the purport of the condition in rule (c) is to require that $a^{\sqrt{}}$ and $b^{\sqrt{}}$ have no prime factor in common.

am i correct in asserting that $P=\mathbb{N}^+ \setminus \{1\}$, and that the formation rules produce a unique representation of every integer $\gt 1$, which uses only prime numbers?

Answer 1

Pick any $n$. By the usual version of the fundamental theorem of arithmetic, there exist distinct primes $a_1, a_2, \ldots, a_r$ and corresponding exponents $b_1, b_2, \ldots, b_r$, so that

$$n=a_1^{b_1} a_2^{b_2} a_3^{b_3} \dots a_r^{b_r}$$

Now, all the $a_i$ are already primes, while some of the $b_i$ may be prime, some may be composite, and some may be $1$. Leave the primes $b_i$ as they stand. Substitute the composite $b_i$ with their expansions by the fundamental theorem. Erase the ones. As an example this could give

$$n=a_1^{b_1} a_2^{c_{21}^{d_{21}} c_{22}^{d_{22}} c_{23}^{d_{23}} \dots c_{2q}^{d_{2q}}} a_3 \dots a_r^{c_{r1}^{d_{r1}} c_{r2}^{d_{r2}} c_{r3}^{d_{r3}} \dots c_{rp}^{d_{rp}}}$$

Now all the remaining $b_i$ are prime, and all the $c_{ij}$ are prime. But some $d_{ij}$ may be composite, and we substitute them, and so on.

It is clear that this process will end, because each component (each prime and each exponent) in the expansion of a composite number is less than that composite number itself.

So eventually we reach in this way a "representation" where all numbers in all "superscript levels" are primes. Was this the representation you wanted to describe?

Answer 2

as one step towards a formal proof of the assertion in my question it seems that we may represent the process of generating $P = \cup_{n<\omega}\; P_n$, as follows:

set $$P_0=\mathfrak{P} $$ and for $n \ge 0$ $$P_{2n+1} = P_{2n} \cup \bigcup_{X = Im{\psi}, \psi \in P_{2n}^{\omega,\sqrt{}}}\left(\prod_{p \in X} p \right)\\ $$ [where $P_{2n}^{\omega,\sqrt{}}$ denotes all the injective maps from a finite ordinal domain into $P_{2n}$, such that any two elements of the image satisfy the condition in rule (c)] and $$ P_{2n+2} = P_{2n+1} \cup \bigcup_{\mathfrak{p} \in \mathfrak{P},a \in P_{2n+1}} p \circ a $$

Answer 3

Here's a shot at a proof. Either I'm missing something or it's fairly simple.

Added: This isn't a proof of what David meant (but didn't precisely say in the question), since as David points out, it uses what rule b) is supposed to say incorrectly. To give an example: For $k=4$, $k^{\sqrt{}} \not \in \mathfrak{P}$. The incorrect argument below would have claimed $7^4\in P$ by writing $4=2\cdot2$, then using rule b) twice. First, $7^2\in P$, which is a correct application, then to say $(7^2)^2\in P$, which is an incorrect application of b), which only allows the base to be a prime (not an arbitrary element of $P$).

While $7^4$ is in $P$, the reason I gave was wrong. It requires first showing that $4\in P$ and working "from the top down", not "from the bottom up" of the power of exponents. I don't see a quick way to show this can be done in general.

Invalid proof:

First, show that $p^k$ will be in $P$ for any prime $p$ and positive integer $k$. Suppose $k$ factors into $r$-many primes as $k=q_1\cdots q_r$. Then $\displaystyle p^k=\left(\cdots\left({(p^{q_1})}^{q_2}\right)\dots \right)^{q_r}$ is in $P$ by repeated applications of rule b).

Every integer $n$ is a product of powers of distinct primes, each of which is now known to be in $P$. Using that decomposition of any $n\in\mathbb{Z}^+$, rule c) will guarantee that $n\in P$.

Answer 4

Here's a spin at an inductive proof:

Let $n$ be a natural number. Then we have two distinct cases:

1. $n\in\mathfrak{P}$. Then $n\in P$ by definition.
2. $n\not\in\mathfrak{P}$. Then $n$ has a prime factorization: $n=p_1^{n_1}p_2^{n_2}\ldots$, with $n_i\lt n$ and $p_i\lt n$ for all $i$. By the induction hypothesis, $n_i\in P$, and $p_i\in \mathfrak{P}$, so we can write $n=(p_1\circ n_1)\cdot(p_2\circ n_2)\cdot\ldots\cdot(p_i\circ n_i)$. By the induction hypothesis, all of the $n_i$ are in $P$, and we know that $\mathop{GCD}(p_i, p_j)=1$ for all $i,j$, so $n\in P$.