I'm trying to find the error in a proof that yields a contradictory result, and I was wondering if the (rather silly and convoluted) function involved in the proof is "valid" in the mathematical sense. I've never experienced an "invalid" function, and I don't even know if such functions exist, so excuse me if this question is naïve or malformed.

To my understanding, any computation that halts, takes input and has output, and can be performed by a universal computer is a function. Is this true? If true, given the fact that the following procedure can be performed on a universal computer in finite time, the procedure can be used in any context where a function mapping from $\mathbb{Q}^{2}$ to $\mathbb{Q}$ is expected, correct? Here's the procedure:

  1. Take the rational two-tuple input and convert it into two base-ten simplified fractions stored internally as some kind of string (this can be done with various combinations of $floor$'s and $log$'s, which can both be implemented on a universal computer, right?).
  2. Replace every "3" in each component of each fraction string with a "33".
  3. Replace every "5" in each component of each fraction string with a "35".
  4. Combine both components of each fraction into a single string with the fraction bar replaced with a "5".
  5. Combine the two strings for the two fractions into one string, with a "." in between.
  6. Re-parse this base-ten representation of the number into an actual rational number.

As an example of this function's mapping form $\mathbb{Q}^{2}$ to $\mathbb{Q}$:

$f(1/3, 1/7) = 1533.157$, or $\frac{1533157}{1000}$.

I know that this is a very strange operation to perform, and that it seems highly notation-specific and biased towards our arbitrary human ideas, but isn't it still technically a "valid" function, in the same realm as all other functions, or does some operation or property of it make it unmathematical or flawed?

  • $\begingroup$ This kind of thing is indeed a function in the mathematical sense; although I think in this particular case, you might want to specify more carefully what happens with zero, and with negative numbers. One particularly important point that your treatment omitted is the need for consistency. That is, if you define a function as some kind of calculation procedure, it must give the same output every time, for the same input. So for example, a step like multiplying by the current day of the month would not be permitted. $\endgroup$ – user22805 Oct 1 '12 at 21:51
  • $\begingroup$ As part of the consistency mentioned by @DavidWallace, you have to specify that your fractions are simplified as far as possible as well, since otherwise your function would produce different output for $\frac{2}{6}$ and $\frak{1}{3}$, which it shouldn't. $\endgroup$ – Arthur Oct 1 '12 at 22:03

The function you describe is perfectly valid. One may be careful with isgns, however, or preferably view this only as a map $\mathbb Q_{>0}^2\to\mathbb Q_{>0}$.

Observe that you can use a similar method to map (pairs of) fractions injectively into $\mathbb N$. All you need is that the objects (here: pairs of rationals) have a standard reprsentation as a finite string over a finite alphabet (here: the ten digits, "/" and ",")

  • $\begingroup$ Thank you! I've since found the error in my contradictory proof - one of the definitions I started with was flawed. $\endgroup$ – exists-forall Oct 1 '12 at 22:07

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.