In this paper we investigate some of the recursion-theoretic problems which are suggested by the logical notion of independence.

A set S of natural numbers will be said to be k-independent (respectively, ∞-independent) if, roughly speaking, in every correct system there is a k-element set (respectively, an infinite set) of independent true sentences of the form x ∈ S. S will be said to be effectively independent (respectively, absolutely independent) if given any correct system we can generate an infinite set of independent (respectively, absolutely independent) true sentences of the form x ∈ S.

We prove that

(a) S is absolutely independent ⇔S is effectively independent ⇔S is productive;

(b) for every positive integer k there is a Π1 set which is k-independent but not (k + 1)-independent;

(c) there is a Π1 set which is k-independent for all k but not ∞-independent;

(d) there is a co-simple set which is ∞-independent.

We also give two new proofs of the theorem of Myhill [1] on the existence of an infinite set of Σ1 sentences which are absolutely independent relative to Peano arithmetic. The first proof uses the existence of an absolutely independent Π1 set of natural numbers, and the second uses a modification of the method of Gödel and Rosser.