Example of a c.e. coded set (from Montalban's book)

39 Views Asked by At

I'm trying to understand Example 2.1.21 in "Computable Structure Theory: Within Arithmetic" by Montalban. The example is as follows.

Given $X \subseteq \mathbb N$, let $\mathcal G$ be the group $\bigoplus_{i \in X} \mathbb Z_{p_i}$ where $p_i$ is the $i$th prime number and $\mathbb Z_{p}$ is the cyclic group $\mathbb Z/p \mathbb Z$. $X$ is c.e. coded by $\mathcal G$, as $i \in X$ iff there is an element of the group of order $p_i$.

Let me write $\mathcal G_X$ for $\bigoplus_{i \in X} \mathbb Z_{p_i}$. What seems to be problematic for me is that if $X$ is infinite then $\mathcal G_X$ has uncountable domain so it even doesn't have an $\omega$-presentation (which is a structure isomorphic to it with $\mathbb N$ as the domain).

Maybe I am misinterpreting the meaning of $\bigoplus$. But the most obvious candidate is that $\bigoplus_{i \in X} \mathbb Z_{p_i}$ is the direct product of groups $\mathbb Z_{p_i}$, and therefore, for $X$ infinite, the domain of $\mathcal G_X$ will be a product of countably many cyclic groups, e.g. $\mathbb Z_2 \times \mathbb Z_{11} \times \mathbb Z_{23} \times \ldots$, and thus the elements of $\mathcal G_X$ are infinite sequences.

If what I wrote above is correct, then maybe a way out of this is to understand $\mathcal G_X$ as the structure with the domain equal to $\mathbb Z$ (countable) and with with operations $+_{p_i}$ (addition modulo $p_i$) for each $i \in X$. In this case, I belive, the example works, because given any $\omega$-presentation $\mathcal A$ of $\mathcal G_X$, I can search through natural numbers and through the (computable) signature to find an element of a given order, and this is clearly c.e. in the presentation, which means $X$ is c.e. coded in $\mathcal G_X$ (according to the definition of $\mathcal G_X$ from this paragraph).

Thank you for any comments.

1

There are 1 best solutions below

0
On

the most obvious candidate is [...] the direct product

This is incorrect. The notation "$\bigoplus$" denotes the direct sum, which differs from the direct product exactly when infinitely many "factor structures" are involved. Intuitively, the direct sum of a bunch of groups is just like the direct product except that we only allow finitely many "coordinates" to be nontrivial (= not the identity element of the corresponding "factor" group).

A bit more formally, given a family $(G_i)_{i\in I}$ of groups, the direct sum $\bigoplus_{i\in I}G_i$ is the group of functions $f:I\rightarrow\bigcup_{i\in I}G_i$ such that

  • $f(x)\in G_x$ for each $x\in I$, and

  • for all but finitely many $x\in I$ we have $f(x)=e_x$ (the identity element of $G_x$).

The direct product $\prod_{i\in I}G_i$ is defined somewhat similarly but not identitically: the second bulletpoint is not included. It's a good exercise to check that if $I$ is countable and each $G_i$ is countable then $\bigoplus_{i\in I}G_i$ is also countable, even though the full direct product $\prod_{i\in I}G_i$ (of which $\bigoplus_{i\in I}G_i$ is just a subgroup) is usually going to be uncountable.