All Questions
11 questions
4
votes
2
answers
544
views
Membership problem in monoids
What is the simplest example of a monoid with undecidable membership problem? In other words, I'm looking for a concrete monoid $S$ such that there is no algorithm which takes elements $s_1,...,s_n$ ...
- 236k
1
vote
1
answer
142
views
Congruences that aren't "finite from above," take 2: semigroups
This is a hopefully less trivial version of this question. Briefly, say that a congruence is parafinite if it is the largest congruence contained in some equivalence relation with finitely many ...
- 38.6k
4
votes
0
answers
170
views
Corollaries of Kleene's Theorem (Regular Languages)
Kleene's theorem that finite automata (specifically, nondeterministic) are expressively equivalent to regular expressions seems to be a powerful and not immediately obvious tool for untangling the ...
- 429
13
votes
1
answer
623
views
Ultracategories with one object
Historically, the theory of ultracategories was invented by Makkai to prove a strong conceptual completeness theorem for first-order logic, roughly: if $T$ and $S$ are two first-order theories such ...
- 15.8k
5
votes
1
answer
227
views
"Tietze-like transformations" for defining interesting bijections between algebraic structures
Consider the following two definitions of the natural numbers:
The natural numbers are the algebraic structure $\mathbb{N}_1$ generated by one constant, $0$ and one unary function, $S$ (and no ...
- 10.7k
5
votes
3
answers
576
views
Is the class of power-associative binars finitely axiomatizable?
A binar is simply a set $S$ equipped with a single binary operation $*$. A power-associative binar is a binar where the subalgebra generated by a single element is associative. Equivalently, they can ...
- 14.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
1
vote
2
answers
339
views
Are monoids with zero and partial homomorphisms related?
Context: Let $\Sigma=\{U,C,A,G\}$ and $L\subset\Sigma^*$, i.e. $L$ is a language over the alphabet $\Sigma$. Let $\Sigma'=\{0,1\}$ and define a homomorphism $f:\Sigma^*\to\Sigma'^*$ by extending $U \...
CommunityBot
- 1
2
votes
0
answers
272
views
Continuity of multiplicative character
Let $G$ be a discrete group and $\beta (G)$ denote the Stone-Cech compactification of $G$, a right topological semigroup. By a multiplicative character, I mean a mapping that preserves multiplication ...
CommunityBot
- 1
3
votes
1
answer
529
views
Study of free monoids of the recursive S. Eilenberg.
Compared to the usual treatises on recursion (eg, Rogers H. "Computability and Undecidability." McGraw-Hill, New York) the book of Samuel Eilenberg & Calvin C. Elgot "Recursiveness" treats such ...
- 6,210
8
votes
2
answers
427
views
Is there a general result that theorems about finite structures proved in ZFC can be proved in ZF?
The title question is too vague so let me be specific.
Much of modern finite semigroup theory uses profinite semigroups and properties of profinite semigroups that depend on the existence of prime ...
- 44.4k