The Universe of Discourse

Proof by insufficient information

Content warning: rambly

Given the coordinates of the three vertices of a triangle, can we find the area? And the answer is yes. If by no other method, we can use the Pythagorean theorem to find the lengths of the edges, and then Heron's formula to compute the area from that.

Now, given the coordinates of the four vertices of a quadrilateral, can we find the area? And the answer is, no, there is no method to do that, because there is not enough information:

These three quadrilaterals have the same vertices, but different areas. Just knowing the vertices is not enough; you also need their order.

I suppose one could abstract this: Let !!f!! be the function that maps the set of vertices to the area of the quadrilateral. Can we calculate values of !!f!!? No, because there is no such !!f!!, it is not well-defined.

Put that way it seems less interesting. It's just another example of the principle that, just because you put together a plausible sounding description of some object, you cannot infer that such an object must exist. One of the all-time pop hits here is:

Let !!ε!! be the smallest [real / rational] number strictly greater than !!0!!…

which appears on Math SE quite frequently. Another one I remember is someone who asked about the volume of a polyhedron with exactly five faces, all triangles. This is an error of thinking on the ontological level, not the mathematical level, so when it comes up I try to demonstrate it with a nonmathematical counterexample, usually something like “the largest purple hat in my closet” or perhaps “the current Crown Prince of the Ottoman Empire”. The latter is less good because it relies on the other person to know obscure stuff about the Ottoman Empire, whatever that is.

This is also unfortunately also the error in Anselm's so-called “ontological proof of God”. A philosophically-minded friend of mine once remarked that being known for the discovery of the ontological proof of God is like being known for the discovery that you can wipe your ass with your hand.

Anyway, I'm digressing. The interesting part of the quadrilateral thing, to me, is not so much that !!f!! doesn't exist, but the specific reasoning that demonstrates that it can't exist. I think there are more examples of this proof strategy, where we prove nonexistence by showing there is not enough information for the thing to exist, but I haven't thought about it enough to come up with one.

There is a proof, the so-called “information-theoretic proof”, that a comparison sorting algorithm takes !!O(n\log n)!! time, based on comparing the amount of information gathered from the comparisons (one bit each) with that required to distinguish all !!n! !! possible permutations (!!\log_2 n! \ge n\log_2 n!! bits total). I'm not sure that's what I'm looking for here. But I'm also not sure it isn't, or why I feel it might be different.

Addendum

Carl Muckenhoupt suggests that logical independence proofs are of the same sort. He says, for example:

Is there a way to prove the parallel postulate from Euclid's other axioms? No, there is not enough information. Here are two geometric models that produce different results.

This is just the sort of thing I was looking for.

[Other articles in category /math] permanent link