For each first order sentence $\phi$ in the language of groups, define :

$$p_N(\phi)=\frac{\text{number of nonisomorphic groups $G$ of order} \le N\text{ such that } \phi \text{ is valid in } G}{\text{number of nonisomorphic groups of order} \le N}$$

Thus, $p_N(\phi)$ can be regarded as the probability that $\phi$ is valid in a randomly chosen group of order $\le N$.

Now define $$p(\phi)=\lim_{N \to \infty}p_N(\phi)$$ if this limit exists.

We say that the theory of groups fulfills a first order zero-one law if for every sentence $\phi$, $p(\phi)$ exists and equals either $0$ or $1$. I'm asking myself whether this 0-1 law holds indeed in group theory.

Since it is conjectured that "almost every group is a 2-group", statements like $\exists x: x\ne 1 \wedge x^2=1 \wedge \forall y:xy=yx$ (meaning $2|Z(G)$) or $\forall x: x^3=1 \to x=1$ (no element has order 3) should have probability $1$ and I don't see any possibility to construct any sentence with $p\not \in \{0,1\}$. Am I missing an obvious counterexample, or can you show (under the condition that almost every group is indeed a 2-group) that the theory of finite groups fulfills this 0-1 law?

  • 8
    $\begingroup$ $\mathcal L_{\text{grp}}=\{e,\circ,{}^{-1}\}$. What is unclear to you? $\endgroup$ – Dominik Jun 30 '13 at 21:09
  • 6
    $\begingroup$ No since, in first order logic, quantifiers refer only to elements of your group, not to functions or subsets of the group. $\endgroup$ – Dominik Jun 30 '13 at 21:14
  • 24
    $\begingroup$ @Alexander: there doesn't exist a first-order sentence in the language of groups which is true precisely of the nilpotent groups, although this isn't obvious. The reason is that the class of nilpotent groups isn't closed under ultraproducts (see en.wikipedia.org/wiki/Ultraproduct#.C5.81o.C5.9B.27s_theorem). However, there is a first-order sentence which is true precisely of the $k$-step nilpotent groups for a fixed $k$, the reason being that $k$-step nilpotence is equivalent to the vanishing of a finite collection of iterated commutators. $\endgroup$ – Qiaochu Yuan Jun 30 '13 at 21:21
  • 9
    $\begingroup$ Since nobody responded to my 500 bounty, I suggest you crosspost this question to MO, if you haven't already. $\endgroup$ – Alexander Gruber Sep 16 '13 at 23:23
  • 9
    $\begingroup$ The question has now been crossposted at mathoverflow.net/questions/150603 . $\endgroup$ – Emil Jeřábek Dec 5 '13 at 14:14

Sharing the question within MO has brought some interesting comments - I send you there for reference - but in the last 2 years there has been no new contribution. So I'm wrapping it up for the less technical scope of SE:

As per now, a FO 0-1 law for group theory as defined by Dominik doesn't exist and may never exist.

The consensus seems to be that an accepted and complete view of what group theoretic concepts correspond to in a classical logic framework is needed to address the problem but - as per now - it is not available.

The actual methods available to cross-translate group theoretic concepts into logic ones seem to suggest that such a law cannot exist for the whole group theory or even for finite group theory. Limiting laws have infact been identified such that group theoretical entities can be partitioned into different classes exhibiting different logical behaviours (i.e. quantification over functions which is ubiquitous in group theory; but also abelianity appears to be relevant). While yet to be proven, some of these classes can be expected to obey a 0-1 law for FOL while some others can be expected to not obey it.


Sentence proposals:

  1. The cardinality of $G$ is even.

    • I strongly suspect the limit diverges by having a zero $\lim\inf$ and a unit $\lim \sup$. Via supermultiplicity, the number of groups of order $2^k n$ is bounded below by the number of order $2^k$ times the number of order $n$, so is infrequently "small" ($n$ prime) and frequently large. Additionally, the number of groups of a given order is upper bounded (see http://www.jstor.org/stable/2946623 ) by something not too stupendously rapidly growing, so no $N$ is going to miraculously overwhelm the running average.
  2. Let $P(n)$ be the cardinality of the set of isomorphism classes of groups of order $n$. For all positive integers $n$, $P(n)>0$ since there is at least a cyclic group of order $n$. Let $C(n) = \sum_{i=1}^n P(n)$, which is clearly positive and monotonically increasing on the positive integers. Set $a_0=1$ and, for $j>0$, set $a_j = \min_i\{i \mid C(i)-a_{j-1} > 2^{2j}\}$, such an $i$ exists because $C$ is monotonically increasing. Let $T = \bigcup_{j=0}^\infty [a_{2j}, a_{2j+1})$ and let $\phi$ be the predicate $|G| \in T$. By construction, $p_N(\phi)$ swings by a factor of two through each interval $[a_j, a_{j+1})$ (from something < $2^{-j}$ to something $> 1- 2^{-j}$ and vice versa). Therefore, the limit as $N$ goes to infinity does not exist.

    • It's not clear to me how this sort of see-saw argument fails in any set that has something like a positive semidefinite inverse norm with infinite support. ($P(n)$ is that inverse norm here, taking cardinalities (a usual norm) to the number of isomorphism classes.)
  • 5
    $\begingroup$ Heuristically "almost all groups are $2$-groups," so we can confidently predict that "the cardinality of $G$ is even" will correspond to a probability of zero. $\endgroup$ – anon Feb 12 '14 at 8:22
  • 4
    $\begingroup$ @anon Shouldn't that be probability $1$ instead? $\endgroup$ – EuYu Feb 12 '14 at 8:28
  • 5
    $\begingroup$ @EricTowers The point is that before you get to the groups of order $3\cdot 2^k$ you hit the groups of order $2\cdot 2^k = 2^{k+1}$ and there are so vastly many of those that they dwarf the groups of $3\cdot 2^k$. The bias doesn't 'settle out' because 2 is the smallest number, so among the numbers with prime multiplicity $k$ $2^k$ is always smallest. $\endgroup$ – Steven Stadnicki Feb 12 '14 at 17:29
  • 2
    $\begingroup$ In #2: would I be correct in saying "cardinality $n$" (for fixed $n$) can be expressible as a simple combination of $\exists,\not\exists,=,\ne$s? However, $\phi$ seems to implicitly quantify over an infinite number of possible cardinalities $-$ is this an accurate impression? $-$ so I don't see why $\phi$ would be expressible in the first-order language of groups. $\endgroup$ – anon Feb 12 '14 at 19:30
  • 6
    $\begingroup$ @EricTowers Can you point to a single $n\gt 256$ where the majority of groups of order $\leq n$ are not of order a power of 2? $\endgroup$ – Steven Stadnicki Feb 25 '14 at 7:14

protected by Zev Chonoles Nov 20 '15 at 3:16

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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