0
$\begingroup$

Hi I'm doing some exercices on reductions and one of them is like this:

enter image description here

My problem rather than doing the reduction is understanding it. For the positive case I want that if Mx(x) never stops then p's domain has to be strictly included in q's domain which has to be stricly included in p's range. Am I wrong? Therefore Dom(p) has to be stricly included in Range(p), right?

Let's forget about reductions for a moment, my problem here is: is there any function $f(x)$ whose domain is strictly included in its range?

We would want to have $Dom(f(x)) = \{1\}$ and $Range(f(x)) = \{1, 2\}$ That would mean that 1's image has to be 1 AND 2 :/

What am I doing wrong?

Thanks for your time and have a nice day! :D

$\endgroup$
1
$\begingroup$

Without getting to the technicality of codomain/range/image and surjective functions, the property you ask for can surely happen. For instance,

$$f(x) = 2x$$

defined over the domain interval $[0,1]$, has the image $[0,2]$. This should not happen over finite domains.

$\endgroup$
0
$\begingroup$

You are completely violating the rules for a function. For any element x in the domain there is only one image. This is the thing which differentiates a function from a relation. In a relation it is perfectly valid for an element to be related to b as well as c.

$\endgroup$
  • $\begingroup$ Yeah, that's what I'm trying to say, am I undersanting something wrong or is not possible to solve the problem, that is, having a function like the example I've given which is obviously wrong :/ $\endgroup$ – clvr_bottle Dec 29 '17 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.