Martin Escardo 23rd Feb 2026. A result by David Wärn [1].

Any type equipped with a binary operation _*_ that is associative,
commutative and idempotent is a set (homotopy 0-type). That is, there
are no higher semilattices! This file is my attempt to understand
David's Agda file [1].

[1] David Wärn. https://dwarn.se/agda/Idem.html , 17 February 2026.
    (See also https://mathstodon.xyz/deck/@dwarn/116091515645003634)

I add, in the discussion of the formal definitions and proofs, some
diagrams and some explanations, and rename some things, which I hope
are correct and what David intended.

Proof sketch (formalized in the anonymous module at the very end of
this file). Fix a type A and an x₀ : A, and write ΩA = (x₀ = x₀). An
operation _*_ on A induces an operation _⋆_ on ΩA.  The main steps
are, for suitably defined act-l and act-r,

  (i)   p ⋆ p = p                             (⋆-idemp)
  (ii)  p ⋆ q = act-l p ∙ act-r q             (⋆-in-terms-of-∙)
  (iii) p ⋆ q = q ⋆ p                         (comm-loop)
  (iv)  act-l p = act-r p                     (only-one-act)
  (v)   act-l p ∙ act-l p = p                 (act-l-idemp)
  (vi)  act-l p ∙ act-l q = act-l q ∙ act-l p (comm-l)

An Eckmann–Hilton argument using (v) and (vi) gives the following:

  (vii) p ∙ q = q ∙ p                         (loop-comm)

Finally, using the associativity of *, we get that

  (viii) act-l (act-l p) = act-l p            (act-l-idem)
  (ix)   act-l p = refl                       (act-l-trivial)
  (x)    p = refl                             (Ω-null)

In the spirit of the original file [1], we make this file
self-contained, without importing any TypeTopology file, to show that
a relatively short argument in a rather Spartan MLTT is possible - we
only need Π-types and identity types. (We also don't use universe
polymorphism.)

\begin{code}

{-# OPTIONS --safe --without-K #-}

module gist.ThereAreNoHigherSemilattices where

\end{code}

What Agda calls sets is what we call types.

\begin{code}

open import Agda.Primitive renaming (Set to Type)

\end{code}

Basic path combinators.

\begin{code}

infix 15 _=_

data _=_ {A : Type} (a : A) : A  Type where
 refl : a  a

ap : {A B : Type} {a b : A} (f : A  B)  a  b  f a  f b
ap f refl = refl

infixr 20 _∙_

_∙_ : {A : Type} {a b c : A}  a  b  b  c  a  c
refl  refl = refl

sym : {A : Type} {a b : A}  a  b  b  a
sym refl = refl

ap₂ : {A B C : Type} (f : A  B  C) {a₁ a₂ : A} {b₁ b₂ : B}
     a₁  a₂
     b₁  b₂
     f a₁ b₁  f a₂ b₂
ap₂ f refl refl = refl

∙refl : {A : Type} {a b : A} (p : a  b)  p  refl  p
∙refl refl = refl

refl∙ : {A : Type} {a b : A} (p : a  b)  refl  p  p
refl∙ refl = refl

\end{code}

We now define a notion of equality (or path) congruence.

`eq-congr h₁ h₂ p` transports a path p : a = b across a commutative
square to obtain a path x = y:

    a ═════ p ════ b
    ║              ║
   h₁              h₂
    ║              ║
    x ════════════ y
           ?

The resulting path is sym h₁ ∙ p ∙ h₂.  Definitionally, when
h₁ = h₂ = refl, the square degenerates and we recover p.

\begin{code}

eq-congr : {A : Type} {a b x y : A}  a  x  b  y  a  b  x  y
eq-congr refl refl p = p

\end{code}

When h = refl the square collapses to a point and the loop is unchanged:

    a ═══ p ══ a
    ║          ║
    h          h    ↝   a ══ refl ══ a
    ║          ║
    a ════════ a

\begin{code}

eq-congr-refl : {A : Type} {a x : A} (h : a  x)  eq-congr h h refl  refl
eq-congr-refl refl = refl

\end{code}

Equality congruence distributes over path concatenation:

    a ══ p ══ b ══ q ═══ c
    ║         ║          ║
   h₁        h₂          h₃
    ║         ║          ║
    x ═══════ y ════════ z

\begin{code}

eq-congr-∙ : {A : Type} {a b c x y z : A}
             {h₁ : a  x} {h₂ : b  y} {h₃ : c  z}
             (p : a  b) (q : b  c)
            eq-congr h₁ h₃ (p  q)  eq-congr h₁ h₂ p  eq-congr h₂ h₃ q
eq-congr-∙ {h₁ = refl} {h₂ = refl} {h₃ = refl} p q = refl

\end{code}

Equality congruence is invertible.

\begin{code}

eq-congr-sym : {A : Type} {a b x y : A} {hax : a  x} {hby : b  y}
               {p : a  b} {q : x  y}
              eq-congr hax hby p  q
              p  eq-congr (sym hax) (sym hby) q
eq-congr-sym {hax = refl} {hby = refl} refl = refl

\end{code}

We now construct a square congruence identity.

Going right-then-down equals going down-then-right:

    a ══ p ══ b
    ║         ║
    q         r
    ║         ║
    x ═══════ y

\begin{code}

eq-congr-sq : {A : Type} {a b x y : A} (p : a  b) (q : a  x) (r : b  y)
             q  eq-congr q r p  p  r
eq-congr-sq refl refl refl = refl

\end{code}

We now show that equality congruence is natural.

The cleanest expression is a commutative square whose nodes are
path spaces and whose edges are "apply congruence with":

  (a = b) ══════ congruence with (ha, hb) ══════ (a = b)
     ║                                              ║
congruence with (hax, hby)                  congruence with (hax, hby)
     ║                                              ║
  (x = y) ════ congruence with (ha', hb') ══════ (x = y)

  where  ha' = eq-congr hax hax ha
         hb' = eq-congr hby hby hb.

The geometric intuition is a cube in A, where the top and bottom faces
record the ha/hb loops and their congruences ha'/hb', and the vertical
edges are hax and hby:

        a ══  ha ══ a
       ╱║           ║╲
    hax ║           ║ hax
     ╱  p           p' ╲
    x   ║           ║    x
    ║   b ══  hb ══ b    ║
    ║  ╱             ╲   ║
    ║ hby           hby  ║
    ║╱                 ╲ ║
    y ══════  hb' ══════ y

  where  p  = eq-congr hax hby p      (front face)
         p' = eq-congr hax hby        (back face)
               (eq-congr ha hb p).

Naturality says that the front face and back face of the cube give the
same path x = y.

\begin{code}

eq-congr-nat : {A : Type} {a b x y : A}
               (ha : a  a) (hb : b  b) (hax : a  x) (hby : b  y)
               (p : a  b)
              eq-congr hax hby (eq-congr ha hb p)
              eq-congr
                 (eq-congr hax hax ha)
                 (eq-congr hby hby hb)
                 (eq-congr hax hby p)
eq-congr-nat ha hb refl refl p = refl

\end{code}

Equality congruence by a composite path equals iterated congruence.

\begin{code}

congr-∙ : {A : Type} {a b u v x y : A}
          (l₁ : a  u) (l₂ : u  x) (r₁ : b  v) (r₂ : v  y) (p : a  b)
         eq-congr (l₁  l₂) (r₁  r₂) p  eq-congr l₂ r₂ (eq-congr l₁ r₁ p)
congr-∙ refl refl refl refl p = refl

\end{code}

Left-cancellation of path concatenation.

\begin{code}

∙-cancel : {A : Type} {a b c : A} (p : a  b) (q₁ q₂ : b  c)
          p  q₁  p  q₂  q₁  q₂
∙-cancel refl q₁ q₂ h = eq-congr (refl∙ q₁) (refl∙ q₂) h

\end{code}

The standard Eckmann–Hilton argument shows that two binary operations
on a set that share a unit and interchange with each other must
coincide and be commutative. Here we only need one piece of that
argument: if loops p and q commute, then p ∙ p and q ∙ q also commute.

The key calculation rearranges a 2×2 grid of tiles:

  ┌──────┬──────┐     ┌──────┬──────┐
  │  p   │  p   │     │  q   │  q   │
  ├──────┼──────┤  ↝  ├──────┼──────┤
  │  q   │  q   │     │  p   │  p   │
  └──────┴──────┘     └──────┴──────┘

  p∙p∙q∙q = p∙(p∙q)∙q = p∙(q∙p)∙q = (p∙q)∙(p∙q)
          = (q∙p)∙(q∙p) = q∙(p∙q)∙p = q∙(q∙p)∙p = q∙q∙p∙p.

The function assoc₄ handles the repeated reassociation steps.

\begin{code}

assoc₄ : {A : Type} {a b c d e : A}
         {p : a  b} {q : b  c} {r : c  d} {s : d  e}
        (p  q)  (r  s)  p  (q  r)  s
assoc₄ {p = refl} {q = refl} {r = refl} {s = refl} = refl

comm₂ : {A : Type} {a : A} {p q : a  a} (h : p  q  q  p)
       (p  p)  (q  q)  (q  q)  (p  p)
comm₂ {p = p} {q = q} h =
 eq-congr
  (sym assoc₄)
  (sym assoc₄)
  (eq-congr
    (ap  x  p  x  q) (sym h))
    (ap  x  q  x  p) h)
    (eq-congr assoc₄ assoc₄ (ap  x  x  x) h)))

\end{code}

We now come to the main theorem.

We fix a type A with an associative, commutative, idempotent
operation, and a base-point x₀.

\begin{code}

module _
         (A     : Type)
         (_*_   : A  A  A)
         (idem  : (a : A)  a * a  a)
         (comm  : (a b : A)  a * b  b * a)
         (assoc : (a b c : A)  (a * b) * c  a * (b * c))
         (x₀    : A)
       where

  ΩA : Type
  ΩA = x₀  x₀

\end{code}

The operation * acts on paths componentwise:

    a₁ ══ p ══ a₂       b₁ ══ q ══ b₂

                                         ↝   a₁*b₁ ══ p ★ q ══ a₂*b₂.

It also splits into a left part followed by a right part:

    a₁*b₁ ══ ap (-*b₁) p ══ a₂*b₁ ══ ap (a₂*-) q ══ a₂*b₂.

\begin{code}

  _★_ : {a₁ a₂ b₁ b₂ : A}  a₁  a₂  b₁  b₂  a₁ * b₁  a₂ * b₂
  _★_ = ap₂ _*_

  ★-in-terms-of-∙ : {a₁ a₂ b₁ b₂ : A} (p : a₁  a₂) (q : b₁  b₂)
                   p  q  ap (_* b₁) p  ap (a₂ *_) q
  ★-in-terms-of-∙ refl refl = refl

\end{code}

The function `reduce` uses idempotence to turn a loop at x₀ * x₀ into
a loop at x₀:

       idem x₀
   x₀ ════════ x₀*x₀
   ║             ║
   ║             ║
   ║             ║
   x₀ ════════ x₀*x₀
       idem x₀

\begin{code}

  reduce : x₀ * x₀  x₀ * x₀  ΩA
  reduce = eq-congr (idem x₀) (idem x₀)

\end{code}

Given loops p, q : x₀ = x₀, we form the loop at x₀*x₀ via _★_, then
reduce it:

    x₀*x₀ ══════ p ★ q ══════ x₀*x₀
      ║                         ║
    idem x₀                   idem x₀
      ║                         ║
     x₀ ═══════════════════════ x₀
                 p ⋆ q

It splits as act-l p ∙ act-r q:

    x₀*x₀ ═ ap(-*x₀) p ═ x₀*x₀ ═ ap(x₀*-) q ═══ x₀*x₀
      ║                    ║                      ║
    idem x₀              idem x₀                idem x₀
      ║                    ║                      ║
     x₀ ═════ act-l p ════ x₀ ═════ act-r q ═════ x₀

With this we have that _★_ induces an operation _⋆_ on loops.

\begin{code}

  _⋆_ : ΩA  ΩA  ΩA
  p  q = reduce (p  q)

  act-l : ΩA  ΩA
  act-l p = reduce (ap (_* x₀) p)

  act-r : ΩA  ΩA
  act-r q = reduce (ap (x₀ *_) q)

  ⋆-in-terms-of-∙ : (p q : ΩA)  p  q  act-l p  act-r q
  ⋆-in-terms-of-∙ p q =
   ap reduce (★-in-terms-of-∙ _ _)
    eq-congr-∙ (ap (_* x₀) p) (ap (x₀ *_) q)

\end{code}

We now show that _⋆_ is idempotent.

When both arguments are equal, p ★ p reduces to p via the idempotence
of *, for any p : a = b:

    a*a ══════ p ★ p ═════ b*b
     ║                      ║
   idem a                 idem b
     ║                      ║
     a ═════════ p ════════ b

\begin{code}

  ★-idemp : {a b : A} (p : a  b)
           eq-congr (idem a) (idem b) (p  p)  p
  ★-idemp refl = eq-congr-refl (idem _)

  ⋆-idemp : (p : ΩA)  p  p  p
  ⋆-idemp = ★-idemp

\end{code}

Next, we show that _⋆_ is commutative.

We use the commutativity of * as a base-point-preserving loop
comm-self : x₀ = x₀, and show that equality congruence by it swaps _⋆_.

comm-loop-raw builds the following stacked rectangle:

    x₀*x₀ ═══ p ★ q ════ x₀*x₀       (top, before reduce)
      ║                    ║
    comm x₀ x₀           comm x₀ x₀  (side paths via commutativity)
      ║                    ║
    x₀*x₀ ═══ q ★ p ════ x₀*x₀       (comm-paths flips the args)
      ║                    ║
    idem x₀              idem x₀
      ║                    ║
     x₀ ═════ q ⋆ p ══════ x₀

Stacking the rectangles gives

  eq-congr comm-self comm-self (p ⋆ q) = q ⋆ p.

The function comm-self-center then shows that comm-self is central
(equality congruence with it is the identity), by specializing to p = q
and using ⋆-idemp.

\begin{code}

  comm-paths : {a b x y : A} (p : a  x) (q : b  y)
              eq-congr (comm a b) (comm x y) (p  q)  q  p
  comm-paths refl refl = eq-congr-refl _

  comm-self : ΩA
  comm-self = reduce (comm x₀ x₀)

  comm-loop-raw : (p q : ΩA)
                 eq-congr comm-self comm-self (p  q)  q  p
  comm-loop-raw p q =
    eq-congr
     (eq-congr-nat (comm x₀ x₀) (comm x₀ x₀) (idem x₀) (idem x₀) (p  q))
     refl
     (ap reduce (comm-paths p q))

  comm-self-center : (p : ΩA)  eq-congr comm-self comm-self p  p
  comm-self-center p =
   eq-congr
    (ap (eq-congr comm-self comm-self) (⋆-idemp p))
    (⋆-idemp p)
    (comm-loop-raw p p)

  comm-loop : (p q : ΩA)  p  q  q  p
  comm-loop p q = eq-congr (comm-self-center _) refl (comm-loop-raw p q)

\end{code}

The function `act-swap` defined below follows from comm-loop via the
splitting ⋆-in-terms-of-∙:

  act-l p ∙ act-r q
    = p ⋆ q              (by ⋆-in-terms-of-∙)
    = q ⋆ p              (by comm-loop)
    = act-l q ∙ act-r p

To deduce act-l = act-r, we specialize to q = refl:

  act-l p ∙ act-r refl = act-l refl ∙ act-r p
      act-l p ∙ refl  = refl ∙ act-r p
            act-l p  = act-r p

\begin{code}

  act-swap : (p q : ΩA)  act-l p  act-r q  act-l q  act-r p
  act-swap p q = eq-congr
                  (⋆-in-terms-of-∙ p q)
                  (⋆-in-terms-of-∙ q p)
                  (comm-loop p q)

  act-l-refl : act-l refl  refl
  act-l-refl = eq-congr-refl _

  act-r-refl : act-r refl  refl
  act-r-refl = eq-congr-refl _

  only-one-act : (p : ΩA)  act-l p  act-r p
  only-one-act p = eq-congr
                    (ap (act-l p ∙_) act-r-refl  ∙refl _)
                    (ap (_∙ act-r p) act-l-refl  refl∙ _)
                    (act-swap p refl)

\end{code}

Using an Eckmann–Hilton argument, we show that loop concatenation is
commutative.

We now know

  (v)  act-l p ∙ act-l p = p                  (using act-l = act-r)
  (vi) act-l p ∙ act-l q = act-l q ∙ act-l p  (comm-l, using act-swap)

Then

  p ∙ q
   = (act-l p ∙ act-l p) ∙ (act-l q ∙ act-l q) (by act-l-idemp twice)
   = (act-l q ∙ act-l q) ∙ (act-l p ∙ act-l p) (by comm₂, using comm-l)
   = q ∙ p

\begin{code}

  act-l-idemp : (p : ΩA)  act-l p  act-l p  p
  act-l-idemp p =
   ap (act-l p ∙_) (only-one-act p)
    eq-congr (⋆-in-terms-of-∙ p p) refl (⋆-idemp p)

  comm-l : (p q : ΩA)  act-l p  act-l q  act-l q  act-l p
  comm-l p q =
   eq-congr
    (ap (act-l p ∙_) (sym (only-one-act q)))
    (ap (act-l q ∙_) (sym (only-one-act p)))
    (act-swap p q)

  loop-comm : (p q : ΩA)  p  q  q  p
  loop-comm p q =
   eq-congr
    (ap₂ _∙_ (act-l-idemp p) (act-l-idemp q))
    (ap₂ _∙_ (act-l-idemp q) (act-l-idemp p))
    (comm₂ (comm-l p q))

\end{code}

We now show that _⋆_ is associative.

The function assoc-paths defined below says that * acts functorially
on 2×1 grids of paths:

    (a*b)*c ══ (p ★ q) ★ r ══ (x*y)*z
        ║                         ║
   assoc a b c               assoc x y z
        ║                         ║
    a*(b*c) ══ p ★ (q ★ r) ══ x*(y*z)

We compare two reductions of the triple self-product x₀*x₀*x₀, one
for each parenthesization:

    (x₀*x₀)*x₀ ══ idem-triple-l ══ x₀
    x₀*(x₀*x₀) ══ idem-triple-r ══ x₀

The function path assoc-self is the loop

    x₀         ═ (by sym idem-triple-l)
    (x₀*x₀)*x₀ ═ (by assoc)
    x₀*(x₀*x₀) ═ (by idem-triple-r)
    x₀

that witnesses the path between the two constructions.  Equality
congruence with assoc-self gives ⋆-assoc-raw.  Since ΩA is commutative
(loop-comm) and the equality congruence witness satisfies the square
identity (eq-congr-sq), we can use ∙-cancel to strip assoc-self and
obtain ⋆-assoc.

\begin{code}

  assoc-paths : {a b c x y z : A} (p : a  x) (q : b  y) (r : c  z)
               eq-congr (assoc a b c) (assoc x y z) ((p  q)  r)
               p  (q  r)
  assoc-paths refl refl refl = eq-congr-refl _

  idem-triple-l : (x₀ * x₀) * x₀  x₀
  idem-triple-l = (idem x₀   refl)  idem x₀

  idem-triple-r : x₀ * (x₀ * x₀)  x₀
  idem-triple-r = (refl  idem x₀)  idem x₀

\end{code}

We now have, recorded as triple-fold-l,

  (a*b)*d ════════════ (p ★ q) ★ r ══════════════════════ (a*b)*d
     ║                                                       ║
(hab ★refl) ∙ hcd                                       (hab ★ refl) ∙ hcd
     ║                                                       ║
     e ══ eq-congr hcd hcd (eq-congr hab hab (p ★ q) ★ r) ══ e

And we have that triple-fold-r does the same for the right-associated
parenthesization.

\begin{code}

  triple-fold-l : {a b c d e : A} (hab : a * b  c) (hcd : c * d  e)
                  (p : a  a) (q : b  b) (r : d  d)
                 eq-congr
                   ((hab  refl)  hcd)
                   ((hab  refl)  hcd)
                   ((p  q)  r)
                 eq-congr
                    hcd
                    hcd
                    (eq-congr hab hab (p  q)  r)
  triple-fold-l refl refl p q r = refl

  triple-fold-r : {a b c d e : A} (hab : a * b  c) (hcd : d * c  e)
                  (p : a  a) (q : b  b) (r : d  d)
                 eq-congr
                   ((refl  hab)  hcd)
                   ((refl  hab)  hcd)
                   (r  (p  q))
                 eq-congr
                    hcd
                    hcd
                    (r  eq-congr hab hab (p  q))
  triple-fold-r refl refl p q r = refl

  loop-triple-l : (p q r : ΩA)
                 eq-congr idem-triple-l idem-triple-l ((p  q)  r)
                 (p  q)  r
  loop-triple-l p q r = triple-fold-l (idem x₀) (idem x₀) p q r

  loop-triple-r : (p q r : ΩA)
                 eq-congr idem-triple-r idem-triple-r (p  (q  r))
                 p  (q  r)
  loop-triple-r p q r = triple-fold-r (idem x₀) (idem x₀) q r p

  assoc-self : ΩA
  assoc-self = sym idem-triple-l  (assoc x₀ x₀ x₀  idem-triple-r)

  ⋆-assoc-raw : (p q r : ΩA)
               eq-congr assoc-self assoc-self ((p  q)  r)
               p  (q  r)
  ⋆-assoc-raw p q r =
   eq-congr
    (sym (congr-∙ (assoc x₀ x₀ x₀) idem-triple-r _ idem-triple-r _)
       sym (congr-∙ (sym idem-triple-l) _ _ _ _))
    (loop-triple-r p q r)
    (ap (eq-congr idem-triple-r idem-triple-r)
      (ap (eq-congr (assoc x₀ x₀ x₀) _)
          (sym (eq-congr-sym (loop-triple-l p q r)))
         assoc-paths p q r))

  ⋆-refl : (p : ΩA)  p  refl  act-l p
  ⋆-refl p =
   ⋆-in-terms-of-∙ p refl
    ap (act-l p ∙_) act-r-refl
    ∙refl (act-l p)

\end{code}

We strip assoc-self using the commutativity of ΩA and the square
identity:

  assoc-self ∙ ⋆-assoc-raw  =  (p ⋆ q) ⋆ r ∙ assoc-self

(by eq-congr-sq once we know loop-comm).

\begin{code}

  ⋆-assoc : (p q r : ΩA)  (p  q)  r  p  (q  r)
  ⋆-assoc p q r =
   ∙-cancel assoc-self _ _ (loop-comm _ _  sym (eq-congr-sq _ _ _))
    ⋆-assoc-raw p q r

\end{code}

We now conclude that every loop is trivial.

act-l is idempotent:

  act-l (act-l p)
   = act-l (p ⋆ refl)    (by ⋆-refl)
   = p ⋆ (refl ⋆ refl)   (by ⋆-assoc)
   = p ⋆ (act-l refl)    (by ⋆-refl)
   = p ⋆ refl            (by act-l-refl)
   = act-l p             (by ⋆-refl)

\begin{code}

  act-l-idem : (p : ΩA)  act-l (act-l p)  act-l p
  act-l-idem p =
   eq-congr
    (⋆-refl _  ap act-l (⋆-refl p))
    (ap (p ⋆_) (⋆-refl refl  act-l-refl)  ⋆-refl p)
    (⋆-assoc p refl refl)

\end{code}

act-l p = refl.

  act-l p ∙ act-l p
   = act-l (act-l p) ∙ act-l (act-l p)   (act-l-idem twice)
   = act-l p                             (act-l-idemp)

So act-l p acts as a right-identity on itself, and we can left-cancel
to get refl.

\begin{code}

  act-l-trivial : (p : ΩA)  act-l p  refl
  act-l-trivial p =
   ∙-cancel
    (act-l p)
    (act-l p)
    refl
    ((ap₂ _∙_
          (sym (act-l-idem p))
          (sym (act-l-idem p))
       act-l-idemp (act-l p))
       sym (∙refl (act-l p)))

\end{code}

Every loop is trivial:

  p  =  act-l p ∙ act-l p  =  refl ∙ refl  =  refl.

The first step is act-l-idemp backwards, and the second is
act-l-trivial. This shows that the type A is a set, as we wished to
know.

\begin{code}

  Ω-null : (p : x₀  x₀)  p  refl
  Ω-null p =
   sym (act-l-idemp p)
    ap₂ _∙_ (act-l-trivial p) (act-l-trivial p)
    ∙refl refl

\end{code}