# What is the point of defining relations in terms of other relations in mathematics?

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: 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...

• 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. – spaceisdarkgreen Nov 8 '18 at 16:37
• @spaceisdarkgreen lemma 5.1.6 already does that one page earlier. – Pinocchio Nov 8 '18 at 21:56
• 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. – Eric Wofsey Nov 8 '18 at 22:08
• What Eric said ^ – spaceisdarkgreen Nov 9 '18 at 0:08
• 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. – Mauro ALLEGRANZA Nov 9 '18 at 7:44

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.