## Characterize the ideals and congruences on the semigroup of natural numbers under max

Characterize the ideals and congruences on the semigroup $\mathbb{N}$ of natural numbers under the $\mathsf{max}$ operator. (I.e., $a\ \mathsf{max}\ b = a$ if $a \geq b$, $b$ otherwise.)

First we will make some definitions.

Definition: A subset $I \subseteq \mathbb{N}$ is called an interval if, whenever $a \leq c \leq b$ and $a,b \in I$, $c \in I$.

Lemma 1: Every nonempty interval in $\mathbb{N}$ has the form $[a,b] = \{c \ |\ a \leq c \leq b\}$ for some $a,b$ or $[a,\infty) = \{c \ |\ a \leq c\}$. Proof: Every nonempty interval on $\mathbb{N}$ has a least element by the well-ordering property of natural numbers. If a nonempty interval $I$ has a greatest element $b$, then $c \in I$ for all $a \leq c \leq b$, and so we have $I = [a,b]$. If $I$ does not have a greatest element, then for every $c \geq a$, there exists $b \in I$ with $a \leq c \leq b$, and thus $c \in I$. So we have $I = [a,\infty)$. $\square$

Lemma 2: If $I$ and $J$ are disjoint intervals and there exist $a \in I$ and $b \in J$ such that $a \leq b$, then for all $x \in I$ and $y \in J$ we have $x \leq y$. Proof: Suppose to the contrary that there exist $x \in I$ and $y \in J$ with $y \leq x$. There are six possible orderings for $\{a,b,x,y\}$ which preserve $a \leq b$ and $y \leq x$. Specifically, these are $a \leq b \leq y \leq x$, $a \leq y \leq b \leq x$, $a \leq y \leq x \leq b$, $y \leq a \leq b \leq x$, $y \leq a \leq x \leq b$, and $y \leq x \leq a \leq b$. In each case, $I \cap J$ is not empty. $\square$

Next we consider the ideals on $\mathbb{N}$. To that end, let $I \subseteq \mathbb{N}$ be a subset.

Suppose that $I$ is an ideal under the $\mathsf{max}$ operator. If $I$ is nonempty (as we insist our ideals to be), then it has a least element $a$ by the well-ordering property of the natural numbers. If $b \geq a$, then $\mathsf{max}(a,b) = b \in I$, and if $b < a$, then $b \notin I$ since $a$ is minimal. Thus $I = [a,\infty)$.

Conversely, suppose $I = [a,\infty)$ for some $a \in \mathbb{N}$. If $t \in I$ and $s \in \mathbb{N}$, then we have $t \geq a$. So $\mathsf{max}(s,t) \geq a$, and thus $\mathsf{max}(s,t) \in I$. So $I$ is an ideal.

Hence the ideals of $(\mathbb{N}, \mathsf{max})$ are precisely the intervals $[a,\infty)$ where $a \in \mathbb{N}$.

Now we will consider the congruences on $\mathbb{N}$. To that end, let $\sigma \subseteq \mathbb{N} \times \mathbb{N}$ be an equivalence relation.

Suppose $\sigma$ is a congruence, and let $A \subseteq \mathbb{N}$ be a $\sigma$-class. We claim that $A$ is an interval. To that end, let $a,b \in A$ and suppose $a \leq c \leq b$. Now $a \sigma b$ and $c \sigma c$, so that (since $\sigma$ is a congruence) $ac \sigma bc$, and thus $c \sigma b$. So $c \in A$. Thus $A$ is an interval (by our definition above). Thus if $\sigma$ is a congruence on $\mathbb{N}$ under $\mathsf{max}$, then the classes of $\sigma$ are pairwise disjoint intervals.

Conversely, suppose the classes of the equivalence relation $\sigma$ are pairwise disjoint intervals. We claim that $\sigma$ is a congruence. To that end, suppose $a \sigma b$ and $c \sigma d$, and suppose without loss of generality that $a \leq c$. By Lemma 2, we have $b \leq d$. So $ac = c \sigma d = bd$. Thus $\sigma$ is a congruence.

Hence the congruences on $(\mathbb{N}, \mathsf{max})$ are precisely the paritions of $\mathbb{N}$ which consist of intervals.