We can think of a notation being assigned to some ordinal o≥ω when there exists some total and onto function g for which:(adsbygoogle = window.adsbygoogle || []).push({});

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)

**Physics Forums | Science Articles, Homework Help, Discussion**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# I Question Regarding Binary PR Predicates

Have something to add?

Draft saved
Draft deleted

Loading...

Similar Threads for Question Regarding Binary |
---|

B What question should you ask? |

I Question about simplifying Sigma notation |

I Shopping List Game: Probability Question |

I A simple question about probability theory |

B Correlation question |

**Physics Forums | Science Articles, Homework Help, Discussion**