##
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