0
$\begingroup$

I was reading the following set of notes on logic (page 84 of paper pdf) and came a across a rather simple definition but was unsure what it meant conceptually:

enter image description here

I think I understand the proof (it would be more clear if the characteristic function was involved) but it didn't feel like I understood what the definition actually meant conceptually or why it was intereting.

It seems that whenever one of the condition $R_i(a)$ is true then we output whatever $P_i(a)$ does. $R(a) \iff a \in R \subseteq \mathbb N^n$. So I am assuming that $P(a)$ is just outputting the relation it is suppose to define. Informally $P:\mathbb N^n \to \{0,1\}$ (though earlier they actually define the characteristic function for this, i.e. indicator function for this). So to me it just seems rather odd to do this because we are defining a new relation using an old one. So Basically whenever we have that the old relation hold we actually return a different relation (or indicator of it). Which seems really weird to me. It's nearly like the new relation function $P$ is a liar. It actually uses some hidden relation $R$ to compute itself but returns other elements. It nearly feels that $R_i$ is irrelevant because if I saw the specification of $P$ (say as a programer), I would just see what it really computes, which is $P_i$. If it does some weird thing in the background seems rather irrelevant.

I suspect I either have a misconception or misinterpreting things (or over thinking things?), though the definition for this new relation $P$ seems poorly motivated to me because the assumption is that $P_i$ is computable, so why do we even need $R_i$ to compute $P_i$? I just don't see the point.

PS: didn't know what would be a good title for this...

Improve this question
$\endgroup$
  • 3
    $\begingroup$ If you saw the (most natural) specification of this as a programmer, you would see a switch statement (or an If, elif... block) that says if $R_i$ holds return $P_i$. You need the $R_i$ to tell you which $P_i$ to compute. The point of this lemma is that you can build a program out of smaller programs with a switch statement. $\endgroup$ – spaceisdarkgreen Nov 8 '18 at 16:37
  • $\begingroup$ @spaceisdarkgreen lemma 5.1.6 already does that one page earlier. $\endgroup$ – Pinocchio Nov 8 '18 at 21:56
  • 2
    $\begingroup$ Lemma 5.1.6 does it for functions $\mathbb{N}^n\to\mathbb{N}$, Lemma 5.1.7 does it for subsets of $\mathbb{N}^n$. They're the same idea, just in slightly different contexts. $\endgroup$ – Eric Wofsey Nov 8 '18 at 22:08
  • 1
    $\begingroup$ What Eric said ^ $\endgroup$ – spaceisdarkgreen Nov 9 '18 at 0:08
  • $\begingroup$ It is a sort of def by cases : it is more intuitive if we use as $P$ a function $f(x) =a$ if $x \ge 0$ and $f(x)=b$ if $x < 0$. But the "mechanism" works for relations as well. $\endgroup$ – Mauro ALLEGRANZA Nov 9 '18 at 7:44
0
$\begingroup$

I'd write $P = (P_1\cdot R_1) + \ldots + (P_n\cdot R_n)$. Then for each input $a$, $$P(a) = (P_1(a)\cdot R_1(a)) + \ldots + (P_n(a)\cdot R_n(a)).$$ If $R_i(a)=1$ and $R_j(a)=0$ for each $j\ne i$, then $P(a) = P_i(a)\cdot R_i(a) = P_i(a)$ as claimed. If $P_1,\ldots,P_n$ and $R_1,\ldots,R_n$ are computable, then $P$ is computable.

Improve this answer
$\endgroup$
  • $\begingroup$ my question is not about the proof. My question is about the semantic meaning of this definition. I understand why its computable. $\endgroup$ – Pinocchio Nov 8 '18 at 16:32
  • 1
    $\begingroup$ Its just the usual definition by cases in computability theory. $\endgroup$ – Wuestenfux Nov 8 '18 at 16:34
  • $\begingroup$ saying its the usual X doesn't help because its the first time seeing this for me. $\endgroup$ – Pinocchio Nov 8 '18 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.