I wonder what this stunning formal analogy between the definitions of being co-prime (for two integers) and being prime (for one integer) might reveal – and how:

$\alpha, \beta$ are co-prime iff

$$(\forall x)\ \alpha|x \wedge \beta|x \leftrightarrow \alpha\beta|x$$

$\alpha$ is prime iff

$$(\forall xy)\ \alpha|x \vee \alpha|y \leftrightarrow \alpha|xy$$

Note that and how the two definitions are equivalent modulo swapping

  • $\wedge$ and $\vee$ on the left side

  • constants and variables on the right side together with

  • the direction of divisibility $|$ with respect to the product [thanks to user Wojowu]

  • the direction of inference $\rightarrow$ [thanks to user Roll up and smoke Adjoint]

  • 1
    $\begingroup$ Note you also swap the direction of divisibility. This is an interesting observation, but I don't think there is any "stunning" meaning behind it. $\endgroup$ – Wojowu Nov 2 '18 at 19:28
  • $\begingroup$ Note that you can also replace $\rightarrow$ with $\leftrightarrow$ since each of those propositions on either side are in isomorphism with one another. $\endgroup$ – BananaCats Category Theory App Nov 3 '18 at 3:29
  • $\begingroup$ There is most likely a nice interpretation in the language of lattices/filters. $\endgroup$ – Slade Nov 3 '18 at 9:05
  • $\begingroup$ In the poset category for integers dividing one another $\text{Hom}(X,Y)$ consists of a single point or is empty. Let $(X \mid Y)$ denote the nonempty hom-set. Notice that multiplication by an element $\alpha \in \Bbb{Z}$ is a functor from the poset category to itself since $(X \mid Y) \implies (\alpha X \mid \alpha Y)$ and so on proves the functoriality of multiplication. $\endgroup$ – BananaCats Category Theory App Nov 4 '18 at 6:34

In the poset category of integers dividing one another we write sometimes write $\alpha \to x$ instead of $\alpha \mid x$.

The "product" $\alpha \beta$ of two coprime objects $\alpha, \beta$ is such that $\alpha \to \alpha \beta \leftarrow \beta$ and for any object $x$ such that $\alpha \to x \leftarrow \beta$ then there is a unique arrow $\alpha \beta \to x$. That is precisely the definition of coproduct in a general category.

Thus when $\alpha, \beta$ are coprime, then the category definitely has a coproduct for them.

Thus $\wedge$ is encoded in the fact that $\alpha \to x \leftarrow \beta$, ie. both morphisms exist simultaneously. I believe product is $\gcd(\alpha, \beta)$.

Actually, it turns out that the coproduct exists for any two integers and it's $\text{lcm}(\alpha, \beta)$.

Primality is difficult because of the $\vee$. So create a new definition. An arrow into a coproduct is prime when there exists a morphism into at least one of the coproduct's components such tha the relevant triangle commutes.

Notice we used coproduct here which is $\text{lcm}(\alpha, \beta)$ since the definition of prime is equivalent to $p \mid \text{lcm}(\alpha, \beta) \implies p \mid \alpha \vee p \mid \beta$.

So take the contrapositive of that. $p \nmid \alpha \wedge p \nmid \beta \implies p \nmid \text{lcm}(\alpha, \beta)$.

Form the "negated" poset category of integers not dividing one another. It's formed by mapping each hom-set to $\varnothing$ when it's nonempty and vise-versa, so it's not a functor from the original category.


The second can become:$$(\forall xy)\alpha\mid xy\to\alpha\mid x\lor\alpha\mid y$$ The first is: $$(\forall x)\alpha\beta\nmid x \to \alpha\nmid x \lor \beta\nmid x \lor \alpha\beta \gt x\lor(\alpha,\beta)^2\nmid x$$ Not sure it reveals much though.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.