CSC363 UTM Winter 2024 Assignment 2 Due Wednesday February 28
You are not allowed to post the assignment questions anywhere; however, you are allowed to search the internet (just cite your resources if you find any). You are also allowed to bounce ideas off classmates and TAs, but at the end, you must write your own solutions.
Q1. Let R(x, y) be a primitive recursive relation, prove that the relation P (x, n) : ∀y < n, R(x, y) is primitive recursive. Is the same true if the word primitive recursive is replaced by computable?
Q2. Let A be a set of natural numbers. Consider the following three statements: P : The set A is the domain of a partial computable function.
Q: The set A is empty.
R: The set A is the range of some computable function.
Prove that: P ⇐⇒ Q ∨ R.
Recall the following from Propositional Logic:
To prove the direction =⇒, it is often easier to use elimination and, instead, prove the following equivalent implication P ∧ ¬Q ⇒ R.
To prove the other direction ⇐= , you need to prove Q =⇒ P and R =⇒ P.
Q3. Let f : N → N be a strictly increasing function. Show that Range(f) is a decidable set.
Q4. Prove that every infinite semidecidable set contains an infinite decidable subset.
Q5. Prove that if a set A of natural numbers is semidecidable and infinite, then there exists an injective computable function f : N → N such that Range(f) = A.
Q6. Let R be a binary relation on N, and let A be the following set A = {x ∈ N: ∃y,R(x,y)}.
Recall that R(x, y) is just a shorthand to writing (x, y) ∈ R. Assume that R is computable. Prove that A is c.e.
Q7. Let A be a c.e. set of natural numbers. Show that there exists a computable binary relation RA on N such that
A = {x ∈ N: ∃y,RA(x,y)}.
Notice that Q7 is asking you to prove the converse implication of Q6.
Q8. A set P of natural numbers is said to be productive if there exists a p.c. function φ such that ∀x[Wx⊆P=⇒(φ(x)↓ ∧φ(x)∈P\Wx)].
Prove that, if P is productive, then P is not c.e. 1
CS Help, Email: tutorcs@163.com
CSC363 UTM Winter 2024 Assignment 2 Due Wednesday February 28
Q9. Prove that the set Tot of indices of (total) computable functions is NOT c.e.
Hint: Assume towards a contradiction that it is c.e. Show that this assumption implies the existence of some computable f such that {φf (e) : e ∈ N} is the set of indices of computable functions. This will imply that the function given by g(x) = φf(x)(x) + 1 is computable (why?). Find a contradiction.
Q10. Let P(N) be the set of all subsets of N (the power set of N). Prove that the relation ≤m on the set P(N) is a partial order but not a total order.
Q11. Consider the relation ≡m on P(N) defined as follows:
A ≡ m B ⇐⇒ [ A ≤ m B ∧ A ≥ m B ] .
Prove that ≡m is an equivalence relation on P(N). Then, show that there is uncountably many equivalence classes for that relation.
Q12. The Parameter Theorem (also known as s-m-n theorem):
There is a computable function s: N2 → N such that for all x,y,z ∈ N,
φs(x,y)(z) = φx(y, z).
Q13. Given sets of natural numbers , we can define the join of these sets as
⊕i∈NAi = {⟨i,x⟩: i ∈ N, x ∈ Ai}.
Prove that:
(a) Foralli∈N,Ai ≤m N.
(b) If C is such that Ai ≤m C for all i ∈ N, then ⊕i∈NAi ≤m C.
The rest of this assignment are bonus questions.
CSC363 UTM Winter 2024 Assignment 2 Due Wednesday February 28
The Arithmetical Hierarchy (bonus)
In Questions 6 and 7, you were asked to show that a set A is c.e. iff A has a particular syntactical form:
A is c.e. ⇔ there is a computable binary relation R such that A = {x ∈ N: ∃y,R(x,y)}.
The syntactical form “∃y, R(x, y)” is known as Σ01. Syntactical forms can be classified into Σ0n and Π0n based on the count and arrangement of the quantifiers involved (see Wikipedia). For example,thesetTot={e∈N:φe istotal}isΠ02becauseTot={e∈N:(∀x)(∃s)[φe,s(x)halts]}. If R is a computable 2-ary relation, the syntactical form “∀y1,∃y2,[R(y1,y2)]” is known as
Π02. More examples:
• ∀y1, R(x, y1) is Π01.
• ∀y1, ∃y2, ∀y3, R(x, y1, y2, y3) is Π03. • ∃y1, ∀y2, R(x, y1, y2) is Σ02.
• ∃y1, ∀y2, ∃y3R(x, y1, y2, y3) is Σ03.
And so on. Generally, for natural n > 0, Σ0n looks like ∃[Π0n−1] and Π0n looks like ∀[Σ0n−1].
A set might be described using syntactical forms of different kinds. For example, the set E = {x ∈ N: x is even} can be expressed as E = {x ∈ N: (∃y)[2y = x]}, which makes it look Σ01. At the same time, E = {x ∈ N: (∀y)[2y + 1 ̸= x]} which looks Π01. This example is not surprising because E is computable (c.e. and co-c.e. at the same time).
Remark 1: If the same kind of quantifier repeats, nothing changes. For example, the following is Σ02:
∃y1, ∃y2, ∃y3, ∀y4, ∀y5, R(x, y1, y2, y3, y4, y4)
if R is computable.
Remark 2: Σ0 and Π0 are the exact same thing, and both represent the class of decidable
Remark 3: Σ0n ∪ Π0n ⊊ Σ0n+1 and Π0n ∪ Σ0n ⊊ Π0n+1.
Questions are on the next page.
浙大学霸代写 加微信 cstutorcs
CSC363 UTM Winter 2024 Assignment 2 Due Wednesday February 28
Q14. Generally, a bounded quantifier such as “∃y < 3” does not change the classification in the arithmetical hierarchy. We exhibit this phenomenon in this question.
Let R(x, y) be a computable binary relation on N, and S = {x : (∃y < 3)R(x, y)}.
(a) Show that S is Σ0. That is, construct a computable 1-ary relation φ such that S =
{x: φ(x)}.
(b) Show that S is Σ01. That is, construct a computable 2-ary relation φ such that S =
{x: ∃y,φ(x,y)}.
Q15. For a natural number e, let We denote the domain of φe (the eth partial computable function). Consider the set Cof = {e: N\We is finite}. Show that Cof is Σ03, i.e., construct a computable 4-ary relation R such that
Cof = {x: ∃y1,∀y2,∃y3,R(x,y1,y2,y3)}. Hint: IfN\We isfinite,then∃y1,∀y2 >y1,y2 ∈We. Why?
Programming Help