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.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: