#### nomadreid

Gold Member

- 1,265

- 88

- Summary
- Wikipedia characterizes a recursively enumerable set at the top of its eponymous article with a statement that it seems to contradict at the end of the article. Or am I missing something?

In https://en.wikipedia.org/wiki/Recursively_enumerable_set, in the introductory section one reads

"...a set

and in a later section it says

"According to the Church-Turing thesis, .... thus a set

The only clue that I can see that would allow both statements to be valid would be the addition of "and only if" to the second statement. But the sense of "if" in a definition is supposed to be "if and only if", no?

True, the article does give a couple of other definitions that are more satisfactory, but I still wonder whether I am missing something essential here, or whether the introductory paragraph was just being a little sloppy. ???

"...a set

*S*of natural numbers is called**recursively enumerable**... if: ...There is an algorithm that enumerates the members of*S*."and in a later section it says

"According to the Church-Turing thesis, .... thus a set

*S*is recursively enumerable if and only if there is some algorithm which yields an enumeration of*S*. This cannot be taken as a formal definition, however, because the Church–Turing thesis is an informal conjecture rather than a formal axiom."The only clue that I can see that would allow both statements to be valid would be the addition of "and only if" to the second statement. But the sense of "if" in a definition is supposed to be "if and only if", no?

True, the article does give a couple of other definitions that are more satisfactory, but I still wonder whether I am missing something essential here, or whether the introductory paragraph was just being a little sloppy. ???