Orbit-finite groups are finite, and therefore not very interesting from the perspective of sets with atoms. It turns out that orbit-finite groupoids form interesting structures. They will be useful in the study of orbit-finite semigroups in the following post.
Category Archives: posts
Can orbit-finite semigroups be straightened?
A straight set is an equivariant set which is equivariantly isomorphic to a disjiont union of sets of the form . A straight semigroup is an equivariant semigroup whose universe is a straight set. We raise the following:
Question 1: is every equivariant, orbit-finite semigroup an image of some orbit-finite, straight semigroup under an equivariant mapping?
We show some simple preliminary observations towards the above question.
Orbit-finite CSPs
Consider the following decision problem (for classical Turing machines). Let be a fixed, finite signature.
Input: Two orbit-finite relational structures , over .
Decide: is there a homomorphism from to ?
Question 1. Is the above problem decidable?
Observe that we are not asking for the existence of an equivariant homomorphism. If this were the case, the problem would be clearly decidable, since there are only finitely many equivariant homomorphisms between orbit-finite sets, and they can be effectively scanned. In this problem, the homomorphisms do not even have to be finitely supported! Below is an example where a homomorphism exists, but no finitely supported homomorphism exists.
Example. Consider the equality atoms. Let be the graph whose vertices are pairs of distinct atoms, and in which edges join a pair with its inverse. Let be the -clique. Then maps to , but no finitely supported homomorphism exists.
Following the idea of this post, in order to solve this problem, it might be useful to move to the totally ordered atoms .
Question 2. In the totally ordered atoms, if there is a homomorphism between orbit-finite structures , , is there one which is equivariant?
A positive answer to Question 2 would imply a positive answer to Question 1.
Edit. After reading Bartek’s comment below, I noticed that Question 2 has an even more negative answer. Consider the structures and (orders reversed). There is a homomorphism from to , namely the mapping , but there is none which is finitely supported.
Orbit-finite systems of linear equations
Consider the following decision problem, over the equality symmetry.
Input: an orbit-finite system of linear equations over
Decide: does have a solution (not necessarily finitely-supported)?
Inspired by Eryk’s beautiful solution of this problem, we present another solution, using an amazing theorem from topological dynamics.
Orbit-finite bijections can be smoothed
In his recent post Bartek demonstrated an example of two equivariant sets with atoms that are related by a finitely supported bijection, but not by any equivariant bijection. We show that if the sets are orbit-finite then this situation is impossible.
Proposition. Let and be two orbit-finite equivariant sets with atoms. If there exists a finitely supported bijection then there exists an equivariant bijection .
Continue reading
Join of two elements
Let be two elements with atoms. The pair satisfies the following universal property: supports both and , and if is another element with this property, then supports .
We demonstrate the existence of an element denoted , with a dual property: is supported both by and by , and if is another element with this property, then is supported by . The construction does not require any assumptions on the symmetry.
Some bijections cannot be smoothed
It can happen that two equivariant sets with atoms are related by a finitely supported bijection, but not by an equivariant bijection.
Bipartite graphs without bipartite partition
In the equality symmetry, there is a single-orbit graph with the property that is bipartite in the classical sense (equivalently, has no odd-length cycle) but has no partition into two parts which are finitely supported and not inter-connected. In other words, the graph maps to the single-edge graph via a infinitely-supported homomorphism, but not via a finitely-supported one. And here’s the graph: its nodes are pairs of distinct atoms, and there is an edge from to , whenever are distinct atoms. That’s it.
Decidability results based on a WQO in homogeneous atoms
There are several decision problems for certain computation models with atoms that are decidable when atoms admit certain well quasi order (WQO), and undecidable otherwise. We recall the problems and formulate few questions related to WQOs.
Continue reading
Cohomology groups of the torus
Čech cohomology is a way of defining cohomology groups (a topological invariant with algebraic structure) on a topological space. We give a rough description of the construction, in a very special case of a torus, and relate it to the construction of the nonstandard alphabets. Continue reading