/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Problem 12 Let \(f\) be a total recursive f... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 6: Problem 12

Let \(f\) be a total recursive function from \(\mathbb{N}\) into \(\mathbb{N}\) and let \(F\left[v_{0}, v_{1}\right]\) be a \(\Sigma\) formula that represents it and is such that $$ \mathcal{P} \vdash \forall v_{1} \exists v_{0} F\left[v_{0}, v_{1}\right] . $$ The purpose of this exercise is to show that there exist total recursive functions that are not provably total. (a) Let \(F\left[v_{0}, v_{1}, \ldots, v_{k}\right]\) be a \(\Sigma\) formula. Show that the set $$ \left\\{\left(n_{0}, n_{1}, \ldots, n_{k}\right): \mathbb{N} \vDash F\left[n_{0}, n_{1}, \ldots, n_{k}\right]\right\\} $$ is recursively enumerable. (b) Let \(f\) be a total function from \(\mathbb{N}\) into \(\mathbb{N}\). Show that the following two conditions are equivalent: (i) \(f\) is recursive; (ii) there exists a \(\Sigma\) formula that represents \(f\). (c) Show that there exists a partial recursive function \(h\) of two variables such that, for every integer \(n\), \- if \(a\) is the G枚del number of \(\Sigma\) formula, say \(F\left[v_{0}, v_{1}\right]\), and if there exists an integer \(m\) such that \(\mathcal{P} \vdash F[\underline{m}, \underline{n}]\), then $$ \mathcal{P} \vdash F[\underline{h(a, n)}, \underline{n}] $$ \- if \(a\) is the G枚del number of the formula \(F\left[v_{0}, v_{1}\right]\) and if there does not exist an integer \(m\) such that \(\mathcal{P} \vdash F[\underline{m}, \underline{n}]\), then \(h(a, n)\) is not defined; \- \(h(a, n)=0\) otherwise. (d) We now define a function \(g\) from \(\mathbb{N}^{3}\) into \(\mathbb{N}\) in the following way: for every integer \(n\), \- if \(a\) is the G枚del number of a \(\Sigma\) formula \(F\left[v_{0}, v_{1}\right]\) and if \(b\) is the G枚del number of a derivation in \(\mathcal{P}\) of the formula \(\forall v_{1} \exists v_{0} F\left[v_{0}, v_{1}\right]\) then \(g(a, b, n)=h(a, n)\); \- \(g(a, b, n)=0\) otherwise. Show that \(g\) is a total recursive function. (e) Show that there exist total recursive functions that are not provably total.

Short Answer

Expert verified
Under the principles of computational mathematics and logic, the exercise demonstrates the recursive enumerability of certain sets, the equivalence of recursive functions with Sigma formulas that represent them, and the existence of partial recursive functions complying with specific conditions. It also establishes the existence of total recursive functions defined by G枚del numbers and shows that there exist total recursive functions that are not provably total due to the incompleteness of the proof system, backed by G枚del's incompleteness theorem.

Step by step solution

01

Part A: Recursive Enumerability of Sets Represented by Sigma Formulas

We begin by noting the definition of a sigma formula - it is a propositional formula that uses only bounded universal quantifiers and unbounded existential quantifiers. With this in mind, the set \n\[ \n\{ \left(n_{0}, n_{1}, \ldots, n_{k}\right): \mathbb{N} \vDash F\left[n_{0}, n_{1}, \ldots, n_{k}\right]\}\n\] \nwhere \(\mathbb{N} \vDash F\left[n_{0}, n_{1}, \ldots, n_{k}\right]\) implies that formula is true in the standard model of arithmetic, is the set of all tuples of natural numbers that satisfy the formula.Following the definition of recursive enumeration, this set is recursively enumerable if there exists a Turing machine that lists all elements of the set. Due to the construction of the sigma formula, which employs the existential quantifier (\(\exists\)), there exists an algorithm to search for an element that satisfies the formula. Hence, a Turing machine can be crafted to list all elements of the natural number tuples that satisfy the formula, rendering the set recursively enumerable.
02

Part B: Equivalence of Recursive Function and Representing Sigma Formula

The function \(f\) is called recursive if there exists an algorithm which takes as input the natural number \(n\) and outputs the corresponding value \(f(n)\). The task is now to connect this with the existence of a sigma formula \(F[v_{0}, v_{1}]\) that represents \(f\). It should be recalled that a sigma formula is a propositional formula that uses only bounded universal quantifiers and unbounded existential quantifiers. If \(f\) is recursive, then we can logically express this search for \(v_{0}\) as an unbounded existential quantifier over \(v_{0}\) (i.e., \(\exists v_{0}\)), and hence use a sigma formula to represent \(f\). Conversely, if a sigma formula \(F[v_{0}, v_{1}]\) represents \(f\), we can retrieve a recursive function via the Turing machine that searches for an array which satisfies the formula - thus proving the equivalence of (i) and (ii).
03

Part C: Existence of a Partial Recursive Function

Here, define a partial recursive function (i.e. a function which is computable but that can potentially leave some input undefined) based on the G枚del number of a sigma formula. If the G枚del number of the formula is \(a\) and an integer \(m\) exists such that \(\mathcal{P}\vdash F[\underline{m}, \underline{n}]\), then we can define the partial recursive function as \(h(a, n) = 0\). If no such integer \(m\) exists, then the function is undefined.
04

Part D: Defining a Total Recursive Function

Based on the partial recursive function defined in the previous step, it's now possible to define the function \(g\) from \(\mathbb{N}^{3}\) into \(\mathbb{N}\). For every integer \(n\), if \(a\) is the G枚del number of a \(\Sigma\) formula $F\left[v_{0}, v_{1}\right]$ and if \(b\) is the G枚del number of a derivation in \(\mathcal{P}\) of the formula \(\forall v_{1} \exists v_{0} F\left[v_{0}, v_{1}\right]\), then \(g(a, b, n)\) = \(h(a, n)\). If no such number exists, then \(g(a, b, n)\) = \(0\). Since both conditions are computable and \(\mathcal{P}\) is provably total, the function \(g\) is also a total recursive function.
05

Part E: Existence of Total Recursive functions that are not Provably Total

A proof that there exists a total recursive function that is not provably total would require a direct showing that the proof system itself is incomplete (i.e., there exist true statements in the system that cannot be proved), or an indirect demonstration by exploiting a divergence such as G枚del's incompleteness theorem. It can be deduced that considering a function that produces the nth G枚del number of a provable statement (which is itself constructive and thus total recursive), if we could prove this function was total, it would result in proving the consistency of the system, which by G枚del's second incompleteness theorem, is impossible, if the system is consistent. Therefore, it is backed by a pretty strong theoretical framework that there do exist total recursive functions that are not provably total.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with 91影视!

Key Concepts

These are the key concepts you need to understand to accurately answer the question.

Total Recursive Function
A total recursive function is a type of function with special properties. It's defined for every input, meaning for every natural number you plug in, you'll get another natural number as a result. These functions are directly connected to the concept of algorithms. If you have an algorithm that can compute outputs for every possible input, then you have a total recursive function.

In formal terms, a total recursive function is computable by a Turing machine. This means that no matter what number you give, the machine will go through its steps and provide you with a result.

Total recursive functions are essential in mathematics and computer science as they form the basis for many computational theories. They contrast with partial recursive functions, which may not be defined for every input.
Sigma Formula
Sigma formulas, or \(\Sigma\) formulas, utilize specific logical constructs to express mathematical propositions. They involve the use of existential quantifiers (\(\exists\)), which allow us to express the existence of certain elements that satisfy a given condition.

A sigma formula is represented in the form \(F[v_0, v_1, \ldots, v_k]\) where it can express relationships between several variables. It uses only bounded universal quantifiers, making it particularly useful in recursion theory to describe certain types of recursive functions.

For instance, a sigma formula can represent a function \(f\) by expressing conditions that relate its input and output. If \(f\) is recursive, then there exists a sigma formula that can encapsulate its behavior, and vice versa. This mutual relation is crucial for understanding the recursive nature of functions in mathematical logic.
G枚del's Incompleteness Theorem
G枚del's Incompleteness Theorem is a fundamental result in mathematical logic. It states two major things about formal systems, like those used in mathematics:
  • First, any consistent formal system sufficient to express arithmetic cannot be complete. This means there are true statements within the system that cannot be proven using the system itself.
  • Second, such a system cannot demonstrate its consistency. If it could prove its consistency, it would be inconsistent.

This theorem has profound implications. For instance, it shows there exist total recursive functions that are not provably total within certain systems. Even if a function is total (defined for all inputs), proving its totality might be impossible within the constraints of the system.

This limitation illustrates the inherent boundaries within mathematical systems and highlights the complex interaction between computation and logical proofs.
Recursively Enumerable Set
A recursively enumerable set is a collection of numbers that can be listed or enumerated by a Turing machine. However, this doesn't mean you can determine if any arbitrary number belongs to the set.

Unlike recursive sets, where membership of a number can be determined with certainty, a recursively enumerable set might only let you enumerate over elements that satisfy a specific criterion.

Recursive enumerability is significant because it connects to the idea of computability. If a set is recursively enumerable, there's a procedure (an algorithm) to list its elements, even if that procedure can't decide membership outright for every potential element. This subtlety is crucial when dealing with problems in the realm of logic and number theory, as it frequently frames the relationship between machines and mathematical expressions.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

This exercise should be worked after reading Chapter 7 on set theory. In particular, one needs to know what the cardinal number \(2^{\kappa_{0}}\) is. (a) Show that if \(T\) is a consistent theory obtained by adjoining a finite number of formulas to \(\mathcal{P}\), then \(T\) is not complete. (b) For every integer \(n\) and every sequence $$ s=(s(0), s(1), \ldots, s(n-1)) \in\\{0,1\\}^{n}, $$ construct a closed formula \(F_{s}\) such that, for all \(s\), (i) \(F_{(s(0), s(1), \ldots, s(n-1), 1)}=\neg F_{(s(0), s(1), \ldots, s(n-1), 0)}\); (ii) \(\mathcal{P} \cup\left\\{F_{\emptyset}, F_{(s(0))}, F_{(s(0), s(1))}, \ldots, F_{(s(0), s(1), \ldots, s(n-1))}\right\\}\) is a consistent theory. (c) Show that there exist \(2^{\kappa_{0}}\) theories that include \(\mathcal{P}\) and that are pairwise inequivalent.

Show that there exists a formula \(F\left[v_{0}\right]\) of \(\mathcal{L}_{0}\) such that \(\mathbb{N} \vDash \neg \exists v_{0} F\left[v_{0}\right]\) and \(\neg \exists v_{0} F\left[v_{0}\right]\) is not derivable in \(\mathcal{P}\). Conclude from this that, for every formula \(G\left[v_{0}, v_{1}, \ldots, v_{n}\right]\), there exists a formula \(H\left[v_{0}, v_{1}, \ldots, v_{n}\right]\) such that $$ \forall v_{0} \forall v_{1} \ldots \forall v_{n}\left(G\left[v_{0}, v_{1}, \ldots, v_{n}\right] \Leftrightarrow H\left[v_{0}, v_{1}, \ldots, v_{n}\right]\right) $$ is true in \(\mathbb{N}\) but is not derivable in \(\mathcal{P}\).

Let \(X\) be a non-empty set and let \(f\) be a function from \(X \times X\) into \(X\). Consider the \(\mathcal{L}_{0}\)-structure \(\mathcal{M}\) whose base set is \(M=\mathbb{N} \cup(X \times \mathbb{Z})\) and in which the symbols \(\underline{S}, \underline{+}\), and \(\underline{\times}\) are interpreted by the functions \(S,+\), and \(\times\) that are defined by the following conditions: \- \(M\) is an extension of \(\mathbb{N}\); \- if \(a=(x, n) \in M-\mathbb{N}\), then \(S(a)=(x, n+1)\); \- if \(a=(x, n) \in M-\mathbb{N}\) and \(m \in \mathbb{N}\), then \(a+m=m+a=(x, n+m) ;\) \- if \(a=(x, n)\) and \(b=(y, m)\) are elements of \(M-\mathbb{N}\), then \((x, n)+(y, m)=\) \((x, n+m)\) \- if \(a=(x, n) \in M-\mathbb{N}\) and \(m \in \mathbb{N}\), then \((x, n) \times m=(x, n \times m)\) if \(m \neq 0\) and \((x, n) \times 0=0\); \- if \(a=(x, n) \in M-\mathbb{N}\) and \(m \in \mathbb{N}\), then \(m \times(x, n)=(x, m \times n)\); \- if \(a=(x, n)\) and \(b=(y, m)\) are elements of \(M-\mathbb{N}\), then \((x, n) \times(y, m)=\) \((f(x, y), n \times m)\). (a) Show that \(\mathcal{M}\) is a model of \(\mathcal{P}_{0}\). (b) Show that none of the following formulas is a consequence of \(\mathcal{P}_{0}\) : (i) \(\forall v_{0} \forall v_{1} v_{0} \pm v_{1} \simeq v_{1} \pm v_{0}\); (ii) \(\forall v_{0} \forall v_{1} \forall v_{2} v_{0} \times\left(v_{1} \times v_{2}\right) \simeq\left(v_{0} \times v_{1}\right) \times v_{2} ;\) (iii) \(\forall v_{0} \forall v_{1}\left(\left(v_{0} \leq v_{1} \wedge v_{1} \leq v_{0}\right) \Rightarrow v_{0} \simeq v_{1}\right)\); (iv) \(\forall v_{0} \underline{0} \times v_{0} \simeq \underline{0}\). (c) Construct a model of \(\mathcal{P}_{0}\) in which addition is not associative. Show that the relation \(R\) is a total ordering. Show that \(E\), with respect to this ordering, has a least element but does not have a greatest element. Show that \(R\) is a dense ordering of \(E\).

Let \(X\) be a non-empty set and let \(f\) be a function from \(X \times X\) into \(X\). Consider the \(\mathcal{L}_{0}\)-structure \(\mathcal{M}\) whose base set is \(M=\mathbb{N} \cup(X \times \mathbb{Z})\) and in which the symbols \(\underline{S}, \underline{+}\), and \(\underline{\times}\) are interpreted by the functions \(S,+\), and \(\times\) that are defined by the following conditions: \- \(M\) is an extension of \(\mathbb{N}\); \- if \(a=(x, n) \in M-\mathbb{N}\), then \(S(a)=(x, n+1)\); \- if \(a=(x, n) \in M-\mathbb{N}\) and \(m \in \mathbb{N}\), then \(a+m=m+a=(x, n+m) ;\) \- if \(a=(x, n)\) and \(b=(y, m)\) are elements of \(M-\mathbb{N}\), then \((x, n)+(y, m)=\) \((x, n+m)\) \- if \(a=(x, n) \in M-\mathbb{N}\) and \(m \in \mathbb{N}\), then \((x, n) \times m=(x, n \times m)\) if \(m \neq 0\) and \((x, n) \times 0=0\); \- if \(a=(x, n) \in M-\mathbb{N}\) and \(m \in \mathbb{N}\), then \(m \times(x, n)=(x, m \times n)\); \- if \(a=(x, n)\) and \(b=(y, m)\) are elements of \(M-\mathbb{N}\), then \((x, n) \times(y, m)=\) \((f(x, y), n \times m)\). (a) Show that \(\mathcal{M}\) is a model of \(\mathcal{P}_{0}\). (b) Show that none of the following formulas is a consequence of \(\mathcal{P}_{0}\) : (i) \(\forall v_{0} \forall v_{1} v_{0} \pm v_{1} \simeq v_{1} \pm v_{0}\); (ii) \(\forall v_{0} \forall v_{1} \forall v_{2} v_{0} \times\left(v_{1} \times v_{2}\right) \simeq\left(v_{0} \times v_{1}\right) \times v_{2} ;\) (iii) \(\forall v_{0} \forall v_{1}\left(\left(v_{0} \leq v_{1} \wedge v_{1} \leq v_{0}\right) \Rightarrow v_{0} \simeq v_{1}\right)\); (iv) \(\forall v_{0} \underline{0} \times v_{0} \simeq \underline{0}\). (c) Construct a model of \(\mathcal{P}_{0}\) in which addition is not associative.

In this exercise, \(\operatorname{Drv}\left[v_{0}, v_{1}\right]\) is a formula that represents the set Drv \(=\\{(a, b): b\) is the G枚del number of a derivation in \(\mathcal{P}\) of the formula whose G枚del number is \(a\\}\). Among the following assertions, which are true for any closed formula \(F ?\) (a) \(\mathbb{N} \vDash \exists v_{1} \operatorname{Dr} v\left[\\# F, v_{1}\right] \Rightarrow F\); (b) \(\mathcal{P} \vdash \exists v_{1} \operatorname{Drv}\left[\\# F, v_{1}\right] \Rightarrow F\); (c) \(\mathbb{N} \vDash F \Rightarrow \exists v_{1} \operatorname{Drv}\left[\\# F, v_{1}\right]\); (d) \(\mathcal{P} \vdash F \Rightarrow \exists v_{1} \operatorname{Drv}\left[\\# F, v_{1}\right]\).
See all solutions

Recommended explanations on Math Textbooks

Calculus

Read Explanation

Discrete Mathematics

Read Explanation

Pure Maths

Read Explanation

Logic and Functions

Read Explanation

Theoretical and Mathematical Physics

Read Explanation

Statistics

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.