Faulty definition of r.e. set in Wiki?

[nomadreid]

TL;DR

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 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. ?

 

[SSequence]

I think that when one says "r.e." it definitely specifically binds the definition. So we can write: "there is a recursive function def. that enumerates the members of S."

Now if you consider:
a set is r.e.
iff
there is an algorithm that yields an enumeration of S [definition of a algorithmically enumerable]

now there two implications here:
left to right
right to left

The left-to-right side is trivial. Because if the set is r.e. then indeed there exists a fixed mechanical procedure to write-down all the elements.

The right-to-left side non-trivial though. And this is the main part of CT/CTT. This establishes an equivalence between r.e. or c.e. [I am using c.e. to mean enumerable by a program] and algorithmically enumerable.

==========

I really doubt you missed anything. I think that the first time that you quoted:
"...a set S of natural numbers is called recursively enumerable... if: ...There is an algorithm that enumerates the members of S."
the intention was to write/mean "program" instead of "algorithm".

 

[nomadreid]

Thanks, SSequence. That makes sense.

 

[fresh_42]

Here's another definition from Wikipedia:

A set $S \subseteq \mathbb{N}$ is recursively enumerable, if $S=\emptyset$ or there exists a total, computational function [means an algorithm] $\mathbb{N} \longrightarrow S$ with $f(\mathbb{N})=S$.

I have difficulties to see any differences between the definitions, except the wording "members of S" or "S" itself. The article lists not less then eleven equivalent statements of recursively enumerable.

 

[SSequence]

Yes, that is correct. That definition equates the range of a (total) computable function with a c.e./r.e. set (the inclusion of $S=\emptyset$ is to also include the boundary case). But that is less of a definition and more of a basic result in elementary computability.

The two standard definitions (probably there are more which I am not aware of) are (both can be shown to be equivalent):
(a)---- enumeration via a (non-terminating) program, which fits closest to our intuition
(b)---- a program halting precisely on all inputs $x$ where $x \in A$ and running forever precisely on all inputs $x$ where $x \notin A$. I don't re-call exactly what the partial function computed by the given program is called ... perhaps semi-characteristic function?

==========

Now there are two directions here in equating range of a computable function with a c.e. set:
(i)---- the range of every total computable function is a c.e. set
(ii)---- every non-empty c.e. set can be written as the range of some total computable function

For the sake of precision, let's take (b) above as our definition.

Informally showing (i) is fairly direct. Given an input $x$ just simulate the given (total) computable function $g:\mathbb{N} \rightarrow \mathbb{N}$ on the inputs. If there exists some input $a \in \mathbb{N}$ where $g(a)=x$, it will be found out (and we can halt). Otherwise our program will run forever. This computes the semi-characteristic(?) function of the set $range(g)$.

For (ii), let's call our non-empty and infinite r.e. set $A$. Now just consider the partial recursive function $f:\mathbb{N} \rightarrow \mathbb{N}$ which halts precisely on those inputs which belong to $A$ (and runs forever otherwise).

It is easy to see that we can enumerate all the elements of $A$ by simulating the function $f$ on all inputs. As soon as $f$ halts on a given input $x$, that value $x$ is added to our enumeration (of $A$).

It isn't difficult at all to make the above procedure conform with the definition (b) [given any input $x$ we now just need to do the same enumeration everytime and keep a counter $n$ that starts from $0$ and runs until it equals $x$]. This way our function will, on an input $x$, return the "$x$-th element" that occurs in the enumeration.

For the case of finite set $A=\{a_0,a_1,a_2,...,a_{N-1}\}$ we can consider the function $g:\mathbb{N} \rightarrow \mathbb{N}$ such that:
$g(x)=a_x$ whenever $x \leq N-1$
$g(x)=a_{N-1}$ whenever $x \geq N$
This function is a total computable function with range equal to $A$.

 

[SSequence]

Here's another definition from Wikipedia:

A set $S \subseteq \mathbb{N}$ is recursively enumerable, if $S=\emptyset$ or there exists a total, computational function [means an algorithm] $\mathbb{N} \longrightarrow S$ with $f(\mathbb{N})=S$.

I have difficulties to see any differences between the definitions, except the wording "members of S" or "S" itself. The article lists not less then eleven equivalent statements of recursively enumerable.

Oh OK, I see what you mean. Yes, it seems this definition is quite close to definition(a) I wrote in previous post [enumeration via a (non-terminating) program (with no input)] and seems identical with one described in OP.

 

[fresh_42]

I don't re-call exactly what the partial function computed by the given program is called ... perhaps semi-characteristic function?

IF I understood it right, the characteristic function is just that, but the entire property is called semi-decidability.

 

[SSequence]

Well, given a set $A \subseteq \mathbb{N}$ we can define two related functions $f,g$(from $\mathbb{N}$ to $\mathbb{N}$) as follows:
$f(x)=1$ when $x \in A$
$f(x)=0$ when $x \notin A$

$g(x)=1$ when $x \in A$
$g(x)=$undefined when $x \notin A$

Usually the first function $f$ is called the characteristic function of $A$.

If the context is clear (and one is not being strict), usually it wouldn't lead to any confusion to also call $g$ the characteristic function. But possibly, it might if we have to consider both $f$ and $g$ together in the same context/situation.P.S.
Sometimes something like this is written [which is basically yet another way of saying the same thing, as the second sentence is just re-wording of definition(b) in post#5]:
A set is recursive iff its characteristic function is computable
A set is r.e. iff its semi-characteristic function is (partial) computable

 

[fresh_42]

You are right. They called it partial characteristic or semi-characteristic function.