Decidability of the Membership problem

132 Views Asked by At

Good day!

I have the following question.

Given a subset S ⊆ N = {0, 1, 2...}, the S-Membership problem asks "Given a number n ∈ N, is n in S"?

We call the set S decidable iff its S-membership problem is decidable.

Let S1, S2 ⊆ N and assume that S1 and S2 are both decidable.

Let S3 = {x + y | x ∈ S1 and y ∈ S2}.

So, I want to prove that the set S3 is decidable. My approach:

  1. Let x = g + t. where x, g, t ∈ N be given
  2. Check if g belongs to either S1 or S2(that is possible cause S1 and S2 Membership problems are decidable). If no, return "no".
  3. Check if t belongs to either S1 or S2. If no, return "no".
  4. Otherwise, return "yes".

Is it the right approach?

Thanks!