TIFR CSE 2010 | Part B | Question: 40

Question

Which of the following statement is FALSE?

• A. All recursive sets are recursively enumerable.
• B. The complement of every recursively enumerable sets is recursively enumerable.
• C. Every Non-empty recursively enumerable set is the range of some totally recursive function.
• D. All finite sets are recursive.
• E. The complement of every recursive set is recursive.

Comments

what does option c means?

---

(B) Because RE language are not closed under complement.

Answer 1

(B) The complement of every recursively enumerable sets is recursively enumerable.

Because RE language are not closed under complement.

Comments

@Arjun Sir What does this mean ... can you explain with an example ?

1. Every Non-empty recursively enumerable set is the range of some totally recursive function.

---

Can some one please elaborate the option c..

---

Range of a function means the set of all possible output values of the function.

---

Arjun Sir can you please explain option c?

---

Equivalent formulations

The following are all equivalent properties of a set S of natural numbers:

Enumerability:

• The set S is the range of a partial recursive function.
• The set S is the range of a total recursive function or empty. If S is infinite, the function can be chosen to be injective.
• The set S is the range of a primitive recursive function or empty. Even if S is infinite, repetition of values may be necessary in this case.

---

@Bikram sir

Can you please explain option c? Thanks in advance :)

---

@VS 

Every Non-empty recursively enumerable set is the range of some totally recursive function.

This means  , the elements( or members )  of non empty Recursively enumerable set are  total recursive functions .

like , if S is a set , and If x is a member (or element) of S, then we use the notation x ∈ S  .

we can write this as , S = {x} 

similarly here , Non empty Recursively enumerable = { all possible output values of total recursive functions } .

------------

There are some discussion about this statement : " The set of total recursive functions is not recursively enumerable ."

Please read these threads :

1. https://math.stackexchange.com/questions/111773/are-total-recursive-functions-recursively-enumerable?rq=1
2. https://math.stackexchange.com/questions/762988/clarification-of-the-argument-for-the-set-of-total-recursive-functions-not-being?rq=1
3. https://math.stackexchange.com/questions/133319/a-revisit-to-the-question-can-total-recursive-functions-be-recursively-enumerat?rq=1

---

Every Non-empty recursively enumerable set is the range of some totally recursive function.

 

"Every Non-empty recursively enumerable set" - Every non-empty recursive enumerable language, "totally recursive function" - "total function of some recursive language. In short, the sentence means,

There is a recursive language which can be many-to-one reducible to all the non-empty recursive enumerable language. 

Remember that many-to-one reduction means that there is a total function which maps one language to other, the mapping necessarily is not an injection (one-one).