Prev: WIMBLES WOBBLE BUT THEY DON'T FALL DOWN
Next: every infinite r.e. set has injective enumeration: showinjectivity
From: Jonny on 28 Mar 2010 15:02
Hi there,

Do recursive functions give unique values for 0?

I'm trying to show that every infinite recursive enumerable (r.e.) set
has an injective (one-one) recursive enumeration.

Is this a standard problem that I'll find in some textbook?

My approach so far:
I've assumed that A is r.e. and infinite. So there's an enumeration g of
A.
Now I've defined f
f(0) = g(0)
f(n+1) = U^2_2 (n,f(mu_y(Vx<=y (¬y=(g*(n))_x)) ) )
where U^2_2(x,y)= y (projection function), and (g*(n))_x gives the value
of g for x (is the course-of-values function of g)
f is recursive
Now I'm trying to show that f injective by induction over n
However, already for f(0)=f(y) I only get f(y)=g(0). But can I assume
that there's only one value for g(0)?

Thanks a lot,
kind regards,
Jonny
From: Aatu Koskensilta on 28 Mar 2010 15:06
Jonny <js784(a)st-and.ac.uk> writes:

> But can I assume that there's only one value for g(0)?

Yes, as follows by definition since g is a (total) function. What
prompts this odd question?

--
Aatu Koskensilta (aatu.koskensilta(a)uta.fi)

"Wovon man nicht sprechan kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Aatu Koskensilta on 29 Mar 2010 10:54
Jonny <js784(a)st-and.ac.uk> writes:

> What I meant was: Can I assume that f equals g(0) only for 0, without
> presupposing its being injective?

Let's recall your definition of f, given a recursive enumeration g of an
infinite set:

f(0) = g(0)
f(n+1) = U^2_2 (n,f(mu_y(Vx<=y (�y=(g*(n))_x)) ) ) where U^2_2(x,y)= y
(projection function), and (g*(n))_x gives the value of g for
x (is the course-of-values function of g)

This isn't quite right. Without being quite as tediously detailed, what
we want is:

f(n) = g(y) where y is the smallest number such that for all m < n,
f(m) =/= g(y)

The injectivity of f follows by an easy induction. I presume you can see
how to show f is recursive and total, given the assumption that g is a
recursive enumeration of an infinite set? (A course-of-values function
does enter into it, but not that of g.)

--
Aatu Koskensilta (aatu.koskensilta(a)uta.fi)

"Wovon man nicht sprechan kann, dar�ber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus
 | 
Pages: 1
Prev: WIMBLES WOBBLE BUT THEY DON'T FALL DOWN
Next: every infinite r.e. set has injective enumeration: showinjectivity