Speed-up by theories with infinite models
Rick Statman · Proceedings of the American Mathematical Society · 1981
We prove that if $S$ is a finite set of schemata and $A$ is a sentence undecided by $S$ such that $S \cup \{ { eg 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.