1
$\begingroup$

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?

$\endgroup$
4
  • 5
    $\begingroup$ You're using the word "satisfies" backwards: a structure satisfies a sentence, not the other way around. $\endgroup$ Jan 13, 2020 at 23:42
  • 5
    $\begingroup$ More importantly, $\mathbb{Z}_n$ is not a submodel of $\mathbb{Z}$ - think about how addition "loops around" in the former but not the latter. $\endgroup$ Jan 13, 2020 at 23:44
  • $\begingroup$ Oh, yes. If it were written $(Z,+_n,0),$ it would be true. Can this be proven with $(Z,+,0)?$ $\endgroup$
    – math_
    Jan 14, 2020 at 9:55
  • 1
    $\begingroup$ @ljubinaa What is the structure $(Z,+_n,0)$? i.e. how do you define $+_n$ on all pairs of integers? $\endgroup$ Jan 15, 2020 at 14:31

1 Answer 1

7
$\begingroup$

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}$.

$\endgroup$
1
  • $\begingroup$ Thank you! I understand this. $\endgroup$
    – math_
    Jan 15, 2020 at 20:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .