0

I'm studying recursive functions and right now I stucked in this:

"Natural numbers subset is PR if and only if characteristic function is PR". Why is that? Becouse it has values 0 ant s(0) only? So how about set {1, 2, 5} is it PR? If so, that means that all subsets are PR?

Thanks to reply to stupid question.

Martynas Riauka
  • 339
  • 1
  • 13

1 Answers1

0

What you cited was the definition of PR subsets of $\mathbb N$. What it means is that in order to see if a set $S\subset\mathbb N$ is PR, you must see if it's characteristic function is PR.

There is no why here, since this is the definition.

The set $\{1,2,5\}$ is, by this definition, primitive recursive if and only if the function $$f(n) = \begin{cases}1 & \text{if } x=1,2,5\\0&\text{otherwise}\end{cases}$$ is primitive recursive.

5xum
  • 123,496
  • 6
  • 128
  • 204
  • @MartynasRiauka Do you know about any function that is primitive recursive? It is probably good to have a few examples to get the feeling of it... – 5xum Jul 24 '14 at 07:58
  • I just don't get it how characteristic function is PR, yet. If I have a same set {1, 2, 5} and f(0)=0 f(1)=1 f(2)=1 ..... How to see that this is PR? – Martynas Riauka Jul 24 '14 at 08:21
  • @MartynasRiauka Go one step at a time. First, try to prove that the characteristic function for ${0}$ is PR. Then, prove that for any $n\in\mathbb N$, the characteristic function for ${n}$ is PR. Then, see how a characteristic function for ${n_1,n_2,\dots,n_k}$ is connected to the characteristic functions for ${n_1}, {n_2},\dots,{n_k}$. – 5xum Jul 24 '14 at 08:24
  • Ok, so I have {0}. To prove that the characteristic function is PR I need to use primitive recursion operator? f(0) = s(0) ok. f(s(0)) = 0 ... Am I going somewhere with this? It seems so simple but my brains doesn't want to work this time. – Martynas Riauka Jul 24 '14 at 08:36
  • @MartynasRiauka You did just fine. $f(0)=1$ and $f(s(n)) = 0$ is exactly the PR definition of $\chi_{{0}}$ – 5xum Jul 24 '14 at 08:38
  • Now if we have {n}, then f(n) = 1 , f(s(n)) = 0 and f(0), f(s(0)), f(s(s(0))), .... f(s(n-1 times)) all equal to 0. Is that proof? – Martynas Riauka Jul 24 '14 at 08:49
  • Nope. You need to define a function using PR rules. – 5xum Jul 24 '14 at 08:50
  • And how to do that? – Martynas Riauka Jul 24 '14 at 08:52
  • @MartynasRiauka By reading some books about primitive recursion, finding what the definition is, then doing some excercises. – 5xum Jul 24 '14 at 08:53
  • Oh ok, I don't waste your time. ;) – Martynas Riauka Jul 24 '14 at 08:57