Characterize the ideals and congruences on the semigroup of natural numbers under the operator. (I.e., if , otherwise.)
First we will make some definitions.
Definition: A subset is called an interval if, whenever and , .
Lemma 1: Every nonempty interval in has the form for some or . Proof: Every nonempty interval on has a least element by the well-ordering property of natural numbers. If a nonempty interval has a greatest element , then for all , and so we have . If does not have a greatest element, then for every , there exists with , and thus . So we have .
Lemma 2: If and are disjoint intervals and there exist and such that , then for all and we have . Proof: Suppose to the contrary that there exist and with . There are six possible orderings for which preserve and . Specifically, these are , , , , , and . In each case, is not empty.
Next we consider the ideals on . To that end, let be a subset.
Suppose that is an ideal under the operator. If is nonempty (as we insist our ideals to be), then it has a least element by the well-ordering property of the natural numbers. If , then , and if , then since is minimal. Thus .
Conversely, suppose for some . If and , then we have . So , and thus . So is an ideal.
Hence the ideals of are precisely the intervals where .
Now we will consider the congruences on . To that end, let be an equivalence relation.
Suppose is a congruence, and let be a -class. We claim that is an interval. To that end, let and suppose . Now and , so that (since is a congruence) , and thus . So . Thus is an interval (by our definition above). Thus if is a congruence on under , then the classes of are pairwise disjoint intervals.
Conversely, suppose the classes of the equivalence relation are pairwise disjoint intervals. We claim that is a congruence. To that end, suppose and , and suppose without loss of generality that . By Lemma 2, we have . So . Thus is a congruence.
Hence the congruences on are precisely the paritions of which consist of intervals.