Recursive and primitive recursive sets and predicates

[26/58%]

Show

LaTeX

Show LaTeX

Problem 328 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Лекции по дискретной математике" [ДДК+21a]More problems in Chapter 21 "Computability and Undecidable Problems"

Let $A$ be a decidable set, and let $g(x)$ and $h(x)$ be general recursive functions. Prove that the function

F(x)= \begin{cases} g(x), & \text{ if } x \in A, \\ h(x), & \text{ otherwise } \end{cases}

is also general recursive.

Problem 620 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Задачник по дискретной математике" [ДДК+21b]More problems in Chapter 25 "The Turing-Church Thesis and Undecidable Problems"

Let $A$ be a decidable set, and let $g(x)$ and $h(x)$ be g.r.f.'s. Prove that the function

F(x)= \begin{cases} g(x), & \text{ if } x \in A, \\ h(x), & \text{ otherwise }\end{cases}

is also general recursive.

Problem 5.4.7 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 5.4 "Reducibility"

Define

f(n)= \begin{cases} \min \left\{ W_{n}\right\} & \text{ if } W_{n} \neq \emptyset , \\ \uparrow & \text{ otherwise }.\end{cases}

Is $f$ a partial recursive function? Prove your answer.

Problem III.3.1 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that the following predicates are primitive recursive:

(a)

$x = y$ ;

(b)

$x + y = z$ ;

(c)

$x \cdot y = z$ ;

(d)

$x$ divides $y$ ;

(e)

$x$ is even;

(f)

$x$ and $y$ are relatively prime;

(g)

$\exists n(x = 1^{2} + 2^{2} + \ldots + n^{2})$ ;

(h)

$\exists n(x = 1 + 2 + \ldots + n)$ .

Problem III.3.2 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that if $P(x_{1}, \ldots , x_{n})$ and $Q(x_{1}, \ldots , x_{n})$ are recursive (primitive recursive) predicates, then the following predicates are also recursive (primitive recursive):

(a)

$(P(x_{1}, \ldots , x_{n})\ \& \ Q(x_{1}, \ldots , x_{n}))$ ;

(b)

$(P(x_{1}, \ldots , x_{n}) \lor Q(x_{1}, \ldots , x_{n}))$ ;

(c)

$\neg P(x_{1}, \ldots , x_{n})$ ;

(d)

$(P(x_{1}, \ldots , x_{n}) \supset Q(x_{1}, \ldots , x_{n}))$ ;

(e)

$P(x_{1}, x_{1}, x_{3}, \ldots , x_{n})$ ;

(f)

$P(f(x_{1}, \ldots , x_{m}), x_{m+1}, \ldots , x_{m+n-1})$ , if $f(x_{1}, \ldots , x_{m})$ is g.r. (p.r.).

Problem III.3.3 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that if the predicate $R(x_{1}, \ldots , x_{n}, y)$ is recursive (primitive recursive), then the predicates $\exists y (y \leq z\ \& \ R(x_{1}, \ldots , x_{n}, y))$ and $\forall y (y \leq z \supset R(x_{1}, \ldots , x_{n}, y))$ are also recursive (primitive recursive).

Problem III.3.6 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that any finite set of natural numbers is primitive recursive.

Problem III.3.7 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that a set of $n$ -tuples is recursive (primitive recursive) if and only if its characteristic function is general recursive (primitive recursive).

Problem III.3.8 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that if $f$ is a general recursive (primitive recursive) function and $a$ is a fixed number, then the set of solutions of the equation $f(x_{1}, \ldots , x_{n}) = a$ is recursive (primitive recursive).

Problem III.3.9 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Let the function $f$ be partial recursive but not general recursive. Prove that the domain of definition of the function $f^{-1}$ is primitive recursive.

Problem III.3.10 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that if the sets $A$ and $B$ are recursive (primitive recursive), then the sets $A \cap B$ , $A \cup B$ , $\mathbb {N} \setminus A$ are also recursive (primitive recursive).

Problem III.3.12 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that every primitive recursive set is recursively enumerable.

Problem III.3.13 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

(a)(b)

Let the sets $A$ and $B$ differ by finitely many elements. Prove that:

(a)

if $A$ is recursive, then $B$ is recursive;

(b)

if $A$ is recursively enumerable, then $B$ is recursively enumerable.

Problem III.3.15 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

(a)(b)(c)

Let $M \subseteq \mathbb {N}^{n}$ . Set

c^{n}(M) = \left\{ c^{n}(x_{1}, \ldots , x_{n}) \mid \langle x_{1}, \ldots , x_{n} \rangle \in M\right\} ,

where $c^{n}$ is defined in problem III.1.14. Prove that:

(a)

$M$ is primitive recursive if and only if $c^{n}(M)$ is primitive recursive;

(b)

$M$ is recursive if and only if $c^{n}(M)$ is recursive;

(c)

$M$ is recursively enumerable if and only if $c^{n}(M)$ is recursively enumerable.

Problem III.3.18 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Let the general recursive function $f(x)$ satisfy the condition: $f(x) \geq x$ for all $x \in \mathbb {N}$ . Prove that the range of values $\rho_{f}$ of the function $f$ is recursive.

Problem III.3.19 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that an infinite set $A$ is recursive if and only if $A$ is the range of values of a strictly increasing general recursive function.

Problem III.3.20 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that a nonempty set $A$ is recursive if and only if $A$ is the range of values of a monotonically (not necessarily strictly) increasing general recursive function.

Problem III.3.21 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that every infinite recursively enumerable set contains an infinite recursive subset.

Problem III.3.23 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that the graph of a general recursive function is recursive.

Problem III.3.25 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that the full preimage of a recursive set under a general recursive function is recursive.

Problem III.3.26 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Let $A$ be a recursive set, $f$ a general recursive function with $\rho_{f} = \mathbb {N}$ , $f(A) \cap f(\mathbb {N} \setminus A) = \emptyset$ . Prove that $f(A)$ is recursive.

Problem III.3.27 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Let $A, B$ be recursively enumerable sets, and $C$ a recursive set such that $A \cap B = \emptyset$ , $A \subseteq C \subseteq A \cup B$ . Prove that $A$ is recursive.

Problem III.3.28 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Let $f, g$ be general recursive functions, with $g$ a 1--1 function. Suppose also that $f(x) \geq g(x)$ for all $x$ . Prove that if $\rho_{g}$ is recursive, then $\rho_{f}$ is recursive.

Problem III.3.34 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that any recursive set is recursively enumerable.

Problem III.3.44 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.3 "Recursive and Recursively Enumerable Sets"

Prove that if the domain of definition of a partial recursive function $f^{n}$ is a recursive set, then $f^{n}$ has a recursive extension.

Problem III.4.32 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"

Prove that every recursive set is $m$ -reducible to any nonempty set with nonempty complement.

References

[ДДК+21a] Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. Лекции по дискретной математике. 3-е изд., Тверской государственный университет, 2021.

[ДДК+21b] Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. Задачник по дискретной математике. 2-е изд., Тверской государственный университет, 2021.

[DuKo01] Du D., Ko K. Problem Solving in Automata, Languages, and Complexity. John Wiley & Sons, 2001.

[LaMa02] Lavrov I.A., Maksimova L.L. Задачи по теории множеств, математической логике и теории алгоритмов. 5-е изд., Физматлит, 2002.