Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Question Regarding Binary PR Predicates

  1. Feb 12, 2017 #1
    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. jcsd
  3. Feb 19, 2017 #2
    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.
     
  4. Feb 19, 2017 #3
    In this particular case:
    g(0)=ω
    g(n)=n - 1 when n≠0
     
    Last edited: Feb 19, 2017
  5. Aug 4, 2017 #4
    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Question Regarding Binary PR Predicates
  1. Predicate calculus (Replies: 7)

Loading...