5.3: Representable Sets and Functions

Last updated
Save as PDF

Page ID: 9709

$Leary.jpg$
Contributed by Christopher Leary and Lars Kristiansen
Professor (Mathematics) at SUNY Geneseo and University of Oslo
Sourced from OpenSUNY

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

For the sake of discussion, suppose that we let $f \left( x \right) = x^2$. It will not surprise you to find out that $f \left( 4 \right) = 16$, so we would like to write $\mathfrak{N} \models f \left( 4 \right) = 16$. Unfortunately, we are not allowed to do this, since the symbol $f$, not to mention $4$ and $16$, are not part of the language.

What we can do, however, is to represent the function $f$ by a formula in $\mathcal{L}_{NT}$. To be specific, suppose that $\phi \left( x, y \right)$ is

\[y = ExSS0.\]

Then, if we allow ourselves once again to use the abbreviation $\bar{a}$ for the $\mathcal{L}_{NT}$-term $SSS \cdots S0 \left( aS \text{'s} \right)$, we can assert that

\[\mathfrak{N} \models \phi \left( \bar{4}, \overline{16} \right)\]

which is the same thing as

\[\mathfrak{N} \models = SSSSSSSSSSSSSSSS0ESSSS0SS0.\]

(Aren't you glad we don't use the official language very often?) Anyway, the situation is even better than this, for $\phi \left( \bar{4}, \overline{16} \right)$ is derivable from $N$ rather than just true in $\mathfrak{N}$. In fact, if you look back at Lemma 2.8.4, you probably won't have any trouble believing the following statements:

$N \vdash \phi \left( \bar{4}, \overline{16} \right)$
$N \vdash \neg \phi \left( \bar{4}, \overline{17} \right)$
$N \vdash \neg \phi \left( \bar{1}, \overline{714} \right)$

In fact, this formula $\phi$ is such, and $N$ is such, that if $a$ is any natural number and $b = f \left( a \right)$, then

\[N \vdash \forall y \left[ \phi \left( \bar{a}, y \right) \leftrightarrow y = \bar{b} \right].\]

We will say that the formula $\phi$ represents the function $f$ in the theory $N$.

Definition 5.3.1.

A set $A \subseteq \mathbb{N}^k$ is said to be representable (in $N$) if there is an $\mathcal{L}_{NT}$-formula $\phi \left( \underset{\sim}{x} \right)$ such that

\[\begin{array}{ll} \forall \underset{\sim}{a} \in A & N \vdash \phi \left( \bar{\underset{\sim}{a}} \right) \\ \forall \underset{\sim}{b} \not\in A & N \vdash \neg \phi \left( \bar{\underset{\sim}{b}} \right). \end{array}\]

In this case we will say that the formula $\phi$ represents the set $A$.

Definition 5.3.2.

A set $A \subseteq \mathbb{N}^k$ is said to be weakly representable (in $N$) if there is an $\mathcal{L}_{NT}$-formula $\phi \left( \underset{\sim}{x} \right)$ such that

\[\begin{array}{ll} \forall \underset{\sim}{a} \in A & N \vdash \phi \left( \bar{\underset{\sim}{a}} \right) \\ \forall \underset{\sim}{b} \not\in A & N \nvdash \phi \left( \bar{\underset{\sim}{b}} \right). \end{array}\]

In this case we will say that the formula $\phi$ weakly represents the set $A$.

Notice that if $A$ is representable, then $A$ is weakly representable. On a few occasions we will talk about a set being representable in $T$, where $T$ is a different set of $\mathcal{L}_{NT}$-formulas. This just means that all of the deductions mentioned in the previous two definitions should be deductions-from-$T$, rather than deductions-from-$N$.

Chaff: A bit of notation has slipped in here. Rather than writing $x_1, x_2, \ldots, x_k$ over and over and over again in the next few sections, we will abbreviate this as $\underset{\sim}{x}$. Similarly, $\bar{\underset{\sim}{x}}$ is shorthand for $\overline{x_1}, \overline{x_2}, \ldots, \overline{x_k}$. If you want, you can just assume that there is only one $x$ - it won't make any difference to the exposition.

We will also discuss representable functions, and this brings up a couple of subtle points that need to be addressed. The general idea is that a function $f : \mathbb{N}^k \rightarrow \mathbb{N}$ should be representable if $N$ is able prove that a formula that represents the function does the right thing, but historically the term weakly representable has been applied to functions whose domains are (possibly strict) subsets of $\mathbb{N}^k$, which adds some complexity.

To begin with, we will need to be able to talk about the domains of functions with a little more precision.

Definition 5.3.3.

Suppose that $A \subseteq \mathbb{N}^k$ and suppose that $f : A \rightarrow \mathbb{N}$. If $A = \mathbb{N}^k$ we will say that $f$ is a total function. If $A \subsetneq \mathbb{N}^k$, we will call $f$ a partial function.

Now we can define what it means for a function to be representable or weakly representable.

Definition 5.3.4.

Suppose that $f : \mathbb{N}^k \rightarrow \mathbb{N}$ is a total function. We will say that $f$ is a representable function (in $N$) if there is an $\mathcal{L}_{NT}$-formula $\phi \left( x_1, \ldots, x_{k+1} \right)$ such that, for all $a_1, a_2, \ldots, a_{k+1} \in \mathbb{N}$,

\[\text{If} \: f \left( a_1, \ldots, a_k \right) = a_{k+1}, \: \text{then} \: N \vdash \phi \left( \overline{a_1}, \ldots, \overline{a_{k+1}} \right) \\ \text{If} \: f \left( a_1, \ldots, a_k \right) \neq a_{k+1}, \: \text{then} \: N \vdash \neg \phi \left( \overline{a_1}, \ldots, \overline{a_{k+t}} \right).\]

Notice that a total function is a representable function if and only if it is a representable subset of $\mathbb{N}^{k+1}$. See Exercise 4.

Definition 5.3.5.

Suppose that $A \subseteq \mathbb{N}^k$ and $f : A \rightarrow \mathbb{N}$ is a (possibly) partial function. We will say that $f$ is a weakly representable function (in $N$) if there is an $\mathcal{L}_{NT}$-formula $\phi \left( x_1, \ldots, x_{k+1} \right)$ such that, for all $a_1, a_2, \ldots, a_{k+1} \in \mathbb{N}$,

\[\text{If} \: f \left( a_1, \ldots, a_k \right) = a_{k+1}, \: \text{then} \: N \vdash \phi \left( \overline{a_1}, \ldots, \overline{a_{k+1}} \right) \\ \text{If} f \left( a_1, \ldots, a_k \right) \neq a_{k+1}, \: \text{then} \: N \nvdash \phi \left( \overline{a_1}, \ldots, \overline{a_{k+1}} \right).\]

Chaff: In the definition above, notice that if, for example, 5 is not an element of the domain of the unary function $f$, then $f \left( 5 \right)$ is not going to be equal to anything, so we know that $f \left( 5 \right) \neq 17$. All we ask, in that case, is that $N$ does not prove $\phi \left( \bar{5}, \overline{17} \right)$. We do not need, and cannot expect, $N$ to prove $\neg \phi \left( \bar{5}, \overline{17} \right)$.

How important is it to know whether a function is total or not? With regards to representability, the big result is the following, the proof of which is omitted.

proposition 5.3.6.

Suppose that $f$ is a total function from $\mathbb{N}^k$ to $\mathbb{N}$. Then $f$ is representable if and only if $f$ is weakly representable.

Partial functions will be very important to us as we work through Chapter 7, but for the next couple of chapters, almost all of our functions will be total. If $f$ is representable, we can say a little more about what $N$ can prove about $f$.

proposition 5.3.7.

Suppose that $f : \mathbb{N}^k \rightarrow \mathbb{N}$ is a total function. Then the following are equivalent.

$f$ is a representable function.
There exists an $\mathcal{L}_{NT}$-formula $\psi \left( x_1, \ldots, x_{k+1} \right)$ such that for all $\underset{\sim}{a} \in \mathbb{N}^k$,
\[N \vdash \left( \forall y \right) \left[ \psi \left( \bar{\underset{\sim}{a}}, y \right) \leftrightarrow y = \overline{f \left( \underset{\sim}{a} \right)} \right].\]

proof

Exercise 9 provides an outline of a proof.

Chaff:

What's in a name? that which we call a rose
By any other name would smell as sweet;
So Romeo would, were he not Romeo call'd,
Retain that dear perfection which he owes
Without that title.
-Romeo and Juliet, Act II, Scene ii

In computer science courses, in many mathematical logic texts, and in fact in Chapter 7 of this book, a different approach is taken when representable sets and functions are introduced. Starting with certain initial functions, the idea of recursion, and an object called the $\mu$-operator, a collection of partial functions is defined such that each function in the collection is effectively calculable. This is called the collection of computable functions, which leads to something called decidable (or computable) sets. Then these texts prove that the collection of representable sets that we just defined is the same as the collection of decidable sets. Thus we all end up at the same place, with nicely defined collection of sets and functions, that we call computable. Or representable. Or recursive. So if you are confused by the different definitions, just remember that they all define the same concept, and remember that the objects that are recursive (or representable or computable) are (in some sense) the simple ones, the ones where membership can be proved in $N$.

To be fair, it is not quite as simple as Juliet makes it out to be. (It never is, is it?) The path that we have taken to representable sets is clean and direct but emphasizes the deductions over the functions. The approach through initial functions stresses the fact that everything that we discuss can be calculated, and that viewpoint gives a natural tie between the logic that we have been discussing and its applications to computer science. For more on this connection, see Section 5.4 and Chapter 7.

Definition 5.3.8.

We will say that a set $A \subseteq \mathbb{N}^k$ is definable if there is a formula $\phi \left( \underset{\sim}{x} \right)$ such that

\[\begin{array}{ll} \forall \underset{\sim}{a} \in A & \mathfrak{N} \models \phi \left( \bar{\underset{\sim}{a}} \right) \\ \forall \underset{\sim}{b} \notin A & \mathfrak{N} \models \neg \phi \left( \bar{\underset{\sim}{b}} \right). \end{array}\]

In this case, we will say that $\phi$ defines the set $A$.

Chaff: It is very important to notice the difference between saying that $\phi$ represents $A$ and $\phi$ defines $A$, which is the same as the difference between $N \vdash$ and $\mathfrak{N} \models$. Notice that any representable set must be definable and is defined by any formula that represents it. The converse, however, is not automatic. In fact, the converse is not true. But we're getting ahead of ourselves.

We have mentioned several times that the axiom system $N$ is relatively weak. We will show in this section that $N$ is strong enough to prove some of the $\mathcal{L}_{NT}$ formulas that are true in $\mathfrak{N}$, namely the class of true $\Sigma$-sentences. And this will allow us to show that if a set $A$ has a relatively simple definition, then the set $A$ will be representable.

Recall from Chapter 4 that a formula is a $\Delta$-formula if it contains only bounded quantifiers. Slightly more complicated are the $\Sigma$-formulas, which can contain bounded quantifiers and unbounded existential quantifiers, and $\Pi$-formulas, which can use both bounded quantifiers and unbounded universal quantifiers.

Example 5.3.9:

Here is a perfectly nice example of a $\Delta$-formula $\phi$: $\left( \forall x < t \right) \left( x = 0 \right)$. Notice that the denial of $\phi$ is not a $\Delta$-formula, as $\neg \left( \forall x < t \right) \left( x = 0 \right)$ is neither a $\Sigma$- nor a $\Pi$-formula. But a chain of logical equivalences shows us that $\neg \phi$ is equivalent to a $\Delta$-formula if we just push the negation sign inside the quantifier:

\[\neg \phi \\ \neg \left( \forall x < t \right) \left( x = 0 \right) \\ \left( \exists x < t \right) \neg \left( x = 0 \right).\]

Similarly, we can show that any propositional combination (using $\land$, $\lor$, $\neg$, $\rightarrow$, $\leftrightarrow$) of $\Delta$-formulas is equivalent to a $\Delta$-formula. We will use this fact approximately 215,342 times in the remainder of this book.

A $\Sigma$-sentence is, of course, a $\Sigma$-formula that is also a sentence. We will be particularly interested in $\Sigma$-formulas and $\Delta$-formulas, for we will show if $\phi$ is a $\Sigma$-sentence and $\mathfrak{N} \models \phi$, then the axiom set $N$ is strong enough to provide a deduction of $\phi$. Since every $\Delta$-sentence is also a $\Sigma$-sentence, any $\Delta$-sentence that is true in $\mathfrak{N}$ is also provable from $N$.

The first lemma that we will provide shows that $N$ is strong enough to prove that $1 + 1 = 2$. Actually, we already know this since it was proved back in Lemma 2.8.4. We now expand that result and show that if $t$ is any variable-free term, then $N$ proves that $t$ is equal to what it is supposed to be equal to.

Recall that if $t$ is a term, then $t^\mathfrak{N}$ is the interpretation of that term in the structure $\mathfrak{N}$. For example, suppose that $t$ is the term $ESSS0SS0$, also known as $SSS0^{SS0}$. Then $t^\mathfrak{N}$ would be the number 9, and $\overline{t^\mathfrak{N}}$ would be the term $SSSSSSSSS0$. So when this lemma says that $N$ proves $t = \overline{t^\mathfrak{N}}$, you should think that $N$ proves $SSS0^{SS0} = SSSSSSSSS0$, which is the same as saying that $N \vdash \bar{3}^\bar{2} = \bar{9}$.

lemma 5.3.10.

For each variable-free term $t$, $N \vdash t = \overline{t^\mathfrak{N}}$.

proof

We proceed by induction on the complexity of the term $t$. If $t$ is the term 0, then $t^\mathfrak{N}$ is the natural number 0, and $\overline{t^\mathfrak{N}}$ is the term 0. Thus we have to prove that $N \vdash 0 = 0$, which is an immediate consequence of our logical axioms.

If $t$ is $S \left( u \right)$, where $u$ is a variable-free term, then the term $\overline{t^\mathfrak{N}}$ is identicala to the term $S \left( \overline{u^\mathfrak{N}} \right)$. Also, $N \vdash u = \overline{u^\mathfrak{N}}$, by the inductive hypothesis, and thus $N \vdash Su = S \left( \overline{u^\mathfrak{N}} \right)$, thanks to the equality axiom (E2). Putting all of this together, we get that $N \vdash t = Su = S \left( \overline{u^\mathfrak{N}} \right) = \overline{t^\mathfrak{N}}$, as needed.

If $t$ is $u + v$, we recall that Lemma 2.8.4 proved that $N \vdash \overline{u^\mathfrak{N}} + \overline{v^\mathfrak{N}} = \overline{u^\mathfrak{N} + v^\mathfrak{N}}$. But then $N \vdash t = u + v = \overline{u^\mathfrak{N}} + \overline{v^\mathfrak{N}} = \overline{u^\mathfrak{N} + v^\mathfrak{N}} = \overline{t^\mathfrak{N}}$, which is what we needed to show. The arguments for terms of the form $u \cdot v$ or $u^v$ are similar, so the proof is complete.

The next lemma and its corollary will be used in our proof that true $\Sigma$-sentences are provable from $N$.

lemma 5.3.11: Rosser's lemma

If $a$ is a natural number,

\[N \vdash \left( \forall x < \bar{a} \right) \left[ x = \bar{0} \lor x = \bar{1} \lor \cdots \lor x = \overline{a - 1} \right].\]

proof

We use induction on $a$. If $a = 0$, it suffices to prove that $N \vdash \forall x \left[ x < 0 \rightarrow \perp \right]$. By Axiom 9 of $N$, we know that $N \vdash \neg \left( x < 0 \right)$, so $N \vdash \left( x < 0 \right) \rightarrow \perp$, as needed.

For the inductive step, suppose that $a = b + 1$. We must show that

\[N \vdash \forall x \left[ x < \overline{b + 1} \rightarrow x = \bar{0} \lor \cdots \lor x = \bar{b} \right].\]

Since $\overline{b + 1}$ and $S \bar{b}$ are identical, it suffices to show that

\[N \vdash \forall x \left[ x < \overline{Sb} \rightarrow x = \bar{0} \lor \cdots \lor x = \bar{b} \right].\]

By Axiom 10, we know that $N \vdash x < S \bar{b} \rightarrow \left( x < \bar{b} \lor x = \bar{b} \right)$, and then by the inductive hypothesis, we are finished.

corollary 5.3.12.

If $a$ is a natural number, then

\[N \vdash \left[ \left[ \left( \forall x < \bar{a} \right) \phi \left( x \right) \right] \leftrightarrow \left[ \phi \left( \bar{0} \right) \land \phi \left( \bar{1} \right) \land \cdots \land \phi \left( \overline{a -1} \right) \right] \right].\]

proof

Exercise 11.

Now we come to the major result of this section, that our axiom system is strong enough to prove all true $\Sigma$-sentences.

proposition 5.3.13.

If $\phi \left( \underset{\sim}{x} \right)$ is a $\Sigma$-formula with free variables $\underset{\sim}{x}$, if $\underset{\sim}{t}$ are variable-free terms, and if $\mathfrak{N} \models \phi \left( \underset{\sim}{t} \right)$, then $N \vdash \phi \left( \underset{\sim}{t} \right)$.

proof

This is a proof by induction on the complexity of the formula $\phi$.

If $\phi$ is atomic, say for example that $\phi$ is $x < y$ and terms $t$ and $u$ are such that $\mathfrak{N} \models t < u$. Then $t^\mathfrak{N} < u^\mathfrak{N}$, so by Lemma 2.8.4, $N \vdash \overline{t^\mathfrak{N}} < \overline{u^\mathfrak{N}}$. But we also know $N \vdash t = \overline{t^\mathfrak{N}}$ and $N \vdash u = \overline{u^\mathfrak{N}}$, by Lemma 5.3.10, so $N \vdash t < u$, as needed.
Negations of atomic formulas are handled in the same manner.
If $\phi$ is $\alpha \lor \beta$ or $\alpha \land \beta$, the argument is left to the Exercises.
Suppose that $\mathfrak{N} \models \exists x \psi \left( x \right)$, where we assume that $\psi$ has only one free variable for simplicity. Then there is a natural number $a$ such that $\mathfrak{N} \models \psi \left( \bar{a} \right)$, and thus $N \vdash \psi \left( \bar{a} \right)$ by the inductive hypothesis. But then our second quantifier axiom tells us, as $\bar{a}$ is substitutable for $x$ in $\psi$, that $N \vdash \exists x \psi$, as needed.
Now if $\mathfrak{N} \models \left( \forall x < u \right) \psi \left( x \right)$, we know by the inductive hypothesis that
\[N \vdash \left[ \psi \left( \bar{0} \right) \land \psi \left( \bar{1} \right) \land \cdots \land \psi \left( \overline{u^\mathfrak{N} - 1} \right) \right].\]
But then by Corollary 5.3.12,
\[N \vdash \left( \forall x < \overline{u^\mathfrak{N}} \right) \psi \left( x \right).\]
Thus, since $N \vdash \overline{u^\mathfrak{N}} = u$, $N \vdash \left( \forall x < u \right) \psi \left( x \right)$, as needed.

Thus if $\mathfrak{N} \models \phi \left( \underset{\sim}{t} \right)$, then $N \vdash \phi \left( \underset{\sim}{t} \right)$.

We will say that $\phi$ is provable (from $N$) if $N \vdash \phi$. And we shall say that $\phi$ is refutable if $N \vdash \neg \phi$.

Suppose that $\phi$ is a $\Delta$-sentence. If $\mathfrak{N} \models \phi$, since we know that $\phi$ is also a $\Sigma$-sentence, Proposition 5.3.13 shows that $N \vdash \phi$. But suppose that $\phi$ is false; that is, suppose that $\mathfrak{N} \not\models \phi$. Then $\mathfrak{N} \models \neg \phi$, and $\neg \phi$ is equivalent to a $\Delta$-sentence. Thus by the same argument as above, $N \vdash \neg \phi$. So we have proved the following:

Proposition 5.3.14.

If $\phi \left( \underset{\sim}{x} \right)$ is a $\Delta$-formula with free variables $\underset{\sim}{x}$, if $\underset{\sim}{t}$ are variable-free terms, and if $\mathfrak{N} \models \phi \left( \underset{\sim}{t} \right)$, then $N \vdash \phi \left( \underset{\sim}{t} \right)$. If, on the other hand, $\mathfrak{N} \models \neg \phi \left( \underset{\sim}{t} \right)$, then $N \vdash \neg \phi \left( \underset{\sim}{t} \right)$.

corollary 5.3.15.

Suppose that $A \subseteq \mathbb{N}^k$ is defined by a $\Delta$-formula $\phi \left( \underset{\sim}{x} \right)$. Then $A$ is representable.

proof

This is immediate from Proposition 5.3.14 and Definition 5.3.1.

The astute and careful reader will have noticed that Corollary 5.3.15 is an implication and not a biconditional. So the corollary provides us with a useful and convenient way of guaranteeing that a particular set is representable, and we will avail ourselves of that guarantee frequently. The seat-of-the-pants version of the corollary is that a set with a very simple definition is representable. Although we won't be able to prove it until later (Lemma 6.3.3) there is a result that is a nod in the direction of a converse:

proposition 5.3.16.

Suppose that $A \subseteq \mathbb{N}^k$ is representable. Then there is a $\Sigma$-formula that defines $A$.

Reading carefully, you are certainly thinking that there must be some representable sets that, although they are $\Sigma$-definable, do not have a $\Delta$-definition (if there weren't any, certainly we would have proven that fact in the Corollary above, right?). You are correct, and we will return to this question in the next section. For now, we'll be happy with some practice in defining some sets with $\Delta$-formulas, and thus establishing that those sets are representable. Doing this will keep us busy for much of the rest of this chapter.

Example 5.3.17:

Suppose that we look at the even numbers. You might want to define this set by the $\mathcal{L}_{NT}$-formula

\[\phi \left( x \right) \: \text{is}: \: \left( \exists y \right) \left( x = y + y \right).\]

But we can, in fact, do even better than this. We can define the set of evens by a $\Delta$-formula

\[Even \left( x \right) = \left( \exists y \leq x \right) \left( x = y + y \right).\]

So now we have a $\Delta$-definition of $EVEN$, the set of even numbers. (We will try to be consistent and use $SMALL CAPITALS$ when referring to a set of numbers and $Italics$ when referring to the $\mathcal{L}_{NT}$-formula that defines that set.) So by Corollary 5.3.15, we see that the set of even numbers is a representable subset of the natural numbers.

Over the next few sections we will be doing a lot of this. We will look at a set of numbers and prove that it is representable by producing a $\Delta$-definition of the set. In many cases, the tricks that we will use to produce the bounds on the quantifiers will be quite impressive.

Example 5.3.18:

Take a minute and write $Prime \left( x \right)$, a $\Delta$-definition of $PRIME$, the set of prime numbers. Once you have done that, here is a definition of the set of prime pairs, the set of pairs of numbers $x$ and $y$ such that both $x$ and $y$ are prime, and $y$ is the next prime after $x$:

\[Primepair \left( x, y \right) = Prime \left( x \right) \land Prime \left( y \right) \land \left( x < y \right) \land \left[ \left( \forall z < y \right) \left( Prime \left( z \right) \rightarrow z \leq x \right) \right].\]

Notice that $Primepair$ has two free variables, as $PRIMEPAIR \subseteq \mathbb{N}^2$, while your formula $Prime$ has exactly one free variable. Also notice that all of the quantifiers in each definition are bounded, so we know the definitions are $\Delta$-definitions.

Chaff: We also hope that you noticed that in the definition of $Primepair$ we used your formula $Prime$, and we did not try to insert your entire formula every time we needed it - we just wrote $Prime \left( x \right)$ or $Prime \left( y \right)$. As you work out the many definitions to follow, it will be essential for you to do the same. Freely use previously defined formulas and plug them in by using their names. To do otherwise is to doom yourself to unending streams of unintelligible symbols. This stuff gets dense enough as it is. You do not need to make things any harder than they are.

Exercises

Show that the set $\{ 17 \}$ is representable by finding a $\Delta$-formula that defines the set. Can you come up with a (probably silly) non-$\Delta$ formula that defines the same set?
Suppose that $A \subseteq \mathbb{N}$ is representable and represented by the formula $\phi \left( x \right)$. Suppose also that $B \subseteq \mathbb{N}$ is representable and represented by $\psi \left( x \right)$. Show that the following sets are also representable, and find a formula that represents each:
(a) $A \cup B$
(b) $A \cap B$
(c) The complement of $A$, $\{ x \in \mathbb{N} | x \notin A \}$
Show that every finite subset of the natural numbers is representable and that every subset of $\mathbb{N}$ whose complement is finite is also representable.
Suppose that $f : \mathbb{N}^k \rightarrow \mathbb{N}$ is a total function. Show that $f$ is a representable function if and only if $f$ is a representable subset of $\mathbb{N}^{k+1}$.
Let $A \subseteq \mathbb{N}$. Define the characteristic function of $A$, $\chi_A : \mathbb{N} \rightarrow \mathbb{N}$ by
\[ \chi_A \left( x \right) = \begin{cases} \begin{array}{ll} 0 & \text{if} \: x \in A \\ 1 & \text{if} \: x \notin A \end{array} \end{cases}\]
Show that $A$ is a representable subset of $\mathbb{N}$ if and only if $\chi_A$ is a representable function.
Let $p \left( x \right)$ be a polynomial with nonnegative integer coefficients. Show that the set $\{ a \in \mathbb{N} | p \left( a \right) = 0 \}$ is representable. After you prove this the obvious way, find a slick way to write the proof. (Or, if you were slick the first time through, find the prosaic way!)
Write a $\Delta$-definition for the set $DIVIDES$. So you must come up with a formula with two free variables, $Divides \left( x, y \right)$, which has the property that $\mathfrak{N} \models Divides \left( \bar{a}, \bar{b} \right)$ if and only if $a$ is a factor of $b$.
Show that the set $\{ 1, 2, 4, 8, 16, \ldots \}$ of powers of 2 is representable.
Suppose that you know that $\phi \left( x, y \right)$ represents the total function $f : \mathbb{N} \rightarrow \mathbb{N}$. Show that $\psi \left( x, y \right) : \equiv \phi \left( x, y \right) \land \left( \forall z < y \right) \left( \neg \phi \left( x, z \right) \right)$ also represents $f$, and furthermore, for each $a \in \mathbb{N}$,
\[N \vdash \left( \forall y \right) \left( \psi \left( \bar{a}, y \right) \leftrightarrow y = \overline{f \left( a \right)} \right).
[Suggestion: After you show that $\psi$ represents $f$, the second part is equivalent to showing $N \vdash \psi \left( \bar{a}, \overline{f \left( a \right)} \right)$, which is pretty trivial, and then proving that
\[N \vdash \left[ \left( \phi \left( \bar{a}, y \right) \land \left( \forall z < y \right) \left( \neg \phi \left( x, z \right) \right) \right) \rightarrow y = \overline{f \left( a \right)} \right].\]
So, take as hypotheses $N$, $\phi \left( \bar{a}, y \right)$, and $\left( \forall z < y \right) \left( \neg \phi \left( x, z \right) \right)$ and show that there is a deduction of both $\neg \left[ \overline{f \left( a \right)} < y \right]$ and $\neg \left[ y < \overline{f \left( a \right)} \right]$. Then the last of the axioms of $N$ will give you what you need. For the details, see [Enderton 72, Theorem 33K].]
In the last inductive step of the proof of Lemma 5.3.10, the use of the inductive hypothesis is rather hidden. Please expose the use of the inductive hypothesis and write out that step of the proof more completely. Finish the cases for multiplication and exponentiation.
Prove Corollary 5.3.12.
Fill in the details of the steps omitted in the inductive proof of Proposition 5.3.13. In the last two cases, how does the argument change if there are more free variables? If, for example, instead of $\phi$ being the of the form $\exists x \psi \left( x \right)$, $\phi$ is of the form $\exists x \psi \left( x, y \right)$, does that change the proof?
We will say that a formula $\phi \left( x \right)$ with one free variable is positively numeralwise determined if, for each $a \in \mathbb{N}$, if $\mathfrak{N} \models \phi \left( a \right)$ then $N \vdash \phi \left( \bar{a} \right)$. Say $\phi \left( x \right)$ is numeralwise determined if both $\phi \left( x \right)$ and $\neg \phi \left( x \right)$ are positively numeralwise determined. Prove that $\phi$ represents a set $A$ if and only if $\phi$ defines $A$ and $\phi$ is numeralwise determined. To reiterate, a set $A$ is representable if and only if $A$ has a numeralwise determined definition.
Show that every atomic formula is numeralwise determined. Then show that the collection of numeralwise determined formulas is closed under $\neg$, $\lor$, $\land$, and bounded quantification.