If a universal sentence is satisfied by all groups $(\mathbb{Z}_n,+_n,0)$, how to prove that $(\mathbb{Z},+,0)$ satisfies this sentence?

101 Views Asked by At

Let $\forall x_1\forall x_2\ldots\forall x_n\, \varphi(x_1,x_2,\ldots,x_n)$ be a universal sentence that is satisfied by all groups $(\mathbb{Z}_n,+_n,0).$ Prove that the group $(\mathbb{Z},+,0)$ satisfies this sentence.

I would prove: If $\varphi$ is a universal sentence and $\bf A$ is a structure, then $\bf A$ satisfies $\varphi$ if and only if for all finitely generated substructures $\bf B \subseteq A$, $\bf B$ satisfies $\varphi$.

$(\mathbb{Z}_n,+_n,0)$ is a finitely generated substructure of $(\mathbb{Z},+,0)$, and that would be the end of the proof. Is this ok?

1

There are 1 best solutions below

1
On

Your proposed one-sentence proof is wrong for two reasons. First, as noted by Noah in the comments, $\mathbb{Z}_n$ is not a substructure of $\mathbb{Z}$. Second, it seems you're appealing to the quoted theorem with $\mathbf{A} = \mathbb{Z}$ and $\mathbf{B} = \mathbb{Z}_n$. Even if $\mathbf{B}$ were a substructure of $\mathbf{A}$, you would only be able to conclude that if $\mathbf{A}$ satisfies $\varphi$, then $\mathbf{B}$ satisfies $\varphi$, which is the converse of what you want to prove. To use the theorem to show that $\mathbf{A}$ satisfies $\varphi$, you need to check that every finitely generated substructure of $\mathbf{A}$ satisfies $\varphi$. And since $\mathbb{Z}$ is itself finitely generated, this approach isn't going to work.

Here's an alternative approach: Try to find a structure $\mathbf{M}$ satisfying $\varphi$ such that $\mathbb{Z}$ is isomorphic to a substructure of $\mathbf{M}$. Then, since $\varphi$ is universal, you can conclude that $\mathbb{Z}$ satisfies $\varphi$.

How to find $\mathbf{M}$? You could use an ultraproduct or compactness. Let $\theta_k(x)$ be the formula $$\underbrace{x+x+\dots + x}_{k \text{ times}} \neq 0.$$

Ultraproduct proof: Let $\mathcal{U}$ be a non-principal ultrafilter on the natural numbers, and let $\mathbf{M} = \prod_{n\in \mathbb{N}} \mathbb{Z}_n / \mathcal{U}$. Since $\mathbb{Z}_n$ satisfies $\varphi$ for all $n$, also $\mathbf{M}$ satisfies $\varphi$, by Łoś's theorem. Similarly, $\mathbf{M}$ is a group. And the element $[(1,1,1,\dots)]\in \mathbf{M}$ has infinite order (by Łoś's theorem, since for each $k$, $\theta_k(1)$ is true in all but finitely many of the $\mathbb{Z}_n$). So it generates an infinite cyclic subgroup, which is isomorphic to $\mathbb{Z}$.

Compactness proof: Add a new constant symbol $c$ to the language of groups, and consider the theory $T = T_\text{grp}\cup \{\varphi\}\cup \{\theta_k(c)\mid k\in \mathbb{N}\}$, where $T_\text{grp}$ is the theory of groups. Any finite subset of $T$ is satisfied by $\mathbb{Z}_n$, interpreting $c$ as $1$, for $n$ larger than the largest $k$ such that $\theta_k(c)$ appears in the finite subset. So $T$ has a model, $\mathbf{M}$, which is a group satisfying $\varphi$. The interpretation of $c$ in $\mathbf{M}$ has infinite order, so it generates an infinite cyclic subgroup, which is isomorphic to $\mathbb{Z}$.