But first things first, let's remember what it means for two sets to have the same cardinal: it means that we're able to create a function that has a one-to-one correspondence between the elements of the first set, and the elements of the second set.
Also, before we even start, I'd like to explain what I'm going to do: it's called a proof by contradiction, though I like our french expression better which would translate by "reasoning to the absurd". The point is that we have something we want to prove is false, so we consider it true and we reason from there. The goal being to end up with a contradiction, something absurd. In which case one of two things happened: either we went wrong during our proof, or our original assumption was not true (thus false).
Also, before we even start, I'd like to explain what I'm going to do: it's called a proof by contradiction, though I like our french expression better which would translate by "reasoning to the absurd". The point is that we have something we want to prove is false, so we consider it true and we reason from there. The goal being to end up with a contradiction, something absurd. In which case one of two things happened: either we went wrong during our proof, or our original assumption was not true (thus false).
First, a tiny bit a of notation. The set of all positive integers is usually noted $\mathbb{N}$. The set containing all numbers (including decimals, and so on) between 2 numbers is noted between square brackets, like this: $[0,1]$. This would be the set containing any real number between 0 and 1, including 0 and 1, as well as every fraction between 0 and 1, as well as some numbers that aren't even possible to write as a fraction (and there's a metric shit-ton of those).
Anyway, what we're going to do is prove that the second set is bigger than the first. Sounds counter-intuitive ? That's half the fun ! Here we go.
Let
$$X = \mathbb{N}
\\
Y = [ 0, 1]
\\
f: X \rightarrow Y $$
That last notation means that f is a function that takes an element of X and associates it an element of Y. On top of that, let's ask for that function to be a bijection.
Now comes the hard part. We're going to prove that even though the function is supposed to be a bijection, so among other things supposed to reach every number between 0 and 1, we can actually find a number between 0 and 1 that isn't reached by the function.
The argument we're going to use is both pretty cool and pretty weird at the same time, it's called Cantor's diagonal argument. We're going to look at all the numbers between 0 and 1 that are reached by our function, and create a new one from that.
The first thing to consider, is that every number can be written with an infinite decimals. It's actually pretty stupid: if you consider 0,5, nothing's stopping you from writing it "0,500000000...". What we're going to do is this: for each integer, we'll look at the number it's associated to, and look at the number of the decimal part at the position equal to the integer we're considering. Read that sentence several times, realise it's still not super-clear, and let me give you an example.
Let's say that 1 is associated to 0,723; then we'll look at the first number of the decimal part, which is 7. If 5 is associated to 0,2 3 6 4 2 3 7 3; we'll consider the 5th number, which is 2. Clearer ? If not, don't worry, an other example is coming.
And now, on to building our new number. We'll build it bit by bit: first we're going to look at the number associated to 1, and look at the 1st number of his decimal writing. If it's a 1, the number we're building will get a 2, and if it's not a 1, we'll write a 1. Then we'll do that for 2, but by looking the 2nd number of the decimal part, and so on... Like this:
$$\begin{align}
&1 \rightarrow 0,\; \textbf{7}\; 2\; 3\dots \\
&2 \rightarrow 0,\; 3\;\textbf{2}\;1\;5\;6\;2 \dots \\
&3 \rightarrow 0,\;5\;4\;\textbf{1}\;5\;1\;6\;5 \dots \\
&4 \rightarrow 0,\;9\;8\;4\;\textbf{6}\;5\;1\;8 \dots \\
&5 \rightarrow 0,\;8\;9\;0\;0\;\textbf{1}\;0\;0 \dots \\
&\dots
\end{align}$$
In this example, the number we're building would be 0,11212... And we can see the diagonal too (which explains the name). Each time a number in bold is different than 1 we put a 1 in the decimal writing, and when it's 1, we put a 2. Still following ? Good ! You've made it through the hard part !
Because now the whole argument has been laid out, and if you think about it, REALLY think about it, you'll realise that absolutely no integer can reach the number we've built. I'll try and make it even clearer:
Let's assume a certain integer, let's call him n, reached our mystery number, let's call him x. We would then have:
$ n \rightarrow x = 0,\dots \underbrace{1}_\text{n-th position}\dots$
In which case our mystery number should have, by construction, a 2 in this place. So this can't be true.
OR we would have:
$ n \rightarrow x = 0,\dots \underbrace{not \; one}_\text{n-th position}\dots$
In which case our mystery number should have, by construction, a 1 in this place. So this can't be true either.
It instantly follows that our mystery number is indeed not reached by an integer, so the function isn't a one-to-one correspondence, and we've actually found a set with a bigger infinity ! Yay us !
And yes, it does mean that there are more numbers between 0 and 1 than there are integers.
This is actually a pretty elaborate proof, so again, don't panic if you don't get it on first read, and maybe try to build a few examples, try to replace n by a small number and test it out, and you should be able to see why it works.
I remember I promised to prove that there actually was an infinity of infinities, but this post is already quite long, so it'll have to wait for next time. But if you're definitely lost after this post, don't worry, none of this will be useful for the next and final one.
$$X = \mathbb{N}
\\
Y = [ 0, 1]
\\
f: X \rightarrow Y $$
That last notation means that f is a function that takes an element of X and associates it an element of Y. On top of that, let's ask for that function to be a bijection.
Now comes the hard part. We're going to prove that even though the function is supposed to be a bijection, so among other things supposed to reach every number between 0 and 1, we can actually find a number between 0 and 1 that isn't reached by the function.
The argument we're going to use is both pretty cool and pretty weird at the same time, it's called Cantor's diagonal argument. We're going to look at all the numbers between 0 and 1 that are reached by our function, and create a new one from that.
The first thing to consider, is that every number can be written with an infinite decimals. It's actually pretty stupid: if you consider 0,5, nothing's stopping you from writing it "0,500000000...". What we're going to do is this: for each integer, we'll look at the number it's associated to, and look at the number of the decimal part at the position equal to the integer we're considering. Read that sentence several times, realise it's still not super-clear, and let me give you an example.
Let's say that 1 is associated to 0,723; then we'll look at the first number of the decimal part, which is 7. If 5 is associated to 0,2 3 6 4 2 3 7 3; we'll consider the 5th number, which is 2. Clearer ? If not, don't worry, an other example is coming.
And now, on to building our new number. We'll build it bit by bit: first we're going to look at the number associated to 1, and look at the 1st number of his decimal writing. If it's a 1, the number we're building will get a 2, and if it's not a 1, we'll write a 1. Then we'll do that for 2, but by looking the 2nd number of the decimal part, and so on... Like this:
$$\begin{align}
&1 \rightarrow 0,\; \textbf{7}\; 2\; 3\dots \\
&2 \rightarrow 0,\; 3\;\textbf{2}\;1\;5\;6\;2 \dots \\
&3 \rightarrow 0,\;5\;4\;\textbf{1}\;5\;1\;6\;5 \dots \\
&4 \rightarrow 0,\;9\;8\;4\;\textbf{6}\;5\;1\;8 \dots \\
&5 \rightarrow 0,\;8\;9\;0\;0\;\textbf{1}\;0\;0 \dots \\
&\dots
\end{align}$$
In this example, the number we're building would be 0,11212... And we can see the diagonal too (which explains the name). Each time a number in bold is different than 1 we put a 1 in the decimal writing, and when it's 1, we put a 2. Still following ? Good ! You've made it through the hard part !
Because now the whole argument has been laid out, and if you think about it, REALLY think about it, you'll realise that absolutely no integer can reach the number we've built. I'll try and make it even clearer:
Let's assume a certain integer, let's call him n, reached our mystery number, let's call him x. We would then have:
$ n \rightarrow x = 0,\dots \underbrace{1}_\text{n-th position}\dots$
In which case our mystery number should have, by construction, a 2 in this place. So this can't be true.
OR we would have:
$ n \rightarrow x = 0,\dots \underbrace{not \; one}_\text{n-th position}\dots$
In which case our mystery number should have, by construction, a 1 in this place. So this can't be true either.
It instantly follows that our mystery number is indeed not reached by an integer, so the function isn't a one-to-one correspondence, and we've actually found a set with a bigger infinity ! Yay us !
And yes, it does mean that there are more numbers between 0 and 1 than there are integers.
This is actually a pretty elaborate proof, so again, don't panic if you don't get it on first read, and maybe try to build a few examples, try to replace n by a small number and test it out, and you should be able to see why it works.
I remember I promised to prove that there actually was an infinity of infinities, but this post is already quite long, so it'll have to wait for next time. But if you're definitely lost after this post, don't worry, none of this will be useful for the next and final one.
No comments:
Post a Comment