Question Regarding Binary PR Predicates

[SSequence]

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 ω_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)

 

[SSequence]

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≥y

In this particular case:
g(0)=ω
g(n)=n - 1 when n≠0

 

[SSequence]

I don't like bumping an old thread (with not much substantial to add). However, there seems to be an important factual mistake (not corrected later), which I feel might be important to correct (partly because of search-engine searches and partly because of forum's own function of searching old threads).

The question is that what is the smallest possible ordinal (obviously less than ω_CK) for which the predicate f can never be primitive recursive.

This is probably wrong. I am basing this on:
https://mathoverflow.net/questions/82136/ordinals-and-complexity-classes

I don't fully understand the answer though, unfortunately.

Then one can ask whether the question in OP is still reasonable question (on the very least with function g in OP as total,onto,1-1) or not, as long as one is restricted to reasonable notations defined explicitly (in a limited/fixed way) up till a smaller point? What I mean is that suppose we fix some relatively large ordinal p(<wCK) and fix the notion of reasonable notations up till that point. Then we can ask the question for any q < p in the context where we are restricted to a reasonable notations only.
We can then say that q is a cut-off point if there is no binary PR predicate say that can serve as the less-than relation for a "reasonable notation" of q.

Suppose we choose a fairly large specific value of p (specifically say p=ε_ε0). Can we find a cut-off point at some q < p or not? This can be thought of as a concrete problem.

Edited:
Modified the post as I am still unsure about many aspects.