Discrete Algebraic Methods

–Finite subsets R ⊆ M are rational.

–If R, R' are rational, then so are R ∪ R', R ⋅ R' and R∗.

Every finitely generated submonoid N ⊆ M is rational, but there also exist rational submonoids which are not finitely generated. The standard example for this is N = {(0, 0)}∪{ (m, n) ∈ℕ×ℕ|m ≥ 1 }; N is a submonoid of ℕ×ℕ but it cannot be finitely generated because for any finite set of pairs (mi , ni) the element (1, 1 + max{ni}) is in N but not in the submonoid generated by the pairs (mi , ni). The submonoid N is rational because N = {(0, 0)} ∪ {(1, 0)} + ({(1, 0)} ∪ {(0, 1)})∗. For groups the situation is different.

Theorem 8.21. Let H be a rational subgroup of a group G. Then H is finitely generated.

Proof: Since H is rational, there is a finite ...