Raphael Carroy : Some finite basis results for quasi-orders

Posted by Filippo Calderoni , part of the Logic Seminar.

At

April 6, 2021, 11 a.m.

In

Zoom

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.