# Orbit-finite dimensional vector spaces, and orbit-finite systems of linear equations

Here is some naive questions that came to one’s mind when considering vector spaces where the dimension is not finite but orbit-finite: under a reasonable assumption on atoms , say -categoricity,

— is it true that every vector subspace of an orbit-finite dimensional vector space is orbit-finite dimensional?

— is it true that the set of solutions of an orbit-finite  system of linear equations is orbit-finite dimensional?

# Orbit-finite 0-simple semigroups

We ask the question of how the Rees-Suskevitch theorem should be generalised to provide representations of orbit-finite 0-simple semigroups. We believe that orbit-finite groupoids will be useful for this.

# Orbit-finite groupoids

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.

# 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.

# 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.