# I Question Regarding Binary PR Predicates

1. Feb 12, 2017

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

The 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: Feb 12, 2017
2. Feb 19, 2017

### Greg Bernhardt

Thanks for the thread! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post? The more details the better.

3. Feb 19, 2017

### SSequence

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

Last edited: Feb 19, 2017
4. Aug 4, 2017

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

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.

Last edited: Aug 4, 2017