Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
7  
$\mathcal L_{\text{grp}}=\{e,\circ,{}^{-1}\}$. What is unclear to you? –  Dominik Jun 30 '13 at 21:09
4  
No since, in first order logic, quantifiers refer only to elements of your group, not to functions or subsets of the group. –  Dominik Jun 30 '13 at 21:14
18  
@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. –  Qiaochu Yuan Jun 30 '13 at 21:21
7  
Since nobody responded to my 500 bounty, I suggest you crosspost this question to MO, if you haven't already. –  Alexander Gruber Sep 16 '13 at 23:23
4  
The question has now been crossposted at mathoverflow.net/questions/150603 . –  Emil Jeřábek Dec 5 '13 at 14:14

1 Answer 1

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.)
share|improve this answer
2  
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. –  anon Feb 12 at 8:22
1  
@anon Shouldn't that be probability $1$ instead? –  EuYu Feb 12 at 8:28
3  
@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. –  Steven Stadnicki Feb 12 at 17:29
1  
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. –  anon Feb 12 at 19:30
1  
@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? –  Steven Stadnicki Feb 25 at 7:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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