Draw lattice of all subuniverses or congruences

Question

I am solving this exercise:

Draw lattices of all subuniverses and of all congruences of $(\mathbb{N}, \star)$, where $x \star y$ is defined as $\max(x, y) + 1$ and $\mathbb{N}$ is the natural numbers $1,2,3,\ldots$

I know the definitions, but I cannot proceed to how to determine and draw ALL the subuniverses and congruences. For the subuniverses, I would start perhaps with finding all subalgebras? To be honest, I started with listing some random possible subalgebras, but this doesn´t seem to be the perfect method.

I really don't know how to apply the definitions on this and would appreciate any help.

EDIT: already tried to solve a part of this question (see my answer) about subalgebras. Main problem is still how to draw them.

Answer 1

Your answer correctly describes the subalgebras (except that you've forgotten about the empty subalgebra). You ask "how would you draw the lattice"? Well, writing $A_n$ for the subalgebra $\{x\in \mathbb{N}\mid x\geq n\}$, we have $A_n\subseteq A_m$ if and only if $m\leq n$. So the lattice is just an infinite descending chain, with the empty subalgebra at the bottom: $$\require{AMScd} \begin{CD} A_1\\ @AAA \\ A_2\\ @AAA \\ A_3\\ @AAA \\ \vdots\\ \varnothing \end{CD} $$

Ok, what about the congruences? Suppose $\approx$ is a congruence on $(\mathbb{N},\star)$. If $n\approx m$ with $n<m$, what other instances of $\approx$ are forced on us? Well, we must have $n\star k\approx m\star k$ for all $k$. Now there are three cases:

Case 1: $k< n$. Then $n\star k = n+1$ and $m\star k = m+1$, so $n+1\approx m+1$.

Case 2: $n\leq k\leq m$. Then $n\star k = k+1$ and $m\star k = m+1$. So $k+1\approx m+1$. Note that this is stronger than what we learned from Case 1, since we get $n+1\approx m+1$ in the special case $k= n$.

Case 3: $m< k$. Then $n\star k = k+1$ and $m\star k = k+1$. This case tells us nothing, since $k+1\approx k+1$ is always satisfied.

Ok, but from Case 2, we see that all the elements in the interval $[n+1,m+1]$ are congruent to $m+1$. In particular, $m\approx m+1$, and since $n\approx m$, we have $n\approx m+1$ as well. Since $m\approx m+1$, by Case 1 $m+1\approx m+2$, $m+2\approx m+3$, etc. So all the elements in the interval $[n,\infty)$ are congruent.

This gives us a clear picture of the possible congruences: First, there is the discrete congruence $=$. If $\approx$ is not discrete, then there is a least $n$ such that $n\approx m$ with $n<m$. By the analysis above, $[n,\infty)$ is one congruence class, and $\{k\}$ is a congruence class for all $k<n$, by how we defined $n$. Let's call this congruence $\approx_n$.

To be careful, let's check that $\approx_n$ is actually a congruence. By symmetry of $\star$, it suffices to show that if $a\approx_n b$, then $a\star c \approx_n b\star c$. If $a < n$, then $a = b$, so $a\star c = b\star c$. If $a \geq n$, then $b\geq n$, so $a\star c\geq a+1 \geq n$ and $b\star c\geq b+1\geq n$, and thus $a\star c \approx_n b\star c$.

The discrete congruence $=$ is least, and we have ${\approx_n} \subseteq {\approx_m}$ if and only if $m \leq n$. So again we get an infinite descending chain, with the discrete congruence at the bottom:

$$ \begin{CD} \approx_1\\ @AAA \\ \approx_2\\ @AAA \\ \approx_3\\ @AAA \\ \vdots\\ = \end{CD} $$

Answer 2

(Partial) answer to how would I find the subalgebras:

Suppose $\mathfrak{A}$ is a subalgebra of $(\mathbb{N}, \ast)$. What can I say about it?

• Considering the standard ordering on $\mathbb{N}$, it always contains a smallest element
• Because $\mathfrak{A}$ is nonempty, for any element, I can always find finite number of smaller elements
• The operation can be interpreted such that for any $a \in \mathfrak{A}, a \ast a = a + 1$ - hence $a + 1$ is still contained in $\mathfrak{A}$
• If I "iterate" the above, $(a + 1) \ast (a + 1) = (a + 1) + 1$ - hence the above-said property is still kept

These properties can be formalized: $a \in \mathfrak{A} \implies (\forall b \geq a) \: b \in \mathfrak{A}$. Each set of the form $\{a, a+1, ... \mid a \in \mathbb{N}\}$ is always a subalgebra of $\mathfrak{A}$, since the operation $\ast$ cannot "return" anything smaller than the smallest element + 1.

Conculsion: All the subalgebras $(\mathbb{N}, \ast )$ are in this form: $\{a, a+1, ... \mid a \in \mathbb{N}\}$.

Could you check if my thought process is correct and how would you draw the lattice of these subalgebras? (Since it goes to infinity, I am not sure how to visualize).