- Thank you to Brilliant for sponsoring this episode.
Hi guys, Jade here.
Here's a super simple argument.
If I have five Australian pigeons and four pigeon holes
if I want to put each pigeon into a pigeon hole
(bright music)
there must be at least two pigeons in the same pigeon hole.
This is called the Pigeonhole Principle,
and more generally,
it states that if you have more items than containers,
if you want to put every item into a container
there must be at least one container
with more than one item in it.
So why is this even a thing?
It's practically counting
but we'll see that it's surprisingly powerful.
It can prove that in any big city
at least two people have the same number of hairs
on their head.
It reveals a fundamental limit of information compression
and it can help prove
that some infinities are bigger than others.
If someone came up to you and asked
do any two people in Sydney, Australia have the same number
of hairs on their head, what would you say?
How would you even begin to figure it out?
You might think you had to go around
to every Sydneysider and count all of their hairs
and then see if you found any two with the same number.
But thanks to the pigeonhole principle
we don't need to do that.
We only need to know two things.
The average number of hairs on a person's head
and the number of people living in Sydney.
I should mention to make this interesting,
we're going to leave out bald people
who have zero hairs on their head
because obviously old bald people have the same number
of hairs on their head.
Sorry, bald people.
So what's the average number of hairs on a human head?
According to Google, it's about 100,000.
We'll assume that no one in Sydney
has more than 1 million hairs on their head.
So we've got a range of 1 to 1 million hairs.
These will be our pigeon holes.
(bright music)
The population of Sydney, Australia is about 6 million.
They will be our pigeons.
Let's fill our 1 million pigeon holes
with 1 million Sydneysiders.
He has one hair, she has two hairs he has three hairs,
all the way up to a million hairs.
We still have 5 million Sydneysider left
who need to go into a pigeon hole.
According to the pigeonhole principle,
because the number of Sydneysider is larger
than the number of possible hairs on a human head,
there simply must be at least two Sydneysiders
with the same number of hairs on their head.
This is amazing.
Without having to know the actual number of hairs
or the two individuals with the same number of hairs
we've managed to prove that
in any city of more than 1 million people,
there must be at least two people
with the same number of pairs on their head.
That was a fun but useless result.
Can the pigeonhole principle be used for anything useful?
Yes, it reveals a fundamental limit of data compression.
Data compression is the technique used
in computer science to make large computer files
like images, audio, and video recordings into smaller files.
This makes them easier to store on your computer
or send over the internet.
Data compression works by manipulating the data
so that it uses fewer bits of information
than the original file.
A very common type of data compression
is lossless compression.
As the name suggests, no information is actually lost
during this compression and we can always get back
all of the original data from the compressed data.
How?
How can you reduce the number of bits
used to represent a file without losing any information?
It's pretty interesting.
Consider a screen of plain text on a white solid background.
There are many long runs of white pixels
and many short runs of black pixels.
A single line of pixels could be represented like this,
a W for every white pixel and a B for every black pixel,
a total of 67 characters.
Using a lossless compression algorithm,
we can represent the same information more efficiently.
Take this string of 12 Ws.
Rather than writing out each W individually,
we can write a 12 and then a W to signify
that there are 12 white pixels in a row.
Similarly, we write 1B to signify one black pixel.
Another 12 followed by a W
to signify another row of 12 white pixels,
3B for three black pixels and so on.
Here we've compressed the original 67 characters
down to just 18.
While the actual format used for the storage
of files is generally binary rather than ASCII characters
like this, the principle remains the same.
If we want to convert the compressed data back
to the original data
we can do so because no information is actually lost.
It's just transformed.
Lossless compression is really useful for things
like text files where the original file
needs to be replicated perfectly.
So here's a question for you.
Can you write a computer program
that losslessly compresses any set of data?
It sounds like a very big question.
How would you go about answering it?
Here's where my mind would go.
Information compression is based on exploiting redundancies.
Redundancies rely on there being some kind
of pattern in the information.
So as long as there's a pattern,
you should be able to compress the data.
So then the question becomes, does true randomness exist?
Maybe it's just that we are not clever enough
to spot the pattern.
A pattern's objectively real
or is everything merely information
and our minds need to simplify to make sense
of the universe.
But there's a much simpler way to answer this question
using the pigeonhole principle.
Imagine a company claims that their new program,
Shrivel Devil, can compress any file
to 80% of its original size
then decompress it back to its original file.
You've got a bunch of e-books that are 100 bit files.
So Shrivel Devil claims to be able to compress them all
into 80 bit files.
It doesn't sound so far fetched,
but here we invoke the pigeonhole principle.
First, let's ask how many 100 bit files
can we possibly have?
A simple calculation shows that we can have
two to the power of 100 of them.
To see how I got this number, let's start smaller.
How many two bit files are possible?
A bit can either be a one or a zero.
So we can have 00, 01, 10, and 11, four possible files
which can also be expressed
as two to the power of two files.
How many three bit files can we possibly have?
000, 001, 010, 011, 100, 101, 110, and 111.
Eight different files, which is also expressed
as two to the power of three.
How many four bit files?
16 or two to the power of four.
The pattern is pretty obvious:
for any number of n bits,
there are two to the power of n possible arrangements
of those bits.
And therefore, two to the power of n possible files.
So the number of possible files we have
with our 100 bit e-books is 2 to the power of 100
and the number of possible compressed files
of 80 bits is 2 to the power of 80.
Now for lossless compression to work,
each compressed data file needs to decompress back
to its original file.
This means that each original file needs to map
to exactly one compressed file
and each compressed file needs to map back
to exactly one original file.
If two original data files are compressed
into the same smaller file,
how will that one smaller file expand
into two different original data files?
It won't.
One will be lost.
So how are we going to compress
2 to the power of 100 original data files
into 2 to the power of 80 compressed data files
and then decompress 2 to the power of 80 files back
into 2 to the power of 100 files without losing any files?
The answer?
We can't.
More than one 100 bit file is going to be compressed
into the same 80 bit file, and therefore one of the files
will be lost during decompression.
For this compression program to work,
each 100 bit file would need to be compressed
into an individual 80 bit file
which the pigeonhole principle tells us is impossible.
As tempting as it sounds, you'll have to pass
on Shrivel Devil.
A program that losslessly compresses any file is impossible.
It violates the fundamental rules of mathematics.
I just think this proof is really clever
because it's so simple
and just not where my mind would've gone.
You might be starting to see the unexpected power
of the pigeonhole principle, but what would happen
if we extended it from a finite number of objects
to an infinite number of objects?
So far, we've used it like this.
If the number of pigeons is larger
than the number of pigeon holes,
we can't have a one-to-one mapping
between pigeons and holes.
Therefore, we will always end up
with at least one pigeonhole with two pigeons in it.
But what if we flip this on its head?
What if we use the fact
that if we can't have a one-to-one mapping
between pigeons and pigeonholes,
it means that the number of pigeons can't be equal
to the number of pigeonholes.
It doesn't sound like much of a difference
but by flipping the argument
we can prove some pretty crazy things about infinity.
First, we'll start by saying two sets
of objects are the same size.
That is, they have the same number of objects
or elements in them,
if you can create a one-to-one mapping between every element
in each set with no elements left over
but if we make a one-to-one pairing
and some Lego people are left over,
we know that we have more Lego people
than chemical elements.
In math talk, we say that the set of Lego People is larger
than the set of chemical elements.
This is pretty simple when it comes to finite sets,
but things start to get weird
when we extend this simple reasoning to infinite sets.
Take the set of natural numbers.
These are the positive integers from one to infinity.
There are infinitely many natural numbers
as we can count them forever and never stop.
Now, take all of the negative whole numbers
which are also infinite as they extend to negative infinity.
Are there the same number
of natural numbers as negative hole numbers?
Unsurprisingly, yes.
We can map every natural number
to a corresponding negative hole number.
According to our one-to-one mapping argument,
the infinity of the natural numbers
and the infinity of the negative hole numbers
are the same size.
What about the infinity of the natural numbers compared
with that of the square numbers?
Square numbers make up only a small part
of all of the natural numbers.
So you might think that the infinity
of the natural numbers is larger
than the infinity of the square numbers.
But let's try a one-to-one mapping idea.
We can see that for every natural number
there's a corresponding square number.
This is more surprising.
The infinity of the natural numbers
and the infinity of the square numbers
are actually the same size.
This is a pretty weird property of infinite sets,
a smaller part of a set, a subset, can be the same size
as the set itself.
In math talk, when two sets have the same size
we say that they have the same cardinalality.
The cardinalality of the natural numbers,
the negative whole numbers and the square numbers
is represented by this symbol and called aleph null.
So are their infinities bigger than aleph null?
Take the set of real numbers.
These include all the whole numbers,
rational numbers and irrational numbers,
numbers that cannot be expressed as a ratio.
They make up all of the numbers
on the continuous number line.
Are the infinity of the natural numbers
and the infinity of the real numbers the same size.
We can answer this the same way we answered
for the other sets of numbers
by seeing if we can can create a one-to-one mapping.
To keep things simple, we're going to limit the reals
to just those between zero and one for now.
So where do we start?
But wait, someone knocks on your door claiming
that they have already made a one-to-one mapping.
This person looks shifty and you don't know
if you can trust them, but can you prove them wrong?
They claim that they have mapped every real number
to a natural number.
So to prove them wrong, you need to come up
with a new real number that definitely isn't on their list.
Can you do it?
You take the first decimal of the first number and add one.
Now you take the second decimal
of the second number and add one.
Now you take the third decimal
of the third number and add one.
You keep doing this for every single number
on their list and you make a new number out of it.
Was this number on their original list?
Well, it's definitely not the first number
because the number in the first decimal place is different.
And it's definitely not the second number
as the number in the second decimal place is different.
You can make this argument for every number.
It's definitely not the 1000000th number
because the 1000000th decimal place will be different.
Even though there were an infinite amount
of real numbers on this list, you've managed to come up
with a number that wasn't on the list.
Therefore, the claim that there was a one-to-one mapping
between every natural number
and every real number must have been false.
But our person's not giving up.
They just add the new number to the list.
Problem solved, right?
No, you're onto them.
This time, you subtract one
from every subsequent decimal place.
This number also wasn't on the list.
In fact, you can create an infinite amount of numbers
that weren't on the original list.
No matter what they do,
there will always be some real numbers
that aren't on their list
and so they cannot create a one-to-one mapping
between the natural numbers and the real numbers.
What does this mean?
There must be more real numbers than natural numbers.
The infinity of the reals is bigger
than the infinity of the natural numbers.
This is a famous argument
called the diagonalization argument
by the genius Georg Cantor.
The cardinality of the real numbers is called aleph one
and here's a question for you to ponder.
Are there any infinities bigger than aleph one?
Let me know your thoughts in the comments.
We usually believe
that getting important insights into the nature
of the universe requires an expensive telescope,
the latest super computer
or cutting-edge laboratory equipment.
But the pigeonhole principle shows how far we can get
by just thinking about things.
This is one of the reasons I fell in love with mathematics.
Today, we just scratched the surface
of the marvels of the infinite.
There is so much more to discover.
With this brilliant course dedicated to infinity,
you'll learn what happens when you add infinities together,
discover strange shapes with infinite length
but finite area, and derive one of the deepest theorems
in all of mathematics.
Oh, and you'll find out
whether there are infinities bigger than aleph one.
I love Brilliant because of the interactivity.
Being a millennial, I struggle with attention
but the active problem solving helps keep me engaged.
In fact, I learned the diagonalization argument
from this course.
Brilliant has loads of other courses about math, physics
and computer science.
Brilliant are offering 20% off the annual premium membership
to the first 200 people who sign up
with the link in the description and pinned comment
or go to brilliant.org/UpAndAtom.
Sign up with the link and start discovering today.
See you in the next episode.
Bye.
(upbeat music)