Representable functions - Enderton

Question

I'm working my way through H. Enderton's A Mathematical Introduction to Logic, and I'm trying to do as many problems as possible. I'm currently confused with exercise 10, page 224, chapter 3.3:

Assume that $R$ is a representable relation and that $g$ and $h$ are representable functions. Show that $f$ is representable, where $$f(\vec{a})=\begin{cases}g(\vec{a})\quad\text{if }\vec{a}\in R\\h(\vec{a})\quad\text{if }\vec{a}\notin R\end{cases}$$

This seems so trivial to me ($\vec{a}$ either is or is not in $R$, and both $g$ and $h$ are representable, therefore $f$ is too) that I think I've missed something.

Any comment?

What is definition of representability? Did you try to use it in this case? — Trismegistos, Mar 19 '15 at 09:54
@Trismegistos I'm not sure how to use it in this case. Do you care to develop? — Demosthene, Mar 19 '15 at 10:07

score 1 · Accepted Answer · answered Mar 19 '15 at 21:14

In the following I'll be sloppy, using the same symbol for the number ($a$) and its numeral ($S^a(0)$).

If the (unary) relation $R$ on $\mathbb N$ is representable [see page 205], we have that for some formula $\rho$ :

$a \in R \Leftrightarrow \vDash_{\mathfrak N} \rho(a)$, for every $a \in \mathbb N$.

In turn, the function $g$ is representable as a (binary) relation [see page 212] if, for some formula $\varphi$ :

$x=g(a) \Leftrightarrow \langle a,x \rangle \in g \Leftrightarrow \vDash_{\mathfrak N} \varphi(a,x)$

and the same for $h$ : $y=h(a) \Leftrightarrow \langle a,y \rangle \in h \Leftrightarrow \vDash_{\mathfrak N} \psi(a,y)$, for a suitable $\psi$.

Thus :

$z=f(a) \Leftrightarrow \langle a,z \rangle \in f \Leftrightarrow \vDash_{\mathfrak N} [\varphi(a,z) \land \rho(a)] \lor [\psi(a,z) \land \lnot \rho(a)]$

Ooohhh, I see! Thanks, I thought I would go crazy over this :) — Demosthene, Mar 19 '15 at 21:17

Representable functions - Enderton

1 Answers1