Sesión Lógica y ComputabilidadLa bisimilitud entre árboles de rango $\omega+2$ no es suave
Pedro Sánchez Terraf
Universidad Nacional de Córdoba -- CIEM-FAMAF, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Es bien sabido que la lógica modal básica ($\mathsf{BML}$) caracteriza la relación de bisimilitud entre marcos de Kripke punteados tales que cada punto tiene finitos sucesores por cada relación de accesibilidad. Es decir, si los “puntos'' de sendos marcos satisfacen las mismas fórmulas de $\mathsf{BML},$ entonces existe una bisimulación entre estos últimos que contiene el par de aquellos. También existen contraejemplos estándares a esta caracterización lógica cuando alguna relación de accesibilidad tiene infinitos sucesores. A su vez, esto se soluciona permitiendo conjunciones (y disyunciones) numerables, obteniendo la lógica infinitaria $\mathsf{BML}_\omega$. Esta lógica tiene una cantidad incontable de fórmulas, y es de interés saber si algún fragmento contable es suficiente para caracterizar la bisimilitud.
En esta comunicación veremos que aún restringiéndose a cierta familia de marcos bien fundados y de “profundidad'' acotada (como en el título), no existe un tal fragmento contable. La prueba utiliza conceptos básicos de Teoría de Conjuntos Descriptiva.
Trabajo en conjunto con: Martín Moroni (Universidad Nacional de Córdoba).