Separability in Classical Natural Deduction

Abstract

Esta dissertação investiga a propriedade de separabilidade em sistemas de dedução natural para a lógica proposicional clássica. A propriedade da separabilidade afirma que, dado um sistema S, S é separável se, sempre que Π é uma Dedução Normal de A a partir de Γ em S, então as únicas regras de inferência que são aplicadas em Π são as regras de inferência para as constantes lógicas que ocorrem em A ou em alguma fórmula de Γ. A propriedade de separabilidade está intimamente relacionada à propriedade do subfórmula. De fato, a separabilidade é um corolário da propriedade do subfórmula, mas o inverso não é verdade. Existem sistemas para a lógica proposicional clássica em dedução natural que são separáveis, mas não têm a propriedade do subfórmula. Isso instiga uma discussão sobre graus de analiticidade, onde a propriedade do subfórmula gera um sentido mais forte de analiticidade do que a propriedade de separação. O primeiro capítulo da dissertação foca na história dos sistemas de dedução natural, de Gentzen e Jáskowski a Prawitz. O segundo capítulo foca na propriedade de separabilidade e contém (I) uma história do teorema de separabilidade para a lógica intuicionista, (II) uma discussão sobre separabilidade em sistemas de dedução natural para a lógica proposicional clássica e, (III) uma discussão sobre diferentes graus de analiticidade. O terceiro capítulo foca em sistemas separáveis para a lógica proposicional clássica que são obtidos a partir de um sistema intuicionista pela adição de regras estruturais. O quarto capítulo foca no desenvolvimento de um sistema de dedução natural separável para a lógica proposicional clássica que é obtido através da adição de uma regra implicacional a um sistema de dedução natural intuicionista. O sistema NH é obtido através da adição da regra do Hosoi ((A → B) → B), (A → C), (B → C) ⊢ C ao fragmento proposicional do sistema NJ de Gentzen. Os principais resultados desta dissertação foram (I) o desenvolvimento do sistema NH, (II) o desenvolvimento de um procedimento de normalização para o sistema NH, e (III) a classificação de diferentes sistemas em três graus de analiticidade: (i) sistemas não analíticos (sistemas que não têm nem a propriedade do subfórmula nem são separáveis), (ii) Sistemas Estritamente Analíticos (sistemas que são separáveis, mas não têm a propriedade do subfórmula) e (iii) sistemas Ultra Estritamente Analíticos (sistemas que são separáveis e têm a propriedade do subfórmula).