Remote Access Proceedings of the American Mathematical Society
Green Open Access

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
DOI: https://doi.org/10.1090/S0002-9939-1981-0597664-7
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: https://doi.org/10.1090/S0002-9939-1981-0597664-7
Article copyright: © Copyright 1981 American Mathematical Society