When showing that a relation is not a function, is there an efficient method for finding particular preimages that are mapped to more than one image, rather than attempting to find particular preimages through guesswork or quasi-exhaustion? For instance, say we have tried 100,000 preimages that seem to map uniquely to various images by some relation, but then it turns out that on our 200,101th preimage, we have shown that the relation is not a function. Is there a general method that would enable us to show that the relation is not a function through a sequence of arguments, rather than computationally searching for such a conclusion?

Please don't say that it depends on the relation. I understand that the method of showing that a relation is not a function can be easily done in, for example, the instance where $f:\mathbb{Z} \rightarrow \mathbb{Z}$ by $f(x)=\frac{1}{x-1}$ where it is clear that $x\neq 1$ and, therefore, $f$ is not a function.

Perhaps this sort of relation may help show my point. Suppose that we have a relation $f:\mathbb{Q^*} \rightarrow \mathbb{Q}$ by $f(\frac{a}{b}) = \frac{\max{(a,b)}}{\min{(a,b)}}$.

Iterating through some particular preimages, it appears that f is a function. But is there a way in showing that there, in fact, a preimage that is mapped to more than one preimage?

  • $\begingroup$ In general, you would need to know specifics about this relation to do anything beyond simple exhaustion $\endgroup$ – Zach Effman May 2 '15 at 17:43
  • $\begingroup$ Quite so. I thus edited my post and included a particular relation at the end that appears to be a function, but is there a way to show that there is actually a preimage that is mapped to more than one image? – $\endgroup$ – Jeremiah Dunivin May 2 '15 at 18:00
  • $\begingroup$ I don't understand--you first give a perfectly nice function and then claim it is not a function. Then, you give an example of a (not well-defined) function instead of a relation. $\endgroup$ – Zach Effman May 2 '15 at 21:28
  • $\begingroup$ I'm confused as to what exactly your question is $\endgroup$ – Zach Effman May 2 '15 at 21:29

Your Answer

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

Browse other questions tagged or ask your own question.