Re: Weird problem

Peter Webb wrote:
"n3wb1e" <n3wb1e@xxxxxxxxxxxxxx> wrote in message news:8H5Ee.193410$75.8362862@xxxxxxxxxxxxxxx

This is from mendelson's book:

Let f(x)= 2 if FLT is true; 1 if FLT is false.
Is f primitive recursive?

I admit that the problem has not too much sense to me...
I think the problem was given first of Wiles' proof, so it must have a sense even without knowing that is provable.
Any idea?

If the book was writen before Wiles as you imply, then at the time it was not known if it was primitive recursive.It may have been the equivalent of a TM halting question. We now know f(x) = 2.

The function is primitive recursive, since it's extensionally equivalent to either f(x) = 2 or f(x) = 1 and all constant functions are primitive recursive. Of course, the specification does not give us a primitive recursive definition of the function and without proving or refuting FLT there is no way to find such a definition.

Similarly, consider the set defined by

 {x | x = 0 & Goldbach's conjecture \/ x = 1 & ~(Goldbach's conjecture)}

It's trivial to show that this set is finite, since it's either {0} or {1}, even though barring a solution to Goldbach's conjecture there's no way to know which it is.

--
Aatu Koskensilta (aatu.koskensilta@xxxxxxxxx)

"Wovon man nicht sprechen kann, daruber muss man schweigen"
 - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
.