Prev: every infinite r.e. set has injective enumeration: show injectivity
Next: Set theory operators compared to Algebra operators #543 Correcting Math
From: Jonny on 28 Mar 2010 15:23
On Sun, 28 Mar 2010 22:06:46 +0300, Aatu Koskensilta wrote:

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

Hi Aatu,

sorry, that question was confused indeed. What I meant was: Can I assume
that f equals g(0) only for 0, without presupposing its being injective?

Thanks a lot
From: Jonny on 29 Mar 2010 15:49
On Mon, 29 Mar 2010 17:54:01 +0300, Aatu Koskensilta wrote:

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

Thanks a lot for sorting this out. Sure, for f to be defined by course-of-
values recursion I need f*.
I believe it's an easy induction, but still I'm not sure with the
induction step:

show f(n)=f(m) -> n=m
induction over n
f(0)=f(m), But f(0)=g(0). Hence f(m)=g(0). But by the second recursion
equation, for no m=/=0 does f(m) equal g(0), hence m=0=n.
f(n+1)=f(m+1), hence f takes the same value for the smallest argument y
such that g(y) doesn't equal f(x) for any x<=n and for the smallest y'
such that g(y') doesn't equal f(x) for any x<=m. but how do I go on from
here? the induction assumption (f(n)=f(m)->n=m) doesn't seem to help

Sorry if I'm slow, I'm not trained in proving.

at any rate, thanks a lot
 | 
Pages: 1
Prev: every infinite r.e. set has injective enumeration: show injectivity
Next: Set theory operators compared to Algebra operators #543 Correcting Math