A cardinality version of Beigel's nonspeedup theorem
- 1 September 1989
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 54 (3) , 761-767
- https://doi.org/10.2307/2274739
Abstract
If S is a finite set, let ∣S∣ be the cardinality of S. We show that if m ∈ ω, A ⊆ ω, B ⊆ ω, and ∣i: ≤ i ≤ 2m & xi ∈ A}∣ can be computed by an algorithm which, for all x1, …, x2m, makes at most m queries to B, then A is recursive in the halting set K. If m = 1, we show that A is recursive.Keywords
This publication has 3 references indexed in Scilit:
- Kenneth Kunen. Set theory. An introduction to independence proofs. Studies in logic and the foundations of mathematics, vol. 102. North-Holland Publishing Company, Amsterdam, New York, and Oxford, 1980, xvi + 313 pp.The Journal of Symbolic Logic, 1986
- Members of countable π10 classesAnnals of Pure and Applied Logic, 1986
- Degrees of Unsolvability: Structure and TheoryLecture Notes in Mathematics, 1979