1

I'm reading an article about automata, and I encounter this:

Let $M$ and $N$ be monoids. We say that $M$ divides $N$; and write $M < N$ , if there is a submonoid $S$ of $N$ and a morphism $\phi: S \to M$ that maps onto $M$ . Informally, $M < N$ means that $M$ is simpler than $N$ . We would naturally consider $M$ to be simpler than $N$ if $M$ is either a submonoid or a quotient of $N$ . We would also expect “simpler than” to be a transitive relation. It is easy to prove (and left as an exercise for the reader) that division is the least transitive relation that includes both the submonoid and quotient relation.

But I dont understand how can I prove that the division is the least transitive relation.Can someone explain to me how to do this?

Tommy do Nascimiento
  • 485
  • 1
    "Least relation" is also called the "smallest relation" (with a given property), as for example in https://math.stackexchange.com/questions/3377113/what-means-smallest-relation-and-what-difference-from-simple-relation. And, confusingly, a smallest relation is also called "minimal", as in https://math.stackexchange.com/questions/1712180/what-is-a-minimal-relation#1712183. – Hew Wolff Feb 21 '23 at 04:24

1 Answers1

4

"Least" isn't modifying "transitive," it's modifying "relation." The phrase

least [property] relation

means "The unique relation $R$ which has [property] and is a sub-relation of every other relation (on the relevant set) with [property]." For example:

  • The least reflexive relation on a set $X$ is just the identity relation $\{(x,x): x\in X\}$.

  • The least symmetric relation on a set $X$ is just the empty relation.

  • More interestingly, the least symmetric relation on $\mathbb{R}$ containing the usual ordering relation $<$ is ... the inequality relation, $I=\{(r,s)\in\mathbb{R}^2: r\not=s\}$. That is, $I$ is symmetric and contains $<$, and any other symmetric relation containing $<$ is at least as big as $I$.

So in particular, the relevant passage is saying that the divisibility relation on monoids is transitive, contains the submonoid and quotient relations, and is contained in any other relation with the previous two properties.

Noah Schweber
  • 245,398