18
$\begingroup$

In ZFC, we can easily say when a triple $\mathscr{G}=\left\langle G,\cdot,1 \right\rangle $ is a group. Furthermore, we can say when a group is finitely generated: First define a "canonical" finitely generated group on $n$ generators by taking the set of all finite ordered tuples of elements from a fixed set of size $n$ ("words in these elements"), and defining the usual equivalence relation that will make the set of equivalence classes into a group. Second, a f.g. group will be a group isomorphic to some quotient of that canonical f.g. group (I believe we can say all this in ZFC, please correct me if I'm mistaken).

So now the question is - will every statement about f.g. groups be decidable in ZFC? Put differently - can any statement about these groups be independent of ZFC? What about finitely presented groups (where the the group in the quotient is itself f.g.)?

For reference, I think of Whitehead's problem that was shown by Shelah to be independent of ZFC. The main difference is that here we are dealing with things that have some finiteness in them, so it is less clear to me whether they can be so manipulated.

$\endgroup$
6
  • 1
    $\begingroup$ Nice question... $\endgroup$ – Asaf Karagila Mar 17 '16 at 11:09
  • 3
    $\begingroup$ I think this depends on what counts as a "statement about f.g. groups". Arguably one could disguise every arithmetical statement (such as "ZFC is consistent") as one about finitely generated free abelian groups -- with group product playing the role of addition and the tensor product of abelian groups playing the role of multiplication. $\endgroup$ – hmakholm left over Monica Mar 17 '16 at 11:38
  • $\begingroup$ @HenningMakholm, that's probably a better way of doing it than what I tried in my answer. $\endgroup$ – goblin GONE Mar 17 '16 at 12:00
  • 1
    $\begingroup$ To begin, P vs NP might be independent of ZFC. But then P vs NP can be formulated as a group-theoretic problem. Specifically, (I am quoting Sapir on MO here): "Sapir, Birget and Rips, Isoperimetric and isodiametric functions of groups Ann. of Math. (2) 156 (2002), no. 2, 345–466, proved that P=NP if and only if the word problem in every group with polynomial Dehn function can be solved in polynomial time by a deterministic Turing machine... $\endgroup$ – user1729 Mar 17 '16 at 12:52
  • $\begingroup$ ..."Thus to show that P=NP one "only" needs to find an algebraic description of finitely presented groups with polynomial Dehn functions (similar to Gromov's description of groups with polynomial growth functions)." $\endgroup$ – user1729 Mar 17 '16 at 12:52
16
$\begingroup$

You're not very concrete about what you consider a "statement about f.g. groups", but presumably we can speak about the property of being a finitely generated free abelian group.

If $G_1$ is a free abelian group on $n$ generators and $G_2$ is a free abelian group on $m$ generators, then the direct product $G_1\times G_2$ is a free abelian group on $n+m$ generators, and the tensor product $G_1\otimes G_2$ is a free abelian group on $nm$ generators.

Therefore, if you allow speaking about direct products and tensor products of abelian groups, then you can speak about addition and multiplication of natural numbers, and then you can express every arithmetical sentence. Among these is "ZFC is consistent", which is undecidable by ZFC itself (unless ZFC is, in fact, not consistent).

$\endgroup$
9
$\begingroup$

I am not sure I understood your question correctly, so let me state my interpretation:

Are there questions about groups which are undecidable (in ZFC)?*

The answer to this question is "yes". This is particularly interesting for finitely presented groups, due to the notion of a Markov property (see Lydon and Schupp, Section IV.4, p192). Let $\mathcal{P}$ be a property of finitely presented groups which is preserved under isomorphism. The property $\mathcal{P}$ is said to be a Markov property if:

  1. There is a finitely presented group $G_1$ with $\mathcal{P}$, and
  2. There is a finitely presented group $G_2$ which cannot be embedded in any finitely presented group which has $\mathcal{P}$.

Theorem (Aidan-Rabin). Let $\mathcal{P}$ be any Markov property of finitely presented groups. Then there is no algorithm which decides whether or not a given finitely presented group has the property $\mathcal{P}$.

Examples of Markov properties, and hence of properties of finitely presented groups which are not recursively recognizable, are:

  • being the trivial group;
  • being finite;
  • being abelian;
  • being nilpotent;
  • being solvable;
  • being free;
  • being torsion-free;
  • being residually finite;
  • having a solvable word problem;
  • being simple;
  • being automatic.

Incidentally, the property of being "being a group" for a set under an operation is undecidable (you state otherwise in your question). To see this, it helps to know that Markov properties were originally defined for semigroup presentations, and Markov proved the analogous result to the Aidan-Rabin theorem, above. Then "being a group" is a Markov property for finitely presented semigroups (because there exist semigroups which do not embed into groups), and hence is recursively undecidable.

I doubt, but am unsure how to prove, that "being finitely generated" is decidable for groups.

*This is quite different to your re-statement: "can any statement about (f.g.) groups be independent of ZFC?"

$\endgroup$
2
  • 1
    $\begingroup$ It seems that I myself might be a bit confused about what exactly does it mean "undecidable by ZFC". Could you please state exactly what do you mean when you say that, to avoid confusion? $\endgroup$ – Ur Ya'ar Mar 19 '16 at 16:16
  • $\begingroup$ I think that maybe what I was aiming for was more in the spirit of: "Can there be some property P of finitely generated groups s.t. (assuming ZFC is consistent) there is a model of ZFC where every f.g. group has P, and a model where there is a f.g. group without P". Is this the same? $\endgroup$ – Ur Ya'ar Mar 19 '16 at 16:20

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.