Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)


Speed-up by theories with infinite models

Author: R. Statman
Journal: Proc. Amer. Math. Soc. 81 (1981), 465-469
MSC: Primary 03F20
MathSciNet review: 597664
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that if $ S$ is a finite set of schemata and $ A$ is a sentence undecided by $ S$ such that $ S \cup \{ {\neg A} \}$ has an infinite model then $ S \cup \{A \}$ is an unbounded speed-up of $ S$ for substitution instances of tautologies. As a corollary, we obtain a conjecture of Parikh's.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03F20

Retrieve articles in all journals with MSC: 03F20

Additional Information

PII: S 0002-9939(1981)0597664-7
Article copyright: © Copyright 1981 American Mathematical Society