Finitely generated monoids - how to show that there is not first order set axiomatizing them.

Let $\mathbb{M}=\langle M,\circ, e\rangle$ be a monoid. We say that $\mathbb{M}$ is finitely generated when there exist finitely many elements in $M$ such that each element of $M$ may be generated using only these elements.

For example, $\langle A^*, \cdot, \epsilon\rangle$ is finitely generated if only and only alphabet $A$ is finite.
Show that the class of finitely generated monoids is not axiomatized.

I would like to use Ehrenfeucht-Fraissé games to prove it. I solved some tasks about showing not-axiomatization with these games, however mentioned exercises were about graphs. So my solutions are based on relations (edges, degrees..). Here, I have no idea which side of this exercise should be attacked by me.

Help me please.

Edit after hints of @Noah
Lets suppose that such $\Delta$ exists. Then, lets extend signature by constans: $c_1,c_2,...$ and let $\Delta'=\Delta\cup \Gamma$, where $\Gamma=\{\forall_{x\in A}\forall_{y\in A}x\circ y \neq c_i:i\in\mathbb{N} \}$. Of course we have infinitely many elements not generated by rest of elements. Using compactness theorem we conclude contradiction. Let $\Delta_0\subseteq\Delta'$ will be finite set. Then it is easy to see that it is satisfable - We can add properly many elements to $A$ generated by nothing and assign to them finitely number of constanst $c_i$.

What do you think about this solution ? If I am wrong, tell me where.

Solution 1:

EDIT THE LAST: Haha, wow, we missed the easy solution.

Two hints:

• What can you say about the cardinality of a finitely generated structure in a language of size $\kappa$? HINT: elements of the structure correspond to "words" on a certain set of symbols . . .

• Assuming that there are arbitrarily large finite structures of the type you care about (that is, arbitrarily large finite monoids - which there are), how does that contradict the Compactness Theorem? HINT: think about adding lots of constants . . .

EDIT: This problem is a bit trickier than I thought at first, and my advice was somewhat misleading. There are several ways to solve it; let me outline some below, but first let me comment on your proposed solution. Your $\Gamma$ is in fact inconsistent: for every element $c$ there must be some $x, y$ such that $xy=c$.

Here are the solutions I see:

• Compactness. The fastest way is to use the compactness theorem, but the usage is a bit more complicated than what I had in mind. A short monoid (that's not standard notation) is a monoid with an identity $e$, an annihilator $o$ (that is, $ox=xo=o$ for all $x$), and such that for every nonidentity elements $a, b$ we have $ab=o$. A short monoid is completely characterized by how many elements it has, and is finitely generated iff it is finite (exercise - basically, there are no interesting ways to combine elements). Now suppose the class of finitely generated monoids were axiomatized by a set $\Gamma$ of first-order sentences. Let $\varphi$ be the sentence asserting that the monoid is short; do you see how to use compactness to show that $\Gamma\cup\{\varphi\}$ has an infinite model, and why that's a problem?

• EF-games. This was the approach you initially mentioned. Let $M_n$ be a free monoid on $n$ generators, and let $M_\infty$ be a free monoid on infinitely many generators. Then for every $n$, we can show that Duplicator has a winning strategy in the EF-game between $M_n$ and $M_\infty$ of length $n$. This shows that if $\Gamma$ is true in every $M_n$, then $\Gamma$ is true in $M_\infty$ (why?); so the class of finitely generated monoids is not axiomatizable by a set of first-order sentences.

• Ultraproducts. This is the nuclear solution. If you've seen the proof of compactness via ultraproducts before, then do the following: let $\mathcal{U}$ be a nonprincipal ultrafilter on $\mathbb{N}$, let $M_n$ be a monoid which is generated by $n$ elements but not by $n-1$ (such exist - exercise), and let $N=\prod_\mathbb{N}M_n/\mathcal{U}$ be the ultraproduct. Then it's not too hard to show that $N$ is not finitely generated; however, $N$ satisfies every sentence that all the $M_n$s satisfy by Los' Theorem, so we're done.

You asked for more details about the EF-games approach. Well, if you understand EF-games for graphs, then you understand them for relational structures - relational structures are basically graphs, except (1) there might be more than one kind of edge relation, and (2) "edges" might connect more than one point (so really hypergraphs are the better analogy). But the idea is the same: alternate picking points, and at the end of the day Duplicator wins if every relation true of one tuple is true of the corresponding tuple.

We can pass from a non-relational structure, like a monoid, to a relational one, by replacing each function symbol with its graph. A monoid has two function symbols: a binary function symbol $*$, and a nullary function symbol (= constant symbol) $e$. We replace these with a ternary relation symbol $R_*$ and a unary relation symbol $U_e$, and consider the corresponding axioms:

• $U_e$ holds of exactly one element, and for all $a, b$ there is exactly one $c$ such that $R_*(a, b, c)$ (we interpret "$U_e(x)$" as meaning "$x$ is $e$," and interpret "$R_*(a, b, c)$" as "$a*b=c$").

• The function represented by $R_*$ is associative: $$\forall a, b, x, y, z[(R(a, b, x)\wedge R(b, c, y))\implies (R(x, c, z)\iff R(a, y, z))].$$

• The element named by $U_e$ is the identity of the function represented by $R_*$: $$\forall x(U_e(x)\implies \forall y(R(x, y, y)\wedge R(y, x, y)).$$

And any monoid $M$ can be turned into a structure in this relational language (call it a "relational monoid") $M_{rel}$ as follows:

• $M$ and $M_{rel}$ have the same underlying set.

• $U_e^{M_{rel}}=\{e^M\}$.

• $R_*^{M_{rel}}=\{(x, y, z): (x*y=z)^M\}$.

Now we can play an EF-game as usual between two relational monoids, $M_{rel}$ and $N_{rel}$. And it's not hard to show that $$M_{rel}\equiv N_{rel}\iff M\equiv N,$$ so we're actually studying the same thing.

Ebbinghaus-Flum-Thomas do something slightly different - they explicitly define EF-games on non-relational structures. But I find that slightly more complicated than passing to the relational versions.