Processing math: 77%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

5.3: Representable Sets and Functions

( \newcommand{\kernel}{\mathrm{null}\,}\)

For the sake of discussion, suppose that we let f(x)=x2. It will not surprise you to find out that f(4)=16, so we would like to write Nf(4)=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 LNT. To be specific, suppose that ϕ(x,y) is

y=ExSS0.

Then, if we allow ourselves once again to use the abbreviation ˉa for the LNT-term SSSS0(aS's), we can assert that

Nϕ(ˉ4,¯16)

which is the same thing as

N⊨=SSSSSSSSSSSSSSSS0ESSSS0SS0.

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

  • Nϕ(ˉ4,¯16)
  • N¬ϕ(ˉ4,¯17)
  • N¬ϕ(ˉ1,¯714)

In fact, this formula ϕ is such, and N is such, that if a is any natural number and b=f(a), then

Ny[ϕ(ˉa,y)y=ˉb].

We will say that the formula ϕ represents the function f in the theory N.

Definition 5.3.1.

A set ANk is said to be representable (in N) if there is an LNT-formula ϕ(x) such that

aANϕ(ˉa)bAN¬ϕ(ˉb).

In this case we will say that the formula ϕ represents the set A.

Definition 5.3.2.

A set ANk is said to be weakly representable (in N) if there is an LNT-formula ϕ(x) such that

aANϕ(ˉa)bANϕ(ˉb).

In this case we will say that the formula ϕ 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 LNT-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 x1,x2,,xk over and over and over again in the next few sections, we will abbreviate this as x. Similarly, ˉx is shorthand for ¯x1,¯x2,,¯xk. 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:NkN 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 Nk, 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 ANk and suppose that f:AN. If A=Nk we will say that f is a total function. If ANk, 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:NkN is a total function. We will say that f is a representable function (in N) if there is an LNT-formula ϕ(x1,,xk+1) such that, for all a1,a2,,ak+1N,

Iff(a1,,ak)=ak+1,thenNϕ(¯a1,,¯ak+1)Iff(a1,,ak)ak+1,thenN¬ϕ(¯a1,,¯ak+t).

Notice that a total function is a representable function if and only if it is a representable subset of Nk+1. See Exercise 4.

Definition 5.3.5.

Suppose that ANk and f:AN is a (possibly) partial function. We will say that f is a weakly representable function (in N) if there is an LNT-formula ϕ(x1,,xk+1) such that, for all a1,a2,,ak+1N,

Iff(a1,,ak)=ak+1,thenNϕ(¯a1,,¯ak+1)Iff(a1,,ak)ak+1,thenNϕ(¯a1,,¯ak+1).

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(5) is not going to be equal to anything, so we know that f(5)17. All we ask, in that case, is that N does not prove ϕ(ˉ5,¯17). We do not need, and cannot expect, N to prove ¬ϕ(ˉ5,¯17).

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 Nk to 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:NkN is a total function. Then the following are equivalent.

  1. f is a representable function.
  2. There exists an LNT-formula ψ(x1,,xk+1) such that for all aNk,
    N(y)[ψ(ˉa,y)y=¯f(a)].
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 μ-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 ANk is definable if there is a formula ϕ(x) such that

aANϕ(ˉa)bAN¬ϕ(ˉb).

In this case, we will say that ϕ defines the set A.

Chaff: It is very important to notice the difference between saying that ϕ represents A and ϕ defines A, which is the same as the difference between N and N. 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 LNT formulas that are true in N, namely the class of true Σ-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 Δ-formula if it contains only bounded quantifiers. Slightly more complicated are the Σ-formulas, which can contain bounded quantifiers and unbounded existential quantifiers, and Π-formulas, which can use both bounded quantifiers and unbounded universal quantifiers.

Example 5.3.9:

Here is a perfectly nice example of a Δ-formula ϕ: (x<t)(x=0). Notice that the denial of ϕ is not a Δ-formula, as ¬(x<t)(x=0) is neither a Σ- nor a Π-formula. But a chain of logical equivalences shows us that ¬ϕ is equivalent to a Δ-formula if we just push the negation sign inside the quantifier:

¬ϕ¬(x<t)(x=0)(x<t)¬(x=0).

Similarly, we can show that any propositional combination (using , , ¬, , ) of Δ-formulas is equivalent to a Δ-formula. We will use this fact approximately 215,342 times in the remainder of this book.

A Σ-sentence is, of course, a Σ-formula that is also a sentence. We will be particularly interested in Σ-formulas and Δ-formulas, for we will show if ϕ is a Σ-sentence and Nϕ, then the axiom set N is strong enough to provide a deduction of ϕ. Since every Δ-sentence is also a Σ-sentence, any Δ-sentence that is true in 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 tN is the interpretation of that term in the structure N. For example, suppose that t is the term ESSS0SS0, also known as SSS0SS0. Then tN would be the number 9, and ¯tN would be the term SSSSSSSSS0. So when this lemma says that N proves t=¯tN, you should think that N proves SSS0SS0=SSSSSSSSS0, which is the same as saying that Nˉ3ˉ2=ˉ9.

lemma 5.3.10.

For each variable-free term t, Nt=¯tN.

proof

We proceed by induction on the complexity of the term t. If t is the term 0, then tN is the natural number 0, and ¯tN is the term 0. Thus we have to prove that N0=0, which is an immediate consequence of our logical axioms.

If t is S(u), where u is a variable-free term, then the term ¯tN is identicala to the term S(¯uN). Also, Nu=¯uN, by the inductive hypothesis, and thus NSu=S(¯uN), thanks to the equality axiom (E2). Putting all of this together, we get that Nt=Su=S(¯uN)=¯tN, as needed.

If t is u+v, we recall that Lemma 2.8.4 proved that N¯uN+¯vN=¯uN+vN. But then Nt=u+v=¯uN+¯vN=¯uN+vN=¯tN, which is what we needed to show. The arguments for terms of the form uv or uv are similar, so the proof is complete.

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

lemma 5.3.11: Rosser's lemma

If a is a natural number,

N(x<ˉa)[x=ˉ0x=ˉ1x=¯a1].

proof

We use induction on a. If a=0, it suffices to prove that Nx[x<0→⊥]. By Axiom 9 of N, we know that N¬(x<0), so N(x<0)→⊥, as needed.

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

Nx[x<¯b+1x=ˉ0x=ˉb].

Since ¯b+1 and Sˉb are identical, it suffices to show that

Nx[x<¯Sbx=ˉ0x=ˉb].

By Axiom 10, we know that Nx<Sˉb(x<ˉbx=ˉb), and then by the inductive hypothesis, we are finished.

corollary 5.3.12.

If a is a natural number, then

N[[(x<ˉa)ϕ(x)][ϕ(ˉ0)ϕ(ˉ1)ϕ(¯a1)]].

proof

Exercise 11.

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

proposition 5.3.13.

If ϕ(x) is a Σ-formula with free variables x, if t are variable-free terms, and if Nϕ(t), then Nϕ(t).

proof

This is a proof by induction on the complexity of the formula ϕ.

  1. If ϕ is atomic, say for example that ϕ is x<y and terms t and u are such that Nt<u. Then tN<uN, so by Lemma 2.8.4, N¯tN<¯uN. But we also know Nt=¯tN and Nu=¯uN, by Lemma 5.3.10, so Nt<u, as needed.
  2. Negations of atomic formulas are handled in the same manner.
  3. If ϕ is αβ or αβ, the argument is left to the Exercises.
  4. Suppose that Nxψ(x), where we assume that ψ has only one free variable for simplicity. Then there is a natural number a such that Nψ(ˉa), and thus Nψ(ˉa) by the inductive hypothesis. But then our second quantifier axiom tells us, as ˉa is substitutable for x in ψ, that Nxψ, as needed.
  5. Now if N(x<u)ψ(x), we know by the inductive hypothesis that
    N[ψ(ˉ0)ψ(ˉ1)ψ(¯uN1)].
    But then by Corollary 5.3.12,
    N(x<¯uN)ψ(x).
    Thus, since N¯uN=u, N(x<u)ψ(x), as needed.

Thus if Nϕ(t), then Nϕ(t).

We will say that ϕ is provable (from N) if Nϕ. And we shall say that ϕ is refutable if N¬ϕ.

Suppose that ϕ is a Δ-sentence. If Nϕ, since we know that ϕ is also a Σ-sentence, Proposition 5.3.13 shows that Nϕ. But suppose that ϕ is false; that is, suppose that Nϕ. Then N¬ϕ, and ¬ϕ is equivalent to a Δ-sentence. Thus by the same argument as above, N¬ϕ. So we have proved the following:

Proposition 5.3.14.

If ϕ(x) is a Δ-formula with free variables x, if t are variable-free terms, and if Nϕ(t), then Nϕ(t). If, on the other hand, N¬ϕ(t), 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

  1. 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?
  2. 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 \}
  3. 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.
  4. 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}.
  5. 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.
  6. 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!)
  7. 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.
  8. Show that the set \{ 1, 2, 4, 8, 16, \ldots \} of powers of 2 is representable.
  9. 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].]
  10. 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.
  11. Prove Corollary 5.3.12.
  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?
  13. 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.
  14. 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.

This page titled 5.3: Representable Sets and Functions is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Christopher Leary and Lars Kristiansen (OpenSUNY) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?