On Easily Infinite Sets and On a Statement of R. Lipton
| dc.contributor.author | Leivant, Daniel | en_US |
| dc.date.accessioned | 2007-04-23T18:24:29Z | |
| dc.date.available | 2007-04-23T18:24:29Z | |
| dc.date.issued | 1979-09 | en_US |
| dc.description.abstract | 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, $\bar{S}$, are infinite but not $\kappa$-infinite. Lipton [6] states that the existence of a recursive set S s.t. neither S nor $\bar{S}$ os polynomially infinite is not a purely logical consequence of $\prod^{0}_{2}$ 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 $\bar{S}$ is linearly infinite is not a tautological consequence of all true $\prod^{0}_{2}$ assertions. We comment on other aspects of [6], and show $(\S 2)$ that a tautological consequence of true $\prod^{0}_{2}$ assertions may not be equivalent (in PA, say) to a $\prod^{0}_{2}$ sentence. The three sections of this paper use techniques of Recursion Theory, Proof Theory and Model Theory, respectively. | en_US |
| dc.format.extent | 735667 bytes | |
| dc.format.extent | 301737 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR79-390 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/7504 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | On Easily Infinite Sets and On a Statement of R. Lipton | en_US |
| dc.type | technical report | en_US |