Discussion between Maryam Ghizhi and Jing Zhang

7:56 PM

A: Range or Domain of Primitive Recursive Function?

WLOG we might assume $A$ is not finite and $0\in A$. We take the definition of r.e. sets to be a set is r.e. if its characteristic function is partial recursive. Then A set is r.e. iff A is a domain of a strictly increasing partial recursive function. Proof: (only if) $A=\Phi_e$, define...

Maryam Ghizhi

I want to approve, but please clarify your answer with specific part. for example (1) is true, because .... (2) is true because...

Jing Zhang

I've edited. There are parts in your question which are not clear, like (4)

Maryam Ghizhi

I edited and remove typo in (4), please complete it about (4) to set bounty and approve.

Jing Zhang

Multiply everything by 2 produces a function whose range is a subset of even numbers

Maryam Ghizhi

Please correct your answer to approve and set bounty, thanks.

Jing Zhang

7:56 PM

What is k in (4)?

Maryam Ghizhi

I think k is a constant, I'm sure there is no meaning for Halting set, am I right

Jing Zhang

There is no meaning if k is a constant either, as in this case the set is either singleton or empty.

Maryam Ghizhi

Which one can be suppose for k to this statement be true?

Jing Zhang

I have no idea. It's not true at t

At all that A must be a subset of even numbers. Or even the projection of A onto even numbers being r.e says nothing about A

Maryam Ghizhi

we know A is r.e in the question.

Jing Zhang

7:56 PM

Then it would be equivalent to (1) (2) in the vacuous way.

Maryam Ghizhi

$k \in \mathbb{N} $ ?

yeah, I'm sure it means some x from A that is even, now it's r.e?

Jing Zhang

Well it still does not make sense to me. The assertion that some x from A is even is r.e provided that A is r.e. But even when A is r.e this is not necessarily true. Like A=the set of odd numbers.

I'll suggest you look into the problems/definitions more carefully.

Maryam Ghizhi

@JingZhang would you please continue here?

thanks.

okey I say if A be an arbitrary r.e

Jing Zhang

Hi I think I've made it pretty clear

Maryam Ghizhi

we choose x that equals to 2k

it means choose x that is even.

so even number is an r.e set