Logic Seminar
Raphael Carroy
University of Turin
Some finite basis results for quasi-orders
Abstract: What is a finite basis result for a quasi-order? A quasi-order is a transitive and reflexive relation on a set (or a class). Given a quasi-order $\leq_Q$ on a set $Q$ and a subset $A$ of $Q$, a basis for $A$ is a subset $B$ of $A$ such that for all $a \in A$ there exists $b \in B$ so that $b \leq_Q a$. The quasi-order $\leq_Q$ has a symmetrization: $p \equiv_Q q$ if and only if $p \leq_Q q$ and $q \leq_Q p$, which is an equivalence relation. We say that the basis $B$ is finite if its quotient by $\equiv_Q$ is finite.
We consider the existence of a morphism between two structures in a given class as a quasi-order on the class of structures. I will talk about some finite basis results on classes of graphs and classes of functions for various notions of morphisms, and the interplay between them.
Tuesday April 6, 2021 at 11:00 AM in Zoom