For a complexity measure $\kappa$, a set is $\kappa$-infinite if it contains a $\kappa$-decidable infinite subset. For a time-based $\kappa$, we prove that there is a recursive S s.t. both S and its complements, $S¯$, are infinite but not $\kappa$-infinite. Lipton [6] states that the existence of a recursive set S s.t. neither S nor $S¯$ os polynomially infinite is not a purely logical consequence of $\prod 20$ theorems of Peano's Arithmetic PA. His proof uses a construction of an algorithm within a non-standard model of of Arithmetic, in which the existence of infinite descending chains in such models is overlooked. We give a proof of a stronger statement to the effect that the existence of a recursive set S s.t. neither S nor $S¯$ is linearly infinite is not a tautological consequence of all true $\prod 20$ assertions. We comment on other aspects of [6], and show $(\S 2)$ that a tautological consequence of true $\prod 20$ assertions may not be equivalent (in PA, say) to a $\prod 20$ sentence. The three sections of this paper use techniques of Recursion Theory, Proof Theory and Model Theory, respectively.