Abstract
Methods originating in theoretical computer science for showing that certain decision problems are NP-complete have also been used to show that certain compactness theorems are equivalent in ZF set theory to the Boolean Prime Ideal Theorem (BPI). Conversely, there is some evidence that set theoretic methods connnected with research on BPI may prove useful in computer science. We survey what is known and then look at some new examples and explore the underlying reasons for the successful application of quite similar methods to solve different problems.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
A. Abian: Generalized completeness theorem and solvability of systems of boolean polynomial equations, Zeitschrift für Mathematische Logik, 16(1970), 263–264.
B. Banaschewski: The power of the ultra-filter theorem, Journal of the London Mathematical Society, ser. 2, 27(1983), 193–202.
R. Cowen: Some combinatorial theorems equivalent to the prime ideal theorem, Proceedings of the American Mathematical Society, 41(1973), 268–273.
R. Cowen: Partition principles for properties of finite character, Reports on Mathematical Logic, 14(1982), 23–28.
R. Cowen: Compactness via prime semilattices, Notre Dame Journal of Formal Logic, 24(1983), 199–204.
L. Cowen, R. Cowen, D. Woodall: Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency, J. Graph Theory, 10(1986), 187–195.
R. Cowen: Two hypergraph theorems equivalent to BPI, Notre Dame Journal of Formal Logic, 31(1990), 232–239.
R. Cowen: Hypergraph Satisfiability, Reports on Mathematical Logic, 24(1991), 113–118.
R. Cowen: Combinatorial Analytic Tableaux, to appear.
M. Frick: A survey of (m,k)-colorings. In J. Gimbel, J.W. Kennedy, L.V. Quintas (eds.): Quo Vadis, Graph Theory? (Annals of Discrete Math 55), North Holland, 1993.
M. Garey, D. Johnson: Computers and Intractability, W. H. Freeman, San Francisco, 1979.
L. Henkin: Boolean representation through propositional calculus, Fundamenta Mathematica, 41(1954), 89–96.
P. Howard: Binary consistent choice on pairs and a generalization of König's infinity lemma, Fundamenta Mathematica, 121(1983), 31–37.
P. Howard: Weak forms of the Axiom of Choice, unpublished.
T. Jech: The Axiom of Choice, North Holland, Amsterdam, 1973.
A. Kolany: Satisfiability on hypergraphs, Studia Logica, to appear.
A. Kolany, P. Wojtylak: Restricted versions of the compactness theorem, Reports on Mathematical Logic, 25(1991), 91–103.
H. Läuchli: Coloring infinite graphs and the Boolean prime ideal theorem, Israel Journal of Mathematics, 9(1971), 422–429.
A. Levy: Remarks on a paper by J. Mycielski, Acta Mathematica Academiae Sceintiarum Hungaricae, 14(1963), 125–130.
J. Łós, C. Ryll-Nardzewski: On the application of Tychonoff's theorem in mathematical proofs, Fundamenta Mathematica, 38(1951), 233–237.
J. Łós, C. Ryll-Nardzewski: Effectiveness of the representation theory for Boolean algebras, Fundamenta Mathematica, 41(1955), 49–56.
J. Mycielski: Some remarks and problems on the coloring of infinite graphs and the theorem of Kuratowski, Acta Mathematica Academiae Scientiarum Hungaricae, 14(1963), 125–130. Errata, ibid., 18(1967), 339–340.
J. Mycielski: Two remarks on Tychonoff's product theorem, Bulletin Academie Polonaise des Sciences, 12(1964), 439–441.
Y. Rav: Variants of Rado's Selection Lemma, and their applications, Mathematische Nachrichten, 79(1977), 145–165.
H. Rubin, D. Scott: Some topological theorems equivalent to the Boolean prime ideal theorem, Bulletin of the American Mathematical Society, 60(1954), 389.
T. Schaefer: The complexity of satisfiability problems, Proceedings of the 10th Annual ACM Symposium on the Theory of Computing, 216–226, 1978.
T. Schaefer: Complexity of decision problems based on finite two-person perfectinformation games, Proceedings of the 8th Annual ACM Symposium on the Theory of Computing, 41–49. 1976.
A. Schrijver: The dependence of some logical axioms on disjoint transversals and linked systems, Colloquium Mathematicum, 39(1978), 191–199.
D. Scott: Prime ideal theorems for rings, lattices and Boolean algebras, Bulletin of the American Mathematical Society, 60(1954), p. 390.
L. Stockmeyer: Planar 3-colorability is polynomial complete, SIGACT News 5, 3(July 1973), 19–25.
D. Woodall: Property B and the four-colour problem. In: D.J.A. Welsh, D.R. Woodall(eds.): Combinatorics, IMA, 1972.
D. Woodall: Improper colourings of graphs. In: R. Nelson, R.J. Wilson(eds.): Graph Colourings, Pitman Research Notes in Mathematics Series, Longman Scientific and Technical, 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cowen, R. (1993). Some connections between set theory and computer science. In: Gottlob, G., Leitsch, A., Mundici, D. (eds) Computational Logic and Proof Theory. KGC 1993. Lecture Notes in Computer Science, vol 713. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0022548
Download citation
DOI: https://doi.org/10.1007/BFb0022548
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57184-1
Online ISBN: 978-3-540-47943-7
eBook Packages: Springer Book Archive