Proving Something Exists

Combinatorics · Axiom Academy

INTRO Proving Something Exists Discover how to prove things exist without actually finding them. Imagine you have some pigeonholes and some pigeons. What happens when you have more pigeons than holes? New York City has about 8 million people. The average human head has between 0 and 150,000 hairs. Try to spot the pattern! Let's explore with a smaller example. Here are 10 people with random hair counts between 0 and 7 hairs. There are two fundamentally different ways to prove something exists. Shows something exists by explicitly constructing it . Shows something exists by logical reasoning , without finding it. Proving something exists doesn't mean you have to find it. You just need to show that it's logically impossible for it not to exist. If you distribute n+1 objects into n boxes, at least one box must contain more than one object. This simple idea has profound consequences across mathematics and computer science. Use non-constructive existence proofs when you need to prove something exists but constructing an example would be difficult, impractical, or impossible.

This is the written version of the interactive lesson above. See the full Combinatorics course.