Hugo D. Macedo (TecMF/DI/PUC-Rio)
Yoneda's Embedding and Post-Completeness
There are several definitions of completeness in the field of logic. This work surveys such definitions and studies a particular one that arose from the work of Emil Post and became known as Post completeness. Such study allows us to differentiate Post completeness, which acts as a classifier of logics in terms of extensibility, from traditional completeness, a relation between semantics and syntax.
We further proceed by showing that Hilbert's proof of Post completeness for the case of classical propositional logic is an instance of the Yoneda lemma, a meta-mathematical result in the field of category theory, thus allowing a proof in a categorical setting. At last we also discuss an interpretation of the lemma which prescribes a theorem logic tautologies satisfy. Such theorem is also present in Hilbert's proof, thus making the lemma doubly useful in our study.