back

My favorite theorems

A small list of some of my favorite theorems.

Theorem on Friends and Strangers:

In a group of 6 people, then there will always be three who are either mutual strangers or mutual acquaintances.

I first saw this theorem in its graph-theoretic form, but I like this formulation more because it's a nice example of how something that can seem very abstract can very quickly be applied for concrete settings. I also like this form because it is very simple to explain and understand, while still not being immediately obvious at all. This theorem was the first time I realized the power of graphs and the kinds of interesting problems that can be represented through graphs.

Fundamental Theorem of Arithmetic:

Every integer larger than 1 can be represented uniquely by a product of prime numbers.

I generally am not a fan of number theory, but I like this theorem a lot. I find that it is the best way to explain why prime numbers are so special. I love using this to create maps to and from the naturals, even when it's not really convenient.

Euclid's Theorem:

There is an infinite amount of prime numbers.

It's all in the simplicity for this one. It is a very elegant statement, it communicates a very simple idea, and has a very concise proof by contradiction. A great way to show how a mathematical proof works.

Cantor-Schröder-Bernstein Theorem:

If there exist injective functions f : A -> B and g : B -> A then there exists a bijective function h : A -> B.

This theorem is particularly relevant for the study of the cardinality of infinite sets. I like that it takes the incredible idea of different sizes of infinity and reduces it to the simple exercise of finding injective maps. I particularly like using this theorem together with the fundamental theorem of arithmetic when dealing with countable sets.

Cantor's Theorem:

For any set A, the cardinality of the set of all subsets of A is strictly larger than the cardinality of A. i.e: |A|<|P(A)|.

This theorem seems boring until you realize it also works for infinite sets. This is the theorem that implies the existence of different sizes of infinity. What really makes this one of my favorites is the diagonalization argument to prove the uncountability of the reals. It is such a creative and unusual technique.

Gershgorin's Circle Theorem:

Every eigenvalue of a square matrix A lies within at least one of the Gershgorin discs D(aii,Ri), where Ri is the sum of the absolute values of every non-diagonal element in the i-th row.

This is the kind of theorem that you first look at and think "thats really random, but not really interesting", but then you just can't stop thinking about it and eventually realize how wonderful it actually is.