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
MathSciNet review: 597664
Full-text PDF

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?)

  • [1] G. Kreisel and H. Wang, Some applications of formalized consistency proofs, Fund. Math. 42 (1955), 101-110. MR 0073539 (17:447g)
  • [2] R. Parikh, Some results on the length of proofs, Trans. Amer. Math. Soc. 177 (1973), 29-36. MR 0432416 (55:5404)
  • [3] R. Statman, Proof-search and speed-up in the predicate calculus, Ann. Math. Logic 15 (1978), 225-287. MR 528658 (81c:03049)

Similar Articles

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

Retrieve articles in all journals with MSC: 03F20

Additional Information

Article copyright: © Copyright 1981 American Mathematical Society

American Mathematical Society