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 ...
- 16.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 ...
- 1,851
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 "...
CommunityBot
- 1
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 ...
- 47.3k
84
votes
3
answers
6k
views
How do I verify the Coq proof of Feit-Thompson?
I probably don't have the appropriate background to even ask this question. I know next to nothing about formal or computer-aided proof, and very little even about group theory. And this question is ...
- 82.7k
6
votes
3
answers
872
views
An element $g$ in a group such that neither $g=1$ nor $g\ne 1$ can be proved.
Edited (this question contains two versions of a similar question)
Is there some finitely presented group $G$ generated by $g_1,...,g_n$ such that
there is an element $g\in G$ expressed as a finite ...
- 236k
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 "...
- 20.5k
8
votes
1
answer
338
views
How bad can the recursive properties of finitely presented groups be?
Any finitely presented group naturally gives rise to an edge-labeled graph (the Cayley graph) and I am considering paths through this graph. Paths correspond to infinite sequences of generators, so ...
- 236k
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-...
- 55.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 ...
- 47.3k
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 ...
- 63.9k
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 ...
- 47.3k
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_\...
- 20.5k
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 ...
- 20.5k
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 ...
- 1,832
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 ...
- 63.9k
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 ...
CommunityBot
- 1
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 ...
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$ ...
CommunityBot
- 1
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'\...
- 38.6k
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 ...
CommunityBot
- 1
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?
- 236k
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?
- 236k
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?...
CommunityBot
- 1
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 ...
- 3,274
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,689
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
9
votes
1
answer
911
views
An ubiquitous pattern of questions
There is an ubiquitous pattern of questions concerning assumedly any kind of mathematical object or structure: groups, graphs, numbers, categories, and so on. It goes like this (informally):
Can a ...
CommunityBot
- 1
10
votes
2
answers
611
views
Normal subgroups of automorphism group of relational structure
Let $S$ be the set of all finite permutations of $\mathbb{N}$, i.e. they fix all but a finite set, and $A\subset S$ the set of all even permutations.
Theorem. The normal subgroups of $S_\infty$ are ...
- 63.9k
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
621
views
Eliminating constant in Rado graph
Let $R$ denote the Rado graph, and let $c$ be a fixed vertex.
Question 1. Is the structure obtained by extending $R$ by the constant $c$ interpretable in $R$ without parameters?
By interpretable I ...
- 63.9k
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 ...
- 4,713
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 ...
- 63.9k
22
votes
6
answers
2k
views
Is any interesting question about a group G decidable from a presentation of G?
We say that a group G is in the class Fq if there is a CW-complex which is a BG (that is, which has fundamental group G and contractible universal cover) and which has finite q-skeleton. Thus F0 ...
- 38.6k
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 ...
- 63.9k
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$ ...
- 21.3k
39
votes
5
answers
4k
views
A “mother of all groups”? What kind of structures have "mother of all"s?
For ordered fields, we have a “mother of all ordered fields”, the surreal numbers $\mathbf{No}$, a proper-class “field” which includes (an isomorphic copy of) every other ordered field as a subfield. ...
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",...
- 63.9k
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 ...
CommunityBot
- 1
2
votes
4
answers
555
views
relatively free groups in $Var(S_3)$
Suppose $S_3$ is the symmetric group of order 6. Which elements of the variety $Var(S_3)$ are relatively free?
This question is related to my previous question
Relatively free algebras in a variety ...
- 63.9k
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 ...
CommunityBot
- 1
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 ...
CommunityBot
- 1
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 ...
- 612
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 ...
CommunityBot
- 1
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 $...
- 1,105