All Questions
Tagged with gr.group-theory lo.logic
105 questions
14
votes
2
answers
725
views
Are there any non-conjugation "extendible automorphisms" in the category of finite groups?
Let $\mathbf{Grp}$ be the category of groups. Given a subcategory $\mathscr{G}$ of $\mathbf{Grp}$ and $G\in\mathit{Ob}(\mathscr{G})$, a $\mathscr{G}$-extendible map on $G$ will here mean an assignment ...
- 21.2k
14
votes
2
answers
1k
views
If every definable class admits a group structure, must global choice hold?
It is a remarkable fact, due to Hajnal and Kertész and explained very well in this MathOverflow answer by user Ashutosh, that the axiom of choice is equivalent to the assertion that every nonempty set ...
- 236k
13
votes
4
answers
843
views
What is a "general" relation algebra?
I'm trying to understand why (or if) the axioms of relation algebras are "the right ones." For example, we can back up the idea that the group axioms exactly capture the notion of "...
- 21.2k
8
votes
0
answers
148
views
What is this quotient of the free product?
Previously asked at MSE. The construction here can generalize to arbitrary algebras (in the sense of universal algebra) in the same signature with the only needed tweak being the replacement of "...
- 21.2k
3
votes
2
answers
347
views
Are there $2^{\aleph_0}$ pairwise non-isomorphic countable groups containing every finite group?
Let us call a group $(G,\cdot)$ finitarily complete if $G$ is countable, and every finite group is isomorphic to a subgroup of $(G,\cdot)$.
Is there a collection of $2^{\aleph_0}$ pairwise non-...
- 48.9k
1
vote
0
answers
162
views
Solution of an equation over free group
Let $F_n$ be a free group on $n$ generators. Let $w \in F_n$ be a word such that there does not exist any solution in $F_n$ for the equation $w.w(t_1, \ldots, t_n) = 1$, where $t_1, \ldots, t_n$ are ...
- 355
5
votes
1
answer
294
views
Words which are not inverted by any endomorphism
Let $w$ be a word in a free group $F_2$ of two generators $x_1, x_2$ such that there does not exist any endomorphism of free group which takes $w$ to $w^{-1}$. Let $w_1, w_2$ be two words in the same ...
- 355
4
votes
0
answers
166
views
Is there any good methods for writing down basis for laws of groups?
I am wondering if there is a good method to write down a finite equational basis for a finite group.
Especially I am wondering if there is a good method in following situations:
We can write a group ...
- 93
10
votes
2
answers
581
views
Maximal Abelian subgroups of $S_\omega$
Let $S_\omega$ be the group of permutations (bijections) $\varphi:\omega\to\omega$, together with composition as binary operation.
Zorn's Lemma implies that every commutative subgroup of $S_\omega$ is ...
- 48.9k
3
votes
1
answer
153
views
Is having a Frobenius pair first-order expressible in the language of groups?
I am trying to figure out whether or not the following property is first-order expressible in the language of groups.
$$\text{$G$ has a subgroup $H$ with which it forms a Frobenius pair $(H,G)$.}$$
My ...
- 133
9
votes
0
answers
275
views
Is “simplicity is elementary” still hard? (Felgner’s 1990 theorem on simple groups, and subsequent work)
I came across a reference in this MathOverflow answer to an intriguing result of Ulrich Felgner [1]: among finite non-Abelian groups, the property of being simple is first-order definable. According ...
- 21.3k
4
votes
1
answer
125
views
Logical generators of groups and $\mathrm{Aut}$-bases
An element $s$ of a group $G$ is a logical generator of $G$ iff every element of $G$ can be defined in the first order language of groups with $s$ as a parameter. In this case we may call $G$ a ...
- 2,233
18
votes
3
answers
547
views
Finite presentability and elementary equivalence
Do there exist two elementary equivalent finitely generated groups $G,H$ such that $G$ is finitely presented but $H$ is not finitely presentable?
It seems reasonable to think that finite ...
- 8,401
2
votes
1
answer
223
views
Possible symmetry groups of power terms
Previously asked and bountied at MSE:
Let $\mathfrak{E}=(\mathbb{N};\mathit{exp})$ be the algebra in the sense of universal algebra consisting of the natural numbers with just exponentiation. To each ...
- 21.2k
9
votes
1
answer
759
views
What classes of groups can arise as "symmetry groups of terms"?
Let $\mathfrak{A}$ be an algebra (in the sense of universal algebra). To each term $t(x_1,...,x_n)$ in the language of $\mathfrak{A}$ in which each variable actually appears we can assign a group $G_\...
- 21.2k
29
votes
2
answers
794
views
Does $\mathrm{SO}(3)$ act faithfully on a countable set?
Let $\mathrm{SO}(3)$ be the group of rotations of $\mathbb{R}^3$ and let $S_\infty$ be the group of all permutations of $\mathbb{N}$. Is $\mathrm{SO}(3)$ isomorphic to a subgroup of $S_\infty$?
This ...
- 1,689
8
votes
1
answer
896
views
Quantifier elimination for abelian groups
In the Wikipedia article (https://en.wikipedia.org/wiki/Quantifier_elimination#cite_note-4) it is said that every abelian group has quantifier elimination property and a long old paper of W. Szmielew ...
- 2,233
4
votes
1
answer
103
views
Computable change in minimum word length of subgroup elements
Let $G$ be an infinite finitely generated group. Fix a finite generating set for $G$.
Define $\mathrm{len}_G:G\to\mathbb{Z}_{\geq 0}$ by sending $g$ to the minimum length of a word in the generators ...
user178109
9
votes
0
answers
108
views
Decidable membership for subgroup generated by three elements in $F_2\times F_2$
Let $F_2$ be the non-abelian free group on two generators. Let $G\subset F_2\times F_2$ be a subgroup generated by three elements. Is there an algorithm deciding if a given element of $F_2\times F_2$ ...
user178109
5
votes
1
answer
87
views
Equality to a power of a given word undecidable in finitely presented group with decidable word problem
Let $G$ be a group with an explicit finite presentation. Assume $G$ has a decidable word problem.
Can there exist an explicit word $w\in G$ such that there is no algorithm deciding if a given word $w'\...
user178109
6
votes
1
answer
150
views
Empty preimage under homomorphism of finitely presented groups with decidable word problems
Let $f:G\to H$ be a homomorphism of finitely presented groups with decidable word problems.
Assume you are given explicit finite presentations for both $G$ and $H$ and you are given the words to which ...
user178109
12
votes
1
answer
468
views
Is the diagonal of finitely presented groups computable?
Let $f:G\to H$ be a surjective homomorphism of finitely presented groups. If the kernel of $f$ is finitely generated then is $G\times_H G$ is a finitely presented group? Can one compute an explicit ...
user178109
15
votes
2
answers
916
views
Element being trivial in a finitely presented group independent of ZFC
Is there an explicit finitely presented group $G$ and an element $g\in G$ such that the statement "$g$ is equal to the identity" is independent of ZFC?
user178109
5
votes
1
answer
146
views
Empty preimage under homomorphism of finitely presented groups independent of ZFC
Is there a homomorphism of finitely presented groups $f:G\to H$ and an element $h\in H$ such that the statement "$f^{-1}(h)$ is empty" is independent of ZFC?
user178109
2
votes
0
answers
71
views
Empty preimage under homomorphism of finitely presented groups with decidable word problems
Let $G, H$ be finitely presented groups with decidable word problems.
Can there be a homomorphism $f:G\to H$ such that there is no algorithm deciding given $w\in H$ whether $f^{-1}(w)$ is empty or not?...
user178109
7
votes
1
answer
143
views
Is there a pseudofinite group with a quantifier-free instance of the order property?
Recall that a group $G$ is pseudofinite if every first-order sentence $\varphi$ (in the language of groups) satisfied in $G$ is also satisfied in some finite group. Also recall that an instance of the ...
- 12.5k
6
votes
0
answers
294
views
Independence results on pure algebra
I think that the most celebrated result in this direction is Shelah's famous work on Whitehead's Problem:
Is every abelian group $A$ such that $Ext^1(A, \mathbb{Z})=0$ free?
This is known to be ...
- 3,318
11
votes
0
answers
564
views
Isomorphic free groups have bijective generating sets
Let $F(X)$ be the free group on a set $X$. Classically, we can prove the statement:
$F(X) \cong F(Y)$ if and only if $|X|=|Y|$.
The proofs (that I have seen) consist of turning the group ...
- 1,185
12
votes
2
answers
583
views
Do there exist acyclic simple groups of arbitrarily large cardinality?
Recall that a group $G$ is acyclic if its group homology vanishes: $H_\ast(G; \mathbb Z) = 0$. Equivalently, $G$ is acyclic iff the space $BG$ is acyclic, i.e. $\tilde H_\ast(BG;\mathbb Z) = 0$.
In ...
- 63.9k
5
votes
0
answers
170
views
How much choice is required for a countably-infinite index subgroup of the real additive group?
The existence of such subgroups implies the existence of a non-measurable set; simply intersect each of the cosets with $[0,1]$. The results will all have equal outer measure, but their union will be ...
- 1,252
8
votes
2
answers
585
views
Is the equational theory of groups axiomatized by the associative law?
Consider the class of groups in the signature {*}. Is the equational theory of that class axiomatized by the associative law? I asked this on math stack exchange but I didn't receive a satisfactory ...
- 2,013
6
votes
2
answers
186
views
What can the approximation of a group by some class be used for?
Recall the following concept due to Malcev and Gromov. Let $C$ be some class of groups. A group $G$ is said to be approximable by the class $C$ if for every finite symmetric subset $F\subset G$ ...
- 163
17
votes
2
answers
2k
views
Why are model theorists so fond of definable groups?
My PhD was on so called "pure" model theory, and my advisor was not very much interested in applications of model theory to algebra. Now I feel the need to fill in the gap, and I'd like to educate ...
- 1,031
0
votes
0
answers
147
views
Groups implementable by finite field
I'm interested in finding all groups for which the group operation (and inverse map) may be implemented using finite field arithmetic.
I've done some searching and have come across "algebraic groups",...
7
votes
1
answer
601
views
Action of infinite symmetric groups on iterated power sets
Let $X$ be an infinite set, and $k \ge 1$ be a natural number. We work without the axiom of choice.
Let $G_0$ be the full symmetric group on $X$, and let $G_1$ be the
full symmetric group on ${\cal ...
- 1,615
10
votes
0
answers
438
views
On the Number of Parallel Automorphism Lines
Given a group $G$, one can define the transfinite line of iterative automorphisms of $G$ to be the following chain of the groups where $G_{\alpha+1}=Aut(G_{\alpha})$ for each ordinal $\alpha$ and the ...
35
votes
7
answers
4k
views
Paradoxical Mathematical Objects Pending for Construction [duplicate]
The possible properties and applications of some mathematical objects have been described far before their rigorous mathematical definition. Some of them even had a seemingly paradoxical description ...
33
votes
1
answer
1k
views
Is this conjecture strictly weaker than P=NP?
My three computability questions are related to the following group theory question (first asked by Bridson in 1996):
For which real $\alpha\ge 2$ the function $n^\alpha$ is equivalent to the Dehn ...
user6976
10
votes
1
answer
1k
views
The Tall Tale of Terminating Transfinite Towers
The transfinite tower of iterative automorphisms of a group $G$ is simply definied to be the following chain of the groups where $G_{\alpha+1}=Aut(G_{\alpha})$ for each ordinal $\alpha$ and the direct ...
39
votes
4
answers
4k
views
The symmetric group theory of natural numbers
Sometimes it is not easy to formulate a correct question. Here is a better version of this question (I still do not know if it is optimal, but it is better than the previous one).
We say that a set $...
user6976
5
votes
1
answer
511
views
Translating first order statements about symmetric groups into the language of numbers and back
A question I was asked recently lead me to the following question. For every closed first order formula $\theta$ in the group signature consider the set $N_\theta$ of natural numbers $n$ such that the ...
user6976
4
votes
3
answers
279
views
Closed free subgroups of the automorphism group of the countable atomless boolean algebra
Let $\mathcal{B}$ be the (unique up to isomorphism) countable atomless boolean algebra, and $\mathrm{Aut}(\mathcal{B})$ its automorphism group, with pointwise convergence topology.
My question: Does $...
- 3,115
7
votes
0
answers
177
views
Countable elementary sub-structure of the automorphism group of the binary rooted tree
Let $G$ be the automorphism group of the binary rooted tree.
The downward Löwenheim-Skolem theorem states that G has a countable elementary sub-structure.
My question is whether such sub-structure ...
- 1,378
2
votes
1
answer
190
views
Logic article on first-order invariants of abelian groups
I remember reading an article published in the 1970s by a Polish mathematician describing the first-order invariants of a torsion-free abelian group. I do not recollect the author's name, the title of ...
- 116
6
votes
2
answers
461
views
Automorphism of the transfinite rooted binary tree
I was studying combinatorical group theory recently, and I came across the infinite regular rooted binary tree and its automorphism group $Aut(T^{(2)})$with the Grigorchuk subgroup.
Let me now ...
- 3,738
10
votes
1
answer
382
views
Wiener's axiomatization of the group law based on division
Gian-Carlo Rota wrote that [*]:
Wiener axiomatized the group law by taking $xy^{-1}$ as the basic operation, and his axiomatization is quite different from any of the other axiom systems for groups....
- 3,393
9
votes
1
answer
276
views
First order formulas for finite groups and invariant theory
Let $G$ be a finite group, and let $K$ be a field of characteristic zero.
Let $\phi(x_1,\ldots,x_n)$ be a first order formula in the language of group theory (so $\phi$ can be for example something of ...
- 5,039
9
votes
1
answer
339
views
Finite and infinite 4-regular vertex-transitive graphs with identical $R$-balls
Consider the set of all 4-regular connected vertex-transitive graphs.
By compactness, for every integer $R \ge 0$, there is an integer $N_R$, so that for every 4-regular vertex-transitive graph of ...
- 91
15
votes
2
answers
972
views
Elementary subgroups of surface groups
From Sela's proof of Tarski's conjecture we know that the surface groups (i.e. fundamental group of a closed surface of genus $\geq 2$) and free (non-abelian) groups have the same first order theory. ...
- 1,713
6
votes
2
answers
706
views
Non-trivial problems about the trivial group
Is there any non-trivial problem (maybe open problem) about the trivial group?
I asked already a question about the Laws characterizing the trivial group. There is a description of such laws. As ...
- 2,233