Č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

# Uniform bound on the size of support of a witness

Let be an equivariant relation. We show that under a certain assumption on , for every , if there exists a witness such that holds, then there also exists one with small support. We show an application to extending homomorphisms.

# Orbit finiteness vs. number of supported elements

A set is orbit finite if and only if the number of its elements supported by atoms grows polynomially with .

# Color-preserving automorphisms in Fraisse classes (new version)

Again, a question closely related to a characterization of *standard atoms* (not to be confused with standard alphabets:). The question is a refinement of a question posted in Automorphisms vs color-preserving automorphisms in Fraisse classes, which has been answered negatively (see the recent post The colored open question closed).

# The colored open question closed

A question in my recent post Automorphisms vs color-preserving automorphisms in Fraisse classes has been answered negatively by Mikołaj. The counterexample Fraisse class is the age of the structure , the rational numbers with the ternary ‘cyclic order’ relation defined by:

I am about to reformulate the question slightly, in order to make refutation harder;)

# A stronger Kleene theorem

This post continues the discussion on the Kleene theorem from here. The previous post gave a notion of regular expressions that had the same expressive power as nondeterministic automata. The idea was that a star corresponds to a graph where the set of vertices had one orbit, and where the edges where labelled by simpler regular expressions. In the case without atoms, such a graph is necessarily a self loop, which corresponds to the standard Kleene star. This post is about a stronger requirement: instead of saying that the graph has one orbit of vertices, we say that it has one orbit of edges.

# Automorphisms vs color-preserving automorphisms in Fraisse classes

Here is a question closely related to a characterization of *standard atoms* (not to be confused with standard alphabets:). It asks whether a bound on the number of automorphisms is equivalent to a bound on the numer of color-preserving automorphisms, in every Fraisse class of finite relational structures.

# Normalization of pp-formulas

Classicaly, primitive positive formulas form the smallest fragment of first-order logic which is closed under conjunction and existential quantification. Pp-formulas can be turned in to a normal form – this is due to Skolemization, i.e. the fact that can be turned into . In this case, Skolemization is a consequence of the axiom of finite choice.

We show that in the world with atoms, not every orbit-finite pp-formula can be converted into an equivalent one in prenex form. This is another demonstration of the failure of the axiom of choice.

This raises the question: what is the appropriate notion of a pp-formula, which does have normal forms?

# The Rum Conjecture is refuted

A conjecture I posted a while ago, concerning reachability of states in automata with atoms after a Brzozowski phase, has been refuted by Mikołaj Bojańczyk.