3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It's simply not true that a bounded distributive lattice is a Heyting algebra. I'll write an answer with more details. $\endgroup$ – Qiaochu Yuan Sep 20 '17 at 6:08
  • $\begingroup$ One small thing you're getting wrong is "largest": it needs to be largest in the sense of the poset, not in the sense of the natural ordering on $\mathbb{N}$. $\endgroup$ – Patrick Stevens Sep 20 '17 at 6:19
  • $\begingroup$ Patrick - I think I took care to handle the usage of "largest" correctly. If there is a place where I used the wrong meaning, please point it out. Perhaps the section where I list the gcds as bullet points is a bit misleading, as though each number 0, 1, 2, 3, 4, is smaller than the next. It's a poset - there aren't orderings between each pair of numbers, but I had to list them in some order. I used "any power of two" as an example of "arbitrarily large" because each number 1, 2, 4, 8, etc. divides the next, so they are increasing in poset order. $\endgroup$ – LyleK Sep 21 '17 at 4:31
1
$\begingroup$

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:

Theorem: Any complete distributive lattice where meets distribute over infinite joins is a Heyting algebra.

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$.

$\endgroup$
  • $\begingroup$ Thank you, that's a very helpful answer! Somehow I got the idea from a lecture I was watching that a bounded lattice is distributed iff it has exponentials. But since you pointed out that only the forward implication is true, I haven't been able to find any definition which states that the reverse implication is true. Perhaps what threw me off is that a complemented distributive lattice (i.e. a Boolean algebra) always has exponentials. $\endgroup$ – LyleK Sep 21 '17 at 4:42
  • $\begingroup$ I also appreciate the positive theorem you provided, and the adjoint functor theorem for posets, which is helpful in calculating the exponential. And I appreciate the example of the lattice of supernatural numbers. I'll give that a try. $\endgroup$ – LyleK Sep 21 '17 at 4:45
  • $\begingroup$ I will say that I'm not totally convinced that $\mathrm{lcm}(2, 5, 7, 11, \ldots) = 0$ in my originally proposed lattice. It makes some sense because $0$ is the only multiple of all of those numbers. But if you construct a series $\mathrm{lcm}(2, 5) = 10$, $\mathrm{lcm}(2, 5, 7) = 70$, etc., it does not converge to $0$, which makes it unsatisfying. I would prefer instead to say the infinite lcm is not defined. $\endgroup$ – LyleK Sep 21 '17 at 4:51
  • $\begingroup$ I think that's valid to say the infinite join is simply not defined, and that means we don't have a complete lattice. A lattice doesn't have to be complete to be a Heyting algebra. So I thought at first you were being too particular in insisting that it be complete. Until I realized that was beside the point. My lattice doesn't have exponentials, as I proved by counterexample, so it's not a Heyting algebra. You were pointing out that, in a complete lattice, you can start with the fact that it's distributive and derive that it has exponentials, for the right kind of distributivity. $\endgroup$ – LyleK Sep 21 '17 at 4:54
  • $\begingroup$ @LyleK: your lattice is definitely a complete lattice. One way to see this is to identify it with the lattice of ideals of the integers, where gcd / meet corresponds to ideal sum and lcm / join corresponds to intersection. "Convergence" is irrelevant, and the infinite lcm is absolutely defined; this isn't a matter of convention, the infinite lcm either exists or it doesn't. $\endgroup$ – Qiaochu Yuan Sep 21 '17 at 5:45

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.