Can a cyclic group be definined in 1st order logic?

Solution 1:

The problem with $\exists x \forall y \exists n \in \mathbb{N}(y = x^n)$

As you already identified in your question, the problem about $\exists x \forall y \exists n \in \mathbb{N} ( y = x^n )$ is that $n$ quantifies over the natural numbers. In first-order logic, you can only quantify over the elements of the structure you are talking about (in this case, groups). The problem here is thus that in general we do not have the natural numbers as elements of our group.

Still, for every natural number $n$ we can make sense of $x^n$ by defining it to be an abbreviation of $$ \underbrace{x \circ \ldots \circ x}_{n \text{ times}}, $$ where we interpret $x^0$ as the identity element. We can even extend this to all integers (so to $n \in \mathbb{Z}$) by saying that $x^{-n} = (x^{-1})^n$.

As I pointed out in a comment, the sentence $\exists x \forall y \exists n \in \mathbb{N} ( y = x^n )$ would not be true of the infinite cyclic group $\mathbb{Z}$, but only for finite cyclic groups. So I will now switch to the 'correct' definition and when I say cyclic group it will include $\mathbb{Z}$. Although the argument below goes through for the class of finite cyclic groups as well.

So it is clear that even though $x^n$ can make sense, we cannot really write $\exists x \forall y \exists n \in \mathbb{Z} ( y = x^n )$ in the language of groups. We could try something else to stay in the language of groups, for example $$ \exists x \forall y \bigvee_{n \in \mathbb{Z}} y = x^n, $$ is purely in the language of groups but now our formula is infinitely long.

Cyclic groups are not first-order axiomatisable

Can there be some trick to axiomatise the cyclic groups? The answer to this is no, and I will give two arguments for this. One that uses Löwenheim-Skolem (short, but offers little insight), and one that uses the compactness theorem to prove that (bit more work, but offers more insight).

In both cases we assume that there is a first-order theory $T$ in the language of groups whose models are precisely the cyclic groups.

The Löwenheim-Skolem trick is quite simple: since $\mathbb{Z}$ is an infinite model of $T$, there should be infinite models of $T$ of arbitrary large cardinalities (by upward Löwenheim-Skolem). However, an infinite cyclic group is always countable as $\mathbb{Z}$ is the only infinite cyclic group.

The argument using compactness goes as follows. Let us add two new constants, $c$ and $d$, to the language and define $$ T' = T \cup \{c^m \neq d^n : m, n \in \mathbb{Z} - \{0\}\}. $$ Now any finite subtheory of $T'$ is contained in $$ T'_k := T \cup \{c^m \neq d^n : -k \leq m,n \leq k, m \neq 0, n \neq 0 \} $$ for some $k \in \mathbb{N}$. We will show that for any $k \in \mathbb{N}$, this theory $T'_k$ is consistent. To do so, we must find a cyclic group (to make sure it is a model of $T$) and the right interpretations for $c$ and $d$ (to satisfy the second part). We can take $\mathbb{Z}$ and interpret $c$ as 1, and $d$ as $k+1$. Then $|d^n|$ will always be at least $k+1$, while $|c^m|$ will always be at most $k$. So this is indeed a model of $T'_k$, and so by compactness $T'$ must be consistent. Then let $G$ be a model of $T'$. Since $G$ is then in particular a model of $T$, it must be a cyclic group. So there is a generator $g \in G$, such that we have $c = g^k$, $d = g^\ell$ for (the interpretations of) the constants $c$ and $d$, with $k, \ell \in \mathbb{Z}$. However, then $c^\ell = g^{k \ell} = d^k$, which contradicts what $T'$ tells us about $c$ and $d$. So we find our contradiction, and conclude that there can be no first-order theory whose models are precisely the cyclic groups.

Just in case you wonder how you can make this work if we read cyclic group as finite cyclic group, you can still find a model for each $T'_k$ if you take a big enough cyclic group every time. Note that here the Löwenheim-Skolem argument does not go through, as we would have no infinite model.

Alternatively, in the case of finite cyclic groups, you are talking about a first-order theory that has only finite models, but has arbitrarily large finite models. It is a really standard compactness exercise to show that that is impossible.