slideshow 3

Logic seminar

On the complexity of Friedman's Free-set Theorem and Thin-set Theorem

Marcello Stanisci
Sapienza University of Rome

 

Monday, 12. January 2015 - 13:30
IM, rear building, ground floor
Free-set Theorem (FST) and Thin-set Theorem (TST), both belonging to the second-order family, have been introduced by H. Friedman in a work called Boolean Relation Theory, that is aimed to find independence results under strong systems of Set Theory. This talk exposes two principles, called LTST and FFST, that are first-order adaptions of FST and TST. In particular, we will see some independence results of LTST and a linear lower bound for FFST. Before presenting the main results, there will be an overview of some known facts that motivated such a research of unprovability, as well as a comparison between FST, TST and the classical Ramsey's Theorem.