- #1

SSequence

- 561

- 96

We can think of a notation being assigned to some ordinal o≥ω when there exists some total and onto function g for which:

i) the domain is N

ii) the co-domain is the set of all ordinals less than o

Now consider the following set:

S={(x,y) | g(x) < g(y) }

Let the characteristic function of this set S be denoted by f : N x N→{0,1}.

As an example, here is one example of the function f above for ω:

f(x,y)=1 if x<y

f(x,y)=0 if x≥y

Here is another example of the function f above for ω+1:

(a) when x=0 and y=0

f(0,0)=0

(b) when x=0 and y≠0

f(0,y)=0

(c) when x≠0 and y=0

f(x,0)=1

(d) when x≠0 and y≠0:

f(x,y)=1 if x<y

f(x,y)=0 if x≥yThe question is that what is the smallest possible ordinal (obviously less than ω

Edit:

We might have also defined the set S above as:

S={(x,y) | g(x) ≤ g(y) }

I do not know whether this would or wouldn't make a substantial difference to the answer of this question. It would probably be an interesting (or at least instructive) exercise by itself to consider this question.

Obviously if we also place the further restriction on g that it has to be 1-1 then clearly these variations shouldn't matter I think (would have to check this just to be sure but if its true it would be easy to show)

i) the domain is N

ii) the co-domain is the set of all ordinals less than o

Now consider the following set:

S={(x,y) | g(x) < g(y) }

Let the characteristic function of this set S be denoted by f : N x N→{0,1}.

As an example, here is one example of the function f above for ω:

f(x,y)=1 if x<y

f(x,y)=0 if x≥y

Here is another example of the function f above for ω+1:

(a) when x=0 and y=0

f(0,0)=0

(b) when x=0 and y≠0

f(0,y)=0

(c) when x≠0 and y=0

f(x,0)=1

(d) when x≠0 and y≠0:

f(x,y)=1 if x<y

f(x,y)=0 if x≥yThe question is that what is the smallest possible ordinal (obviously less than ω

_{CK}) for which the predicate f can never be primitive recursive.Edit:

We might have also defined the set S above as:

S={(x,y) | g(x) ≤ g(y) }

I do not know whether this would or wouldn't make a substantial difference to the answer of this question. It would probably be an interesting (or at least instructive) exercise by itself to consider this question.

Obviously if we also place the further restriction on g that it has to be 1-1 then clearly these variations shouldn't matter I think (would have to check this just to be sure but if its true it would be easy to show)

Last edited: