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

DOI: http://dx.doi.org/10.1090/S0002-9939-1981-0597664-7
PII: S 0002-9939(1981)0597664-7
Article copyright: © Copyright 1981 American Mathematical Society