Undefined Behavior: Not Just for Programming Languages

This is an oldie but goodie. Start with this premise:
a = b
Multiply both sides by a:
a2 = ab
Subtract b2 from both sides:
a2 – b2 = ab – b2
Factor the left side:
(a + b)(a – b) = ab – b2
Factor the right side:
(a + b)(a – b) = b(a – b)
Divide both sides by (a – b) and cancel:
a + b = b
Substitute b for a:
b + b = b
Finally, let b = 1 and simplify:
2 = 1

I ran into this derivation when I was nine or ten years old and it made me deeply uneasy. The explanation, that you’re not allowed to divide by (a – b) because this term is equal to zero, seemed to raise more questions than it answered. How are we supposed to keep track of which terms are equal to zero? What if something is equal to zero but we don’t know it yet? What other little traps are lying out there, waiting to invalidate a derivation? This was one of many times where I noticed that in school they seemed willing to teach the easy version, and that the real world was never so nice, even in a subject like math where — you would think — everything is clean and precise.

Anyway, the point is that undefined behavior has been confusing people for well over a thousand years — we shouldn’t feel too bad that we haven’t gotten it right in programming languages yet.

10 Replies to “Undefined Behavior: Not Just for Programming Languages”

  1. In “(a + b)(a – b) = b(a – b)”, where does the leftmost “a” go? Should it not be “(a + b)(a – b) = ab(a – b)”?

  2. I guess my issue is that the equality is wrong before you divide both sides by (a-b). You can’t factor out a zero either. Maybe I’m just stupid. I have not drank coffee yet today.

  3. there is no undefined behaviour in mathematics, as dividing both sides of an equation is no mathematical transformation, you have a theorem that for all x,y,z real numbers where z!=0 if zx=zy then x=y, the only thing you can do is evaluate the bounded variables and apply modus ponens to acquire a “new” formula, if you don’t have z!=0 you simply CAN’T get the formula, this is the difference between math and a programming language (or other system) specification which generates a state subspace in a bigger state space. when this state subspace isn’t closed that’s when undefined behaviour occures, whereas the space of proveable formulas is exactly the formulas which are proveable with the given deductive apparatus, so no escape there

    for a more comprehensive view take a look at “A Concise Introduction to Mathematical Logic” or the Coq or Isabelle proof assistants

  4. If it is not known that the divisor is nonzero, this has to be added as a premise. The final “theorem” is not a = b -> 1 = 2 but a = b & a-b != 0 -> 1 = 2, which is trivially true.

  5. Another one on the same vein:

    What is 1 – 1 + 1 – 1 … ?

    Let 1 – 1 + 1 – 1 … = C

    Then C = 1 – (1 – 1 + 1 – 1 …) => C = 1 – C => C = 1/2.

    But you can prove C = 1/4 etc. using the same “technique”. 🙂

  6. Actually, it’s the other way around: you’re allowed to do the divide only if you can prove it is not by zero. So it’s not about remembering what could be zero, it’s about proving what can’t be. Entirely different point of view.

    One problem with CS is that it’s horribly hard to prove anything substantial.

Comments are closed.