# Is there a group with countably many subgroups, but is not countable in ZF?

Inspired by this question, although I don't think it was the OP's intention, hence this separate question:

Is there a group $G$ with countably many subgroups, but is a not a countable group itself in $\mathrm{ZF}$?

In $\mathrm{ZFC}$ we can look at the cyclic subgroups of $G$ and "estimate" the number of elements in the group, to conclude that $G$ is countable. But this ends up not going through in $\mathrm{ZF}$ since a countable union of finite sets does not have to be countable, in particular it is known that that a countable union of two element sets does not have to be countable.

So a possible way to construct such a uncountable group (although I am not saying this is a good way to go, I have no idea) is start with a collection $\{ A_i \mid i \in \mathbb{N} \}$ where $A_i$ are pairs, whose union is not a countable set and note that every torsion free cyclic group has two natural generators, so conceivably there could be a torsion free group with $A_i$ the natural generating set for a cyclic groups ("$1,-1$" but we could not actually define such a function all $A_i$ without the axiom of choice). Then the constructions would have to make sure there are only countable many subgroups (this seems difficult and would take a lot of care)

An interesting paper "On the number of Russell's socks or $2+2+2+\cdots = ?$" by Horst Herrlich, Eleftherios Tachtsis discusses some of the ideas around countable unions of pairs.

• @JoeJohnson126: only with the axiom of choice. – mercio Nov 16 '15 at 17:32
• @JoeJohnson126 In ZFC that is true, but you can not arrive to that conclusion in ZF, as I said in the post. – Paul Plummer Nov 16 '15 at 17:32
• Sorry about that. My brain added a "C" at the end of "ZF". – Joe Johnson 126 Nov 16 '15 at 17:36
• If you had the described injection $S_{\mathbb N}\hookrightarrow S_A$, wouldn't that give you a sock-choosing function? Choose an element of $A_0$; this entails a choice of an element of each $A_i$ by considering the image of the permutation that swaps $0$ with $i$. – Henning Makholm Jan 6 '16 at 19:58
• And there certainly is an injection $f:X\hookrightarrow S_X$ for every set $X$, without choice: If $X$ is empty then this is trivial; otherwise choose a fixed $x_0\in X$ and let $f(x)$ be the transposition $(x\;x_0)$. – Henning Makholm Jan 6 '16 at 20:08

Start with a model of ZF+atoms, $M$, with a set of atoms $A$ which forms a group isomorphic to $\mathbb{D}/\mathbb{Z}$, where $\mathbb{D}$ is the set of dyadic fractions: $\mathbb{D}=\{{p\over 2^k}: p, k\in\mathbb{Z}\}$. Let $G$ be the group of automorphisms of $A$, and consider the symmetric submodel $N$ of $M$ corresponding to the filter of finite supports on $G$. Then in $N$, $A$ is no longer countable, since there are nontrivial automorphisms of $\mathbb{D}/\mathbb{Z}$ fixing arbitrary finite sets; but the only subgroups of $\mathbb{D}/\mathbb{Z}$, other than the whole thing, are those of the form $$\{x: 2^kx=0\}$$ for some fixed $k\in\mathbb{N}$. This provides an explicit bijection - in the original universe, $M$ - between the subgroups of $A$ and $\omega$. Now, passing to $N$, we get no additional subgroups of $A$, and the map described above is symmetric; so in $N$, $A$ has only countably many subgroups.
Meanwhile, the statements "$A$ is uncountable" and "$A$ has countably many finitely generated subgroups" are each "bounded," so we may apply the Jech-Sochor theorem to push this construction into the ZF-setting.
• @AsafKaragila My thoughts got garbled when I was writing this - this is just for the simpler question of getting countably many finitely generated subgroups. For $\mathbb{Q}/\mathbb{Z}$, every finitely generated subgroup is definable in an explicit way as the set of elements with order (dividing) a fixed number, and this provides a perfectly symmetric bijection from $\{$finitely generated subgroups$\}$ to $\omega$. – Noah Schweber Nov 17 '15 at 4:16
• This example does, unfortunately, have uncountably many subgroups: for every set of primes $X$ we can associate the least subgroup of $\mathbb{Q}/\mathbb{Z}$ containing every element of order $\in X$. – Noah Schweber Nov 17 '15 at 4:18
• @AsafKaragila Hang on, what about the group $B$ of dyadic rationals mod $\mathbb{Z}$? A symmetric copy of this would again have countably many finitely generated subgroups, while being uncountable - and unless I'm having a silly moment, $B$ has only finitely-generated subgroups (other than $B$ itself), so this would work. – Noah Schweber Nov 17 '15 at 4:28