Reports on Mathematical Logic

No. 25 (1991)


Adam KOLANY and Piotr WOJTYLAK

RESTRICTED VERSIONS OF THE COMPACTNESS THEOREM

A b s t r a c t. Certain restricted versions of CT, the Compactness Theorem for propositional logic, are introduced by imposing additional conditions on the number of occurrences of propositional variables in sets of formulas. In addition we also consider corresponding versions of some equivalents of CT. The introduced versions turn out to be neither provable in ZF set theory nor equivalent to BPI, the Boolean Prime Ideal theorem. The question of their equivalence to $AC_fin$, the Axiom of Choice for finite sets, is left open. The restricted versions of CT were suggested by Robert Cowen in connection with his work: Two hypergraph theorems equivalent to BPI, Notre Dame Journal of Formal Logic 31(1990), 232-240, on intimate relations between BPI and NP - complete decision problems.


Back to Main Menu