|
Question Details:
When calling a set A “decidable”, we frequently let the background context supply which superset B ⊇ A that A is decidable with respect to. Awareness of which set B is in question is important, though. Show that there exist subsets A, B, and C of ω such that A is decidable with respect to B, but A is not decidable with respect to C.
For the record, our courses defintion of a 'decidable set' is a set with a computable characteristic function. If A is a subset of B, the characteristic
function of A (with respect to B) is X: B -> {0,1}:
X(b) = 1, if b
belongs to A; 0, if otherwise
Lastly, ω is the set of natural numbers.
|