show that this decidable set $C$ exists
No, it is not necessarily recursively enumerable.  There are languages that are recursively enumerable but not recursive.  Thus, their complement is not recursively enumerable.  From that, you should be able to prove that the answer to the question in the final sentence of your post is no (I'll let you fill in the details from there).