2

I am solving an exercise from my class and my task is to prove that two algebras descried below are subdirectly irreducible. I have described the algebras and their non-trivial congruence relations and I am proving that they are subdirectly irreducible iff the intersection of all non-trivial congruence relations is non-zero.

Here is my progress, however, I am still struggling to prove that the congruence relations that I found are really congruence relations and that there are no other non-trivial congruence relations.

I will really appreciate any help.

  1. Congruence relations on $P^l_5$

$P^l_5$ := $(\{0, 1, 2, 3, 4\}, f^l_n)$, $f^l_n(4)=4$, $f^l_n(x)=x+1$ for $x \neq 4$

enter image description here

Trivial congruence relations: $|012349|$, $|0|1|2|3|4|$.

Non-trivial congruence relations: $|0|1|2|34|$, $|0|1|234|$, $|0|1234|$. There are two congruence classes contained in the intersection of these congruence relations: $|0|$ and $|34|$. So for each non-trivial congruence relation $\theta$, $3 \theta 4$. Therefore $(3,4)$ is our "witness" of subdirect irreducibility.

  1. Congruence relations on $P^l_\infty$

$P^l_\infty$ := $(\{0, 1, 2, 3, 4, ...\}, f^l_\infty)$, $f^l_\infty(0)=0$, $f^l_\infty(x)=x-1$ for $x \neq 0$.

enter image description here

Trivial congruence relations: $|01234...|$, $|0|1|2|3|4|...$.

Non-trivial congruence relations: $|01|2|3|4...|$, $|012|3|4...|$, $|0123|4...|$, ... There is an infinite number of congruence relations. Their intersection contains $|01|$ congruence class. So for each congruence relation $\theta$, $0 \theta 1$. Therefore, the pair $(0,1)$ is our "witness" of subdirect irreducibility.

Tereza Tizkova
  • 2,238
  • 1
    That looks good to me. What is your question? Are you unsure about the fact that you found a monolith for each of those algebras? (A monolith $\mu$ is a congruence of $\mathbf A$ such that $\mu\leq\theta$ for all $\theta\in\mathbf{Con}\mathbf A\setminus{\Delta_A}$.) – amrsa Dec 04 '21 at 15:33
  • @amrsa Thank you. I have two struggles. 1) I cannot find formal version of the "claim" I am using (that SI <=> nonempty intersection of nontrivial congruences). 2) I think I should prove that there is no other congruence. And dont know how. (maybe this is equal to your note about finding a monolith?) – Tereza Tizkova Dec 04 '21 at 17:06
  • 1
    I think in another post it became clear that one of the books you follow is Burris and Sankappanavar. If this is not so, it's easy to find online; if it is, then that result is Theorem 8.4, on chapter II. You don't have to prove that there are not other congruence relations but the ones you mentioned. In fact, there are (infinitely many, in the infinite algebra), but the point is that whenever a congruence is non-trivial, from $a\theta b$ with $a\neq b$ you can always conclude that $3\theta4$, in the first case and $0\theta1$ in the second. – amrsa Dec 04 '21 at 17:32
  • @amrsa You are right, Im reading that book! :) So, for example in the case of $P^l_5$, what is the monolith? I understand there are pairs of elements related by each non-trivial congruence, but I still fail to identify the "minimal" one of them. Is it the $|0|1|2|34|$, because it has least number of elements related with each other? I fail to connect finding a pair of elements, like $(3,4)$ related by each $\theta$ and concluding that there is a monolith and which one is it out of the congruences. – Tereza Tizkova Dec 05 '21 at 11:44
  • 1
    The monolith is that one which you identified: the relation $${3,4}^2\cup\bigcup_{x\in A}{x}^2,$$ or, as you wrote it, $|0|1|2|34|$. Notice that $3\equiv4$ whenever $a\equiv b$ for $a\neq b$ in that algebra and $\equiv$ is a congruence; further, from $3\equiv4$ you cannot derive any other related pairs. – amrsa Dec 05 '21 at 12:18
  • 1
    Notice also that the mentioned relation is not the monolith because it has a minimal number of pairs among the non-trivial congruences; it's because it's contained in each of them, in this case, if there are two different elements which are related, then $3 and $4$ are. Thus it's the least congruence among the non-trivial ones. Algebras that are not s.i. fail to have such a congruence, that is, if they have minimal non-trivial congruences, they have more than one. – amrsa Dec 05 '21 at 12:26
  • @amrsa I finally understand! Thank you! If I could accept your comments as an answer I would do that haha. Really appreciate, since I couldn´t really find many sources explaining this. – Tereza Tizkova Dec 05 '21 at 13:55
  • 1
    You can gather the information provided in my comments with the one you already had in the original question and answer it. Later on, you might accept your own answer (although you don't receive any rep for that) and perhaps someone will upvote it (the same for your other answer with a bounty but which is not entirely correct, as Keith Kearnes showed; you can edit it to make it a good answer). – amrsa Dec 05 '21 at 14:51

1 Answers1

2

I will try and answer my own question, with huge help from @amrsa and his/her comments.

$P^l_5$

Congruence relations on $P^l_5$ $\Delta$ = $|0|1|2|3|4|$. (By $\Delta$, I denote the diagonal congruence relation).

Other congruence relations:

For any $a \in P^l_5$ and any congruence relation $\theta_1$: If $0 \theta a$, then $1 = f(0) \theta_1 f(a) = a+1$ and so on, which gets us to $3 \theta_1 4 => 4 \theta_1 4$ in the end.

Hence, $\theta_1 = |01234|$. (The congruence relation relating all elements is denoted $\bigtriangledown$ in Burris & Sankappanavar, however, I am not sure, how to call it and will use $\theta_i$).

This observation shows that any congruence relation, apart from $\Delta$, has to either have $0$ in a separate class, or all elements are in one class with zero. This will help me generate other congruence relations on $P^l_5$.

If I start from $1$ this time and assume another congruence relation, $\theta_2$, then $1 \theta_2 2 => 2 = f(1) \theta_2 f(2) = 3 => 3 \theta_2 4 => 4 \theta_2 4$. (Assuming that zero is in separate congruence class).

Hence, $\theta_2 = |0|1234|$.

Now I will proceed by assuming $1$ is also in separate class and generating another congruence class, starting from $2 \theta_3 3$. This gives me $\theta_3 = |0|1|234|$.

By similar procedure, $\theta_4 = |0|1|2|34|$.

In conclusion, the non-diagonal congruence relations on $P^l_5$ are: $|01234|$, $|0|1|2|34|$, $|0|1|234|$, $|0|1234|$.

Finding the monolith

The monolith here is the relation $|0|1|2|34|$ (also possible to be written as $\{3,4\}^2 \cup \bigcup_{x \in A}\{x\}^2$). It is because for aby $a,b \in P^l_5$, whenever $a \neq b$ and $a \theta b$ by any congruence relation $\theta$, then $3 \theta 4$ too.

To put it another way, from the relation $3 \theta 4$, no other relation can be derived.

Hence the $|0|1|2|34|$ is the monolith because it's contained in each of the other congruence relation (apart from the diagonal one). If there are any two different elements which are related, then $3$ and $4$ must be related too. Thus it's the least congruence among the non-trivial ones.

Whenever $a \neq b$ and $a \alpha b$ by some congruence relation $\alpha$, it follows that $a + 1 \alpha b + 1 => a + 2 \alpha b + 2$ ... $4 \alpha 4$. And the step before $4 \alpha 4$ hass to be $3 \alpha 4$ if $a \neq b$, so $3 \alpha 4$ always follows.

The pair $(3,4)$ is therefore the "witness" of subdirect irreducibility of the $P^l_5$.

$P^l_\infty$

Congruence relations on $P^l_\infty$ $\Delta$ = $|0|1|2|3|4|...$.

Other congruence relations:

I will use similar thought process as with $P^l_5$. However, this time, $0$ will be in the role of $4$, because it is mapped to itself. So now, any element will be either in separate class, or together in a class with $0$.

This means that naturally, one congruence relation is immediately $\theta_1 = |01234...|$.

Then, I will proceed by putting more and more elements into the class together with zero and this way generate the rest.

For $\theta_2$, suppose $|01|$ is one congruence class (which is possible, because $0 = f(0) \theta_2 f(1) = 0$ holds). Then, if $2 \theta_2 a$ for any $a \neq 0,1,2$, then $1 \theta_2 a$ and $0 \theta_2 a$ ass well, which goes against the assumption that $0, 1$ are in a separate class. Similar thinking about other elements shoes that there is always one congruence class containing zero, and the other elements are either in this class with zero, or they are in one-element class.

Hence, the (non-diagonal) congruence relations on $P^l_\infty$ look like this:

$|01|2|3|4...|$, $|012|3|4...|$, $|0123|4...|$, ...

Indeed, the $P^l_\infty$ is an infinite algebra and there is an infinite number of congruence relations on $P^l_\infty$.

Finding the monolith

Here, the monolith is $|01|2|3|4...|$, because for any $a,b \in P^l_\infty$, $a \neq b$, if they are related by any congruence $\theta$, then $0 \theta 1$ too.

Whenever $a \neq b$ and $a \alpha b$ by some congruence relation $\alpha$, it follows that $a - 1 \alpha b - 1 \implies a - 2 \alpha b - 2 \implies$ ... $0 \alpha 0$. And the "step" before $0 \alpha 0$ has be $0 \alpha 1$ if $a \neq b$, so $0 \alpha 1$ always follows.

Hence, this algebra is again subdirectly irreducible and the pair $(0,1)$ is the "witness" of subdirect irreducibility.

Tereza Tizkova
  • 2,238
  • 1
    Well, it's not like you have to give a detail account of every principal congruence relation, but you still have to justify that, for example $\theta(1,3)=\nabla$, which follows from $$1\equiv3 \Rightarrow 2\equiv4 \Rightarrow 3\equiv0,$$ whence ${\equiv}={\nabla}$, by your reasoning above. The same for $\theta(1,4)$ ($\theta(2,4)$ would already follow from the above displayed implications); likewise for the other example. I'm sure you'll do that so I'll upvote it right now. – amrsa Dec 05 '21 at 20:09
  • 1
    By the way, I suppose you know these algebras are called mono-unary. In an answer to another question a few years ago, I had to mention (without proving it) which are, up to isomorphism, all the mono-unary algebras. These are all the prime power cycles, with or without an extra isolated point adjoined, plus the the finite chains and the invite chain you have there as $P_{\infty}^l$. – amrsa Dec 05 '21 at 20:14
  • @amrsa So you mean I should prove that for example on $P^l_5$ if any other elements than 3, 4 are related by some congruence than this congruence must be the "biggest one" and therefore only the pair $(3,4)$ is in that one class together in the monolith, right? – Tereza Tizkova Dec 05 '21 at 20:34
  • 1
    You don't have to do that, as there could be more than three congruences, as it is the case in the infinite algebra; in the case of $P^l_5$, it's equivalent. What you need to prove is that whenever $a\neq b$ and $a\equiv b$ for some congruence $\equiv$, then $3\equiv4$; or, in the case of $P^l_{\infty}$ which has infinitely many congruences, $0\equiv1$. So $\equiv$ doesn't have to be $\nabla$, it just must include the monolith. – amrsa Dec 06 '21 at 09:50
  • @amrsa Alright, updated (in bold) and thank you again. Btw interesting source about the mono-unary algebras, didnt know this. – Tereza Tizkova Dec 06 '21 at 21:37
  • If you consider to edit your answer to the other question (the one with the bounty) as I suggested in a comment above, then notify me, so that I might upvote it (if I think it is correct) and close this page. Notice that it's not really more difficult than this one. – amrsa Dec 06 '21 at 21:42