I was trying to get a better understanding of exponentials in lattices, and how to compute them. I started investigating a particular lattice, and came to a seeming contradiction.
We can construct a lattice on the natural numbers $\mathbb{N}$ = $\{0, 1, 2, ...\}$ where the ordering relation $\le$ is divisibility. Herein I will write $a\ |\ b$ to say that $a$ divides $b$. More specifically that means that $\forall a, b \in \mathbb{N} . a\ |\ b\ \mathrm{iff}\ \exists m \in \mathbb{N}. a \cdot m = b$.
The least element $\bot$ is $1$, because for all $a$, $1\ |\ a$. The greatest element $\top$ is $0$, because for all $a$, $a\ |\ 0$. It is slightly odd to think of $0$ as greater than the other integers, but remember this is with respect to divisibility, not the usual ordering on natural numbers.
The meet $a \wedge b$ is $\mathrm{gcd}(a, b)$, and the identity is $0$. We can see that $a \wedge 1 = 1$ for any $a$. The join $a \vee b$ is $\mathrm{lcm}(a, b)$, and the identity is $1$. Also $a \vee 0 = 0$ for any $a$.
It's a well-known result that gcd and lcm distribute over each other, e.g. $\mathrm{gcd}(a, \mathrm{lcm}(b, c)) = \mathrm{lcm}(\mathrm{gcd}(a, b), \mathrm{gcd}(b, c))$. This can be proven by factoring the numbers into prime factors with exponents, such that gcd maps to max and lcm maps to min, then using the fact that max distributes over min. I believe this can be extended to work when $a$, $b$, or $c$ can be $0$, by coding an extra factor of $0^0$ or $0^1$ into each factorization. Note this obeys the expected property that $0^0\ |\ 0^1$ because $1\ |\ 0$.
Since we have a bounded, distributive lattice, we have a Heyting algebra. Every Heyting algebra has exponentials (a.k.a. implication). That is, for all $a$ and $b$, there exists a greatest $x$ such that $a \wedge x \le b$, and we call that value $a \Rightarrow b$. This has nifty properties such as $(a \wedge (a \Rightarrow b)) \le b$. We also have the identity $c \wedge a \le b$ iff $c \le a \Rightarrow b$.
So, how would we calculate the exponential, given two natural numbers $a$ and $b$? Let's take $a = 6$ and $b = 20$. We want to find the greatest value $x$ such that $\mathrm{gcd}(6, x)\ |\ 20$. Let's try some values for $x$:
- $\mathrm{gcd}(6, 0) = 6$ does not divide $20$.
- $\mathrm{gcd}(6, 1) = 1$ divides $20$.
- $\mathrm{gcd}(6, 2) = 2$ divides $20$.
- $\mathrm{gcd}(6, 3) = 3$ does not divide $20$.
- $\mathrm{gcd}(6, 4) = 2$ divides $20$.
- $\mathrm{gcd}(6, 5) = 1$ divides $20$.
- $\mathrm{gcd}(6, 6) = 6$ does not divide $20$.
- $\mathrm{gcd}(6, 7) = 1$ divides $20$.
We can continue this pattern, and we will find that there are arbitrarily large values for $x$ that satisfy the equation. (E.g., any power of two.) Note that although $0$ is the largest value, it does not satisfy the equation.
Thus it seems we are stuck --- we cannot find a largest $x$ that satisfies the equation. This seems to be a contradiction. Heyting algebras are supposed to have exponentials, yet we cannot find the exponential.
What am I doing wrong?
It is simply not true that a bounded distributive lattice is a Heyting algebra. In a Heyting algebra with any infinite joins, meets must distribute over all infinite joins that exist. That's not true here and it's what makes everything not work.
More specifically, observe that
$$\gcd(6, \text{lcm}(2, 5, 7, 11, \dots)) = \gcd(6, 0) = 6$$
where the lcm ranges over all primes not equal to $3$, but
$$\text{lcm}(\gcd(6, 2), \gcd(6, 5), \dots) = 2.$$
Here is a positive result, though:
This is an application of the "adjoint functor theorem for posets," and explicitly it goes like this: the exponential $a \Rightarrow b$ is given by the join / supremum of all $c$ such that $a \wedge c \le b$. You need meets to distribute over infinite joins in order for this element to itself satisfy $a \wedge c \le b$, and that's what goes wrong here: the lcm of all $x$ such that $\gcd(6, x) | 20$ is $0$.
There is a lattice which can be regarded as a completion of $\mathbb{N}$ under divisibility, in some sense, which is a Heyting algebra, though. It's the lattice of supernatural numbers, which you can think of as numbers having a prime factorization which may have infinitely many nonzero exponents, and where the exponents may be infinite. ($0$ is not an element.) Another way of describing this lattice is as the product of infinitely many copies of $\mathbb{N} \cup \{ \infty \}$ under the usual ordering.
In this lattice I invite you to compute that $6 \Rightarrow 20$ is equal to $2^{\infty} 3^0 5^{\infty} 7^{\infty} \dots$.