4 ms·
My answer would be that there are existence proofs for things that we cannot produce examples of. (There are actually many such proofs, but at some point I sto
by btilly 13y ago
My answer would be that there are existence proofs for things that we cannot produce examples of. (There are actually many such proofs, but at some point I stopped being shocked.) And furthermore there exist existence proofs for classes of things, at least some of the examples of which we can NEVER verify without adding new axioms to our axiom system!
Let me give a concrete example. A minor of a graph is any graph that you can get from the first by deleting points, deleting edges, or contracting points and joining edges. See https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem https://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theo... for a theorem which says that any family of graphs that is closed under taking minors (ie if G is in the family, then every minor of G is as well) can be characterized by a finite set of forbidden minors. Any graph without a minor in the forbidden set, is in the family.
The best known example of such a family is planar graphs. Those are graphs that you can draw in the plane without crossings. The forbidden minors are K_5 (5 points, all connected to each other) and K_3_3 (2 groups of 3 points, every point in each group connects to the every point in the other). Any graph without either of those as minors, is planar.
So, given any family of graphs that is closed under taking minors, we must have a concrete set of forbidden minors. Furthermore it turns out that given a finite set of forbidden minors, we can use them create a polynomial-time algorithm for recognizing whether a given graph is in the family.
Here is where it gets strange.
Given a family of graphs, we do not have a procedure to produce the forbidden minors. Such a procedure would be wonderful - it would let us do interesting things like solve the Halting problem! That is, of course, an impossible thing to do. This proves that there is, in fact, no such procedure. So we have proved existence of finite, concrete lists, yet proved that in general it is impossible to construct said lists.
It gets worse. There are many interesting families of graphs which are closed under minors, many of which we do not have any decision procedure for at all! (For example graphs embeddable in 3-dimensions without anywhere embedding a knot.)
So we've proven the existence of finite answers to concrete mathematical problems. Yet cannot produce those answers. In general we can NEVER produce those answers. Yet we know that they exist.
Now for the philosophy question: in what sense do those unfindable, unverifiable answers actually exist?
- acchow 13y ago> Now for the philosophy question: in what sense do those unfindable, unverifiable answers actually exist? I don't really see anything philosophically interesting here. Such a feeling probably arises from a misinterpretation of the halting problem here: > it would let us do interesting things like solve the Halting problem! That is, of course, an impossible thing to do. This proves that there is, in fact, no such procedure. No such procedure to do it generally.
- btilly 13y agoIf you're familiar with the history of constructivism and the corresponding foundational debates (never truly resolved) of the early 20th century, then it is clear what I am referring to. If you're not familiar with that, Constance Reid's Hilbert! contains a surprisingly readable history of this debate for non-mathematicians, disguised as a biography. For another accessible popular reference, The Mathematical Experience walks through this in a variety of levels of detail (you get out of it what you have the background to get out of it, but it is enjoyable anyways).
- tel 13y agoThis is closely related to proof by the probabilistic method, which shows up quite often in pattern recognition literature and combinatorics (Erdös was fond of it). This method says that instead of even proving the exact existence of something (despite missing any examples) you simply prove that the probability of its existence is positive (and thus cannot be zero). At some level these are just proofs that lower-bound the size of the set of instances, and it may be possible to convert any such argument in to one that is more directly measuring the count of instances. In practice however they tend to go through using bounds which are derived from measurable to arguments on random variables, so the conversion is less obvious to me. I wish my copy of DGL wasn't 2 hours away or I'd dig up one. (Edit: Wikipedia to the rescue! The "second example" on this page goes through using Markov's Bound on distributions http://en.wikipedia.org/wiki/Probabilistic_method http://en.wikipedia.org/wiki/Probabilistic_method)
- sanderjd 13y ago