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.

  • 1
    $\begingroup$ @JoeJohnson126: only with the axiom of choice. $\endgroup$ – mercio Nov 16 '15 at 17:32
  • 1
    $\begingroup$ @JoeJohnson126 In ZFC that is true, but you can not arrive to that conclusion in ZF, as I said in the post. $\endgroup$ – Paul Plummer Nov 16 '15 at 17:32
  • 1
    $\begingroup$ Sorry about that. My brain added a "C" at the end of "ZF". $\endgroup$ – Joe Johnson 126 Nov 16 '15 at 17:36
  • 1
    $\begingroup$ 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$. $\endgroup$ – Henning Makholm Jan 6 '16 at 19:58
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Henning Makholm Jan 6 '16 at 20:08

I believe the answer is yes, as follows:

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.

  • $\begingroup$ The set of atoms is also "nicely definable", but it's not countable anymore, and certainly the set of Its finite subsets if not countable. You need to argue better why the collection of subgroups is countable. $\endgroup$ – Asaf Karagila Nov 17 '15 at 3:45
  • $\begingroup$ @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$. $\endgroup$ – Noah Schweber Nov 17 '15 at 4:16
  • $\begingroup$ 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$. $\endgroup$ – Noah Schweber Nov 17 '15 at 4:18
  • $\begingroup$ Hmm, yes. I agree with that first comment; with the second also, and this is where my concern lies in the possibility of this even happening. I think the right theorem would be from ZF that a group with only countably many subgroups is finitely generated. $\endgroup$ – Asaf Karagila Nov 17 '15 at 4:19
  • $\begingroup$ @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. $\endgroup$ – Noah Schweber Nov 17 '15 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.