How are some infinities bigger than others?

214 views

[ad_1]

I was watching Veritasium’s video about math having a fatal flaw. He explained that if we make a set of all the numbers in between 0 and 1, then added one to the first digit of the first number and added one to the second digit of the second number etc, we would always have a new number. He said this proved that there were more numbers in between 0 and 1 than natural numbers.

I was confused as to why you can’t do this with natural numbers, and how that proved one infinity was smaller than another.

In: Mathematics
[ad_2]

[removed]

>I was confused as to why you can’t do this with natural numbers,

If you take a natural number, and change one of its digits after the decimal place, you don’t get another natural number. If you start with, say, 3, and change the ten thousandths place, you get 3.0001, which isn’t a natural number— so it’s not a problem that it’s not found on your list of all the natural numbers.

[deleted]

The thing about math is, in some ways, it’s like a game. The rules are whatever we say they are. Math is a human invention so all of its rules and definitions are whatever humans have come up with.

So we have decided that, in math, we can have things called sets. Sets are just like collections of things. And sets can have sizes, which we define by the number of things in that set.

But what about the size of sets that have an endless amount of things? Like the set of all natural numbers? Or the set of all real numbers?

Well, in this case we have decided that to sets with an endless amount of things are the same size if you can create a rule that maps every single object in each of the sets on a 1-to-1 basis without missing any in either set.

For example, take the natural numbers {0, 1, 2, 3….}

Then take the even numbers {0, 2, 4, 6…}

Clearly there are “more” natural numbers than even numbers, right? Because the natural numbers *include* the even numbers, plus more!

Wrong.

Given our rule, they are the same size because we can map them 1-to-1. Take any natural number, multiply it by 2 and you get a unique even number. Taken any even number, divide it by 2 and you get a unique natural number. 1-to-1 mapping. They are the **same size.**

So we began to wonder if all sets with an endless amount of objects were the same size.

Back in the day, a dude named Cantor came up with a rather elegant argument that showed that the set of real numbers is actually bigger than the set of natural numbers. He created a proof that showed that, no matter what rule you created to map the natural numbers to the real numbers, that there would exist real numbers not accounted for in that mapping. That there would always be and endless amount of real numbers left over.

For that reason, we consider the set of real numbers as being “larger” than the set of natural numbers.

Notice that, at no point have I used the word infinity. Unfortunately, “endless” *means* “infinite” and both of those sets we were talking about (natural and real numbers) are endless, so they are both infinite, yet according to our rules of math, the latter is larger than the former. Hence, “some infinities are bigger than others.”

> He explained that if we make a set of all the numbers in between 0 and 1

Not just a set, a list. It has to be well-ordered for the proof to work. There has to be a first number and a second number and so on. They can’t all be in a disorganized heap.

Remember, the point of the proof is to show that such a list is *impossible.* The argument is, no matter what list you present, his method will find a Real number 0 < x < 1 that isn’t on the list.

>… Why you can’t do this with natural numbers

Well, in order to do the trick, you need an ordered list first. You need something that clearly comes after another thing, so that you can assing an ‘ID’ to a natural number the same way Vertitasium uses a natural number as an ID for the real ones.

But the thing is, what else is there but natural numbers? Nothing else is ‘naturally ordered’. You could use the alphabet, but there is no reason why it should be ordered the way it is in the first place. A being first is arbitrary.

But 1 coming before 2 isn’t, and it’s the only thing we can all agree on. It’s also the reason why it’s called a countable infinity.

First, we need to agree on what a list is. A list is just a way to assign a real number to each integer. There are a lot of possible lists, so just to make things clear, here is a possible list with an obvious rule of construction :

* 1) 0.1
* 2) 0.11
* 3) 0.111
* 4) 0.1111
* 5) 0.11111
* …
And so on

This is a particular list of real numbers between 0 and 1. It contains infinitely many items (one for each integer) but it certainly does not contain all the real numbers between 0 and 1. For exemple, it does not contain 0.2

Given any list of real numbers, there is a procedure (known as diagonalisation) that will return a real number that is not on that specific list. To illustrate the procedure, let’s just take an example with a beginning of a list

* 1) 0.**1**45869735…
* 2) 0.2**3**3813848…
* 3) 0.12**1**565351…
* 4) 0.835**8**35833…
* 5) 0.1535**7**3831…
* …

Take the digits in bold (**1** **3** **1** **8** **7** …) , add 1 to each digit (2 4 2 9 8 …) , and create a new number by concatenating these new digits after a “0.” . This gives will give a number starting with : 0.24298…
(Note that this procedure always gives a number which is a real number between 0 and 1)
This new number cannot be anywhere on the list. Indeed, for any integer n, the n-th digit of that new number is different from the n-th digit of the n-th number on that list.

Now, one can answer the following question : “Can we make a list of real numbers that contains all real numbers between 0 and 1 ?” The answer is NO. Because whatever the list is, there is always at least one real number that is not on that list, which is the one created by the procedure.

This happens because there are far too many real numbers. Which means that even if you try to make an infinite list of real numbers, you will always miss some of them. So we translate that by saying that the infinity of real numbers is larger than the infinity of integers.

You can not do the same procedure with a list of integers, because the object created by the procedure of concatenating digits is not an integer.

reading your post I may be mistaken but I think you may have misunderstood something.

we make a set of all the numbers in between 0 and 1, then added one to
the first digit of the first number and added one to the second digit of
the second number etc, we would always have a new number. ”

what makes me think you may have misunderstood is where you say “new number”

if my understanding is correct the number itself is not “new” it may be clearer to say it is “unpaired”

the proof is a proof by contradiction and “proves” that one “infinity” is larger than others by

1. first assuming you can pair up (a bijection) the set of natural numbers and real numbers the set of both is infinite and it is assumed that it could be done.

2. it is proven that our assumption leads to a contradiction this is done by “finding” (proving there exists) a “unpaired” number after all the numbers were paired up (this was assumed)

3. the proof that the there is a unpaired number works works by applying a process to the infinite list where a number is shown to be different from every number on the list. this is done by adding some value to the infinite representation of a real number for every real number Importantly the number “created” exists and is a real number it would exist in a set of real numbers but it can’t exist on the set of paired numbers between natural and real numbers.

4. because we assumed we could pair up the all numbers of each and proved there was a unpaired number this implies that our assumption was wrong.

further because there is a unpaired real number and presumably all the natural numbers were paired then their are “more” real numbers ie its a larger set but both sets were infinite.

>I was confused as to why you can’t do this with natural numbers

Because then they’re not natural numbers. Natural numbers *must* be integers. Let’s try “adding one to the first digit of the first number and one to the second digit of the second number etc”:

* 1 is a natural number.
* 2.1 is not
* 3.01 is not

The Natural Numbers are 0, 1, 2, 3… But there are infinite numbers between 0 and 1. And another infinite numbers between 1 and 2, and another between 2 and 3…

The smaller infinities are called “**countable**” and the bigger ones “**uncountable**”. Here’s why:

1. Count the natural numbers: OK. 0,1,2,3,4…. It would take forever to count them all. But *if you had forever, you could do it*!
2. Now, count the numbers between 0 and 1, decimal numbers allowed: Alright. 0 ….um, *what’s the next number*? Is it 0.1? No, can’t be, then you’d have missed 0.01. Is it 0.01? No then you’d have missed 0.001…

**If you try and count the numbers between 0 and 1, you can’t even get to the first number past 0 in the list**, because no matter what number you say next, you’ll have missed an *infinite* number of numbers before that one! When trying to list the numbers between 0 and 1, there’s infinities *inside* infinities. An infinite number of numbers between each of an infinite number of numbers. It’s **uncountable**.

Listing the natural numbers doesn’t have this paradoxical-explosion-of-infinities problem. There’s just a “regular” list of numbers. It’s infinitely long, but each step is well defined and not growing within itself.

>I was confused as to why you can’t do this with natural numbers, and how that proved one infinity was smaller than another.

Every natural number has a finite number of digits. Every irrational number has an infinite number of digits. If you tried this with natural numbers you’d quickly run out of digits to change.

Firstly, here is a key term: bijection.

A bijection is a pairing up of the elements of two sets such that every element of the first set is paired up with a single element of the second set, and there are no unpaired elements in the second set.

For example, if we have two sets {1, 2, 3} and {a, b, c}, we can create a bijection by pairing them up like this: 1→a, 2→b, 3→c. Since we can create a bijection between those two sets, that tells us that the two sets are the same size.

Similarly, if we can’t create a bijection between two sets, they must be different sizes. For example {4, 5} and {d, e, f}. No matter how we pair things up, we cannot create a bijection between those two sets. 4→d, 5→e pairs up every element of the first set, but ‘f’ gets left unpaired. 4→d, 4→e, 5→f makes sure there are no unpaired elements in the second set, but 4 got paired up twice, and it can only be paired up once to count as a bijection.

You might be wondering why mathematicians use bijections to compare the sizes of sets. Why don’t they just *count* the number of elements?

But, think about what you do when you count things. You look at one object and say “one”, then the next and say “two”, and so on until you’ve looked at each object and said a number. What you’ve just done is created a bijection between the group of objects and a subset of the natural numbers. If we go back to the example of {1, 2, 3} and {a, b, c}, if someone asked you to count the number of elements in that second set, then the pairing 1→a, 2→b, 3→c is probably exactly what you would do.

Now, to bring things back to your original question: as I said, if you can show that a bijection can’t be formed between two sets, then we must conclude that the two sets are different sizes. And that’s exactly what Cantor’s goal was with his diagonalization argument. The way the argument works is that it shows that for any pairing between the natural numbers and the interval (0, 1), there’s always going to be a number in the interval that gets left out, and isn’t paired with a natural number, similar to our example above with 4→d, 5→e leaving out ‘f’.

Why doesn’t this work with the natural numbers themselves? Well, let’s try it out. Firstly, we’re going to have to write the naturals with infinite zeros after the decimal place (as in 1.000…, 2.000…, etc.) so that we can talk about arbitrary digits (if we didn’t do this then we would have a problem if we had to talk about the 17th digit of the number 8 or something). Then, if we go down the list, creating a new number by adding 1 to nth digit of the nth number, what we’re going to end up with is a number that ends in an infinite string of ones after the decimal place.

Now, the thing about this number that we’ve created is that it’s not a natural number (it would be a rational number), which means it’s not supposed to be on list in the first place! It’s not a problem for the same reason that 1→a, 2→b, 3→c leaving out ‘f’ isn’t a problem. {a, b, c,} doesn’t include ‘f’, so a bijection shouldn’t (and can’t) include it. The set up I described above isn’t the only way to try to diagonalize the naturals, but they all have the same problem, in that whatever number you create isn’t going to be a natural.

So to sum it all up, with the interval (0, 1), a diagonalization is guaranteed to create a number between 0 and 1, but with the naturals a diagonalization is going to create a non-natural number. That’s the difference between the two and that’s why the same argument doesn’t apply.

It happens because the amount of real numbers between 0 and 1 is infinite and it’s the same between 1 and 2. So what you get is this definition of real numbers, “The amount of real numbers is equal to the number of natural numbers times infinity.” So no matter how many natural numbers you have there will always be that number times infinity real numbers, even if there are an infinite number of natural numbers. Which there is. It’s all just based on definitions and word play.

The number of real numbers=Xinfinity, where X=the number of natural numbers.

The number of natural numbers=infinity.

So…

The number of real numbers=infinity times infinity.

Or infinity^2

When the number of natural numbers is only “infinity.”

I saw a guy on an old NOVA documentary put it something like this:

There are an infinite number of irrational numbers between zero and one. If you create a set of numbers that includes whole numbers going to infinity *and* the irrational numbers between each of the whole numbers, the irrational numbers, “get to infinity” way sooner, and that infinity is always many infinities larger than the infinity of whole numbers in the same set. One of the infinities seems to be a multiple of the other. One sub-set will always be infinitely larger than the other until they both somehow become infinite.

Same way an infinite one dimensional universe is just a dot to us. And an infinite two dimension is just a line stretching infinitely long, but wouldn’t take up all the space in our universe. And our infinite third dimension universe wouldn’t be able to completely fill up a forth dimension.

Infinity^0 is equivalent to 1. Not really big now is it

Infinity^2 is infinity*infinity.

Infinity^3 is comparable to the space our universe takes up

Time can also be considered a dimension, we experience time in one dimension, and time will never end so it is infinite. But we only experience it one moment at a time. Two dimensional time would be experiencing all that has happened and will happen at the same time, three dimensional time is all possible time lines from the starting point, or the creation of our universe. A zero dimensional time line would be like if you took a photo of the universe, a particular moment in time, and than nothing ever changes.

There are two ways to compare sizes of two sets A and B:

1. count how many elements are in A, count how many elements are in B, compare the result
2. Pair up the elements of A with the elements of B, see in which set you run out of elements first

While they seem similar, if you think about it you come to realize there is a principal difference between them: the first method assigns a “size” to A and then to B and then compares them. It does not only check if A and B have the same amount of elements, it also calculates what that amount is.

Both methods are fine (and equivalent) if A and B are finite, but when we try to extend them to the infinite we run into problem with the first method, namely, you would never finish counting the elements of A.

The second method does not require you to do so. Granted, if the sets are infinite then there are infinitely many pairs, but you are not required to present the pairing pair by pair, just to produce a rule.

We say that two sets are of the same size, denoted |A|=|B|, if there is a rule which matches every element of A with every element of B such that every element of B is paired exactly once. For example the set of natural numbers (1,2,3,…) can be paired with the set of even numbers (2,4,6,…) via the rule “x pairs with 2x”.

(To be more detailed: if there is a pairing such that every element of B is paired with at most 1 element of A [but not all of them must pair] we say that B is at least as large as A and denote |A| <= |B|. If there is a pairing with each element of B is paired with at least one element of A [but it could be more than 1] we say that A is at least as large as B denoted |A| >= |B|. It is not trivial at all to show that |A| >= |B| and |A| <= |B| implies |A|=|B| [or even, under my notations, that |A| <= |B| implies |B| >= |A|], but it does indeed hold. This result is called the Schröder–Bernstein theorem)

Now that we have a working definition of when one infinity is larger than other, one can try to argue that not all infinities are the same by showing there are two infinite sets A and B for which |A| <= |B| holds, but |A| >= |B| does not. The textbook example is to show that there are more natural numbers than real numbers. There are many videos of the proof you can look up, but the general idea is to:

1. note that it is easy to show that |Naturals| <= |Reals|: every natural number already is areal number, so matching x with x suffices.
2. Prove that if you try to do the opposite, that is, pair with each natural number a real number hoping that you’ve covered all real numbers, then there must be a number you have missed. This is done via a simple* argument called Cantor diagonalizations which has since become a staple of modern mathematics.

*by simple I don’t mean trivial. It is natural for people with no background to struggle with it. Don’t be disparaged if you don’t get it immediately, just keep revisiting it. It is a common saying that the main difference between mathematicians and non mathematicians is that mathematicians are so used to not understanding things they don’t get phased by it.

One infinite set can only be “larger” than another infinite set if we ignore the fact that you can’t measure any infinite set, because they are all infinitely large.