quarta-feira, outubro 25, 2017

Cantorian Sets: "Beyond Infinity - An expedition to the outer limits of the mathematical universe" by Eugenia Cheng



“If this be not that you look for, I have no more to say, but bid Bianca farewell for ever and a day.”

In “The Taming of the Shrew” by William Shakespeare (quoted by Cheng in the book)


Eugenia Cheng starts by saying right at the beginning of the book, "Infinity is not a number," and I think it really helps to get that misconception out of the way at the start. As soon as we one gets past that hurdle the rest is just a piece of cake.
As pointed out numerous times by Cheng, Cantor is the accepted authority on this, but are there alternatives?

Cantor Infinities


Key Idea: You can put the even numbers in one-to-one correspondence with the whole numbers and say that this demonstrates they have the same cardinality.

1->2
2->4
3->6
...

This shows that the set of whole numbers is the same size as the set of even numbers.

This seems counter-intuitive - and it's usually a real challenge to anyone encountering it for the first time, but if you do accept this then all sorts of deep and interesting mathematics follow. The way I think about this is, it's not a natural property, it's not a statement about the world*; it's Cantor's definition of infinity, let's go along with it and see what happens.

Non-Cantor Infinities?


But what about the intuitive (naive, even) point that that in between the even numbers you have the odd numbers, therefore the set of even numbers is smaller than the set of whole numbers?

2, 4, 6, 8, 10, …
is obviously smaller than
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

Therefore, the set of whole numbers is obviously bigger than the set of even numbers.

There's a hidden assumption that if I add an element to a set then the set gets bigger. That seems like a reasonable assumption to me. Are there "non-Cantor infinities"? To understand current thinking on infinities one must understand Cantor, but maybe one should also consider alternatives.

What Cheng proposed is nothing new in the field of number theory dealing with Infinity: “The general question is: How should we compare the size of infinities? So far, we have decided that the real numbers are unaccountable, that is, that there is no possible way to match them up precisely with the natural numbers because some real numbers are doomed to be omitted. Intuitively this means that there must be ‘more’ real numbers than natural numbers, but what could this possibly mean if they’re both infinite? Some infinities are bigger than others – how is that possible, seeing as infinity is already infinitely big? Isn’t it the biggest thing that there is? How can anything be bigger that it? Just like questions of the soul, everlasting life, and whether or not I’m fat, this comes down to definitions.”
The way to dealt with infinities is the following: Start with a simpler question. How do you determine if two finite sets are equal in size? The basic process is to place the two sets in one to one correspondence.  This is key to answering the question about infinities. I know that I have the same number of fingers as toes because I can pair them up with none left over. I know that I have more ears than noses because when I attempt to pair them up I find I make one pair, say nose paired with left ear, and have one ear left over. Now this "one to one correspondence" sounds a bit of an odd process - after all why not simply count each set? The reason is because for infinite sets you cannot count them. But even for infinite sets you can still apply the very basic process of placing it in one to one correspondence.

And as Cheng so ably demonstrates, this can be done for some infinities such as the integers, the prime numbers, the rational numbers so they are equal in size, but fails for others like the integers and the reals. The mathematical proof is quite far more rigorous than that, but the key idea is that simple.

Take the Hilbert Hotel Paradox which Cheng uses throughout the book (bear with me; I’m going to rephrase Cheng here). You have an infinite amount of rooms in your hotel. An infinite amount of people turn up. You fit them one per room. Fine. Then a new person turns up demanding a solo room. How to fit them in? Easy. Move the person from room 1 into room 2, the one who was in 2 into 3, and so on. Infinite amount of people, infinite amount of rooms, all have a room, but now room 1 is free. Infinity + 1 = infinity. Then an infinite amount of new people turn up. They also demand solo rooms. How to fit them in? Easy. Move the person from room 1 into room 2. From room 2 into room 4. From room 3 into room 6. Now you have an infinite amount of odd numbered rooms free. Infinity x 2 = infinity.

So far so good.

But imagine trying to count up all the possible fractions. Someone gives you an infinite list of numbers where the decimal points go off to infinity. You start numbering them; the first one is no. 1, the second is no. 2, and so on. And you do it. You number them all, 1 to infinity.

Then that someone plays a trick. The first set of decimals are like this:

0.11111...
0.2222...
0.3333...
0.4444...
0.6745969...

What they do is change one number in the decimal expansion. They change the first digit of no. 1, the second digit of no. 2, the third digit of no. 3. And so on to infinity. You've now got a number that starts 0.23451..., which is different in at least one digit to every single one that you've numbered to infinity.

You can't add it to the list. Your list of fractions is therefore bigger than your infinity.

This is therefore a second, bigger, infinity than the one of all counting numbers. The infinity of counting numbers is called aleph-null; that of all fractions as well (real numbers) is called R. And you can take this further into ever more mind-boggling and inexplicable higher levels of infinity. If you can prove there are any infinities in between these two, or even that there are no infinities between these two, you would get lots of buns from the mathematical community.

What about the primes which Cheng barely mentions? First, the number of primes is the same as the number of normal (natural) numbers (which is also the same as the number of perfect squares). This is because they can be put into a one-to-one correspondence like this:

1.............. 1st prime number.............. 1 squared (1)
2.............. 2nd prime number............ 2 squared (4)
3.............. 3rd prime number............. 3 squared (9)
4.............. 4th prime number............. 4 squared (16)
...
1000........ 1000th prime number....... 1000 squared (1,000,000)
...
Billion....... Billionth prime number.... 1 billion squared
...

So - and this is counter-intuitive - there are not "more natural numbers" than there are primes or perfect squares because for any natural number, you can match it to a prime or perfect square. This is a peculiar property of infinite series like this - that you can put them on a one-to-one correspondence with a subset [It's also possible to order the rational numbers (fractions) like this. So, the number of factions - 1/2, 3/4, 7/8, etc. - is the same as the number of natural numbers. Again, counter-intuitive.]

However, there are still different sizes of infinity. In fact, there are an infinite number of sizes of infinity. These are called Aleph-Null, Aleph-One, Aleph-Two, etc, (and there are also sizes of infinity that fall outside this series). There are Aleph-Null natural numbers, Aleph-Null primes, Aleph-Null perfect squares, Aleph-Null fractions/rational numbers. There are more than Aleph-Null real numbers though (real numbers include irrational numbers like pi or the square root of two that cannot be expressed as a fraction).

In the 19th century, Georg Cantor showed how to compare the sizes of sets, including infinite sets, by putting the elements of the sets into one-to-one correspondence. Here you can think of a set as just a collection of objects, e.g. numbers. For example, in the finite case, you can put the elements of the sets {1,2,3} and {4,5,6} into 1-to-1 correspondence, or pair them off, showing they are the same size: 1<->4, 2<->5, 3<->6. You might say you could just count the elements in both sets and see that they are the same size, but the action of counting is in fact putting the objects being counted into one-to-one correspondence with the counting numbers, if you think about it.

One can think of finite examples where one can prove two large sets are the same size without having to count them. E.g., at a mass wedding of Moonie couples, if there are no men and women left over in the stadium then we know there are an equal number of men and women i.e. the men and women have been put into a (romantic) one-to-one correspondence, so the set of men is the same size as the set of women, but we don't know the size.

In the infinite case, we can't count the elements of the sets but, like with the Moonies, if an infinite set can be put into one-to-one correspondence with the infinite set of counting numbers or natural numbers, namely {1,2,3,4,5,6,7, etc.} then we consider it the same "size" as the set of natural numbers and we say that infinite set is "countable". Note that strict subsets of the natural numbers can be as "big" as the set of natural numbers. e.g. the set of even numbers {2,4,6,8,10, etc.} is missing half the natural numbers but is countable. To see this, you need to put the even numbers in one-to-one correspondence with all the natural numbers. This is easily done: 1<->2, 2<->4, 3<->6, 4<->8, 5<->10 etc. It can be proved that every even number will be in this list (just divide it by 2 to find its partner). Therefore, the set of even numbers is the same size as the set of natural numbers and so is countable. 

You provide two infinite sets of numbers in your question. The set of primes was proved infinite by Euclid, and the normal numbers or composite numbers are simply made by multiplying the primes together and so the set of composite numbers is also infinite. The set of primes and the set of composites are subsets of the natural numbers. The natural numbers have a natural ordering, namely, 1<2 1-to-1="" 1="" 2="" a="" also="" and="" any="" are="" argument="" as="" be="" biggest="" both="" by="" can="" composite="" composites="" correspondence="" countable.="" countable="" each="" etc.="" for="" idea="" in="" into="" is="" it="" makes="" match="" matching="" natural="" nbsp="" next="" number="" numbers:="" numbers="" of="" other.="" p="" prime="" primes="" put="" same="" sense="" set="" size="" smallest="" so="" subset.="" subset="" taking="" the="" then="" therefore="" used="" we="" with="">

Cantor also proved that the set of real numbers (all the finite and infinite decimal numbers e.g. 2, 4.5, PI, sqrt(2), etc.) cannot be put into one-to-one correspondence with the natural numbers and is therefore uncountable. (see: https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument). So, in some sense the infinity of real numbers is "bigger" than the infinity of natural numbers. This answers one’s other question: there are many degrees of infinity.

The confusing part is this. If I have a bag of all the natural numbers and take natural numbers out one at a time in the order 1,2,3,4,5, etc., then whatever natural number you may come up with, however big, I will eventually draw it from the bag given enough time. The point is that the same is not true of the real numbers. If you have a bag of all the real numbers and take real numbers out one at a time, in whatever order, I can build a real number (in fact many real numbers) as you do this which you will probably never draw out of the bag. This is shown by Cantor's diagonal argument also used by extensible by Cheng.

The question then is: who cares if there are different size infinities? Well, the set of real numbers, which Cantor showed to be uncountable, is required for calculus which is crucial to physics, engineering, applied maths, etc. And in fact, some mathematicians are sceptical of these ideas about infinity and try to prove calculus theories using only finite maths.

Also, Cantor considered the obvious question: is there an intermediate infinity strictly between the infinity of the natural numbers and the infinity of the real numbers in size? Cantor conjectured that there was no such intermediate infinity and this is known as the Continuum Hypothesis or CH. Cantor apparently went insane trying but failing to prove it. In the 20th century, Gödel and Cohen showed that CH can neither be proved nor disproved from the accepted foundations of mathematics, which explains why Cantor couldn't prove it - it's not provable nor is it disprovable! So, CH is an example of a mathematical statement which is undecidable, and is part of the crisis in the foundations of mathematics. 

This is one of the top experts in the field, Hugh Woodin, explaining the current state of play in this crisis:


In an ironic faint echo of Cantor's descent into insanity over a century ago, in this talk Woodin says that 15 years earlier he believed CH was false, and now he believes it true!

How bad is this mess in Maths? Well, to prove that arithmetic (+,-,x,/) is consistent i.e. that you won't end up with contradictions, you need to first build a bigger system than arithmetic in which you can prove the consistency of arithmetic. But you then can't prove the consistency of the bigger system without building an even bigger system, and so on. So, it's theoretically possible that a primary school child doing their sums could end up proving 0=1, which is clearly a contradiction. No mathematician believes this will happen, but no-one can prove it won't currently. The video shows the lengths mathematicians have gone to try to resolve this issue.

Cheng's book is what you need to study first before you can get an idea of what the video is about, although the talk is considered as aimed at the layperson.

It's when Cheng started tackling Calculus and the infinitesimal small that things started going downhill.  What happened to Newton and Leibniz???

9 comentários:

Book Stooge disse...

First, and most important:
"and whether or not I’m fat, this comes down to definitions".
I'm sorry to be the one to have to tell you, but yes, you are fat.

Now that that is out of the way...

I have to admit, I didn't follow the majority of what you wrote, but what I did get is that this book seems to try to make infinity into a number. Hence all the playing and tricks and whatnot. All of these contradictions would disappear if infinity wasn't treated as a number. Infinity is not the realm of Mathematics but of philosophy and schools of logic.

Let me know if I read your post wrong and drew wrong conclusions.

Manuel Antão disse...

If I remember my bedtime stories correctly, isn't a chubby troll even more dangerous? Chubby trolls are very territorial and your common internet troll is surrounded by it's kin, so when the food supply is threatened or sparse they turn on one another in a horrifying display. I recommend popcorn while viewing the festivities.

Now that that is out of the way...:)

And no. Math belongs to the math realm not to shitty philosophies. Aleph null is the countable infinity. Anything that can be counted falls into this one. You can count integers. You can count primes (as in the 17th prime) or whatever. So both the integers and the primes are infinite in the sense of aleph null. You can draw a line from each prime to its position in the sequence and, in that sense there are "the same number" of them. The prime numbers are a subset of the integers, but you can put the primes in a one-to-one relationship with the integers, with every integer paired with a prime number, so in that sense there are equal numbers in both sets. That is how we can define an infinite set. Infinity is weird...

Book Stooge disse...

But "Infinity" isn't math. It's a concept that can applied to many things besides math. Math and numbers are just one of the more easily used examples in explaining "Infinity". And that is why I said it belongs to Philosophy. Math just hijacked it ;-)

And what I find really interesting, is that we can comprehend the idea of Infinity even while it ties us in knots, or drives us mad, as it did that guy you referenced. If it was truly beyond our scope, I don't think it would ever come up as even an idea.So we can grasp at least a part, if not the whole.

On a completely unrelated note:

Thanks for saying what you did on the latest Surviving a Bad Book post. I was really trying to be nice to that guy, as he had JUST started following me. But the first words on MY blog are him complaining about how hard he as an indie has it? I've said some things on other peoples' blog over this past year that I've regretted, so I wanted to show this guy some mercy but my goodness, I really, really, really wanted to light into him with both fists and maybe a foot or two. I figure he's used up his grace period, so we'll see what happens in future posts. But thanks.

And thanks for being a reader first when interacting with me.

Manuel Antão disse...

At the end of the day, you're right. "Infinity" even when applied to Math is counter-intuitive. Maybe that's why it's one of the most difficult Math areas.

It's trolling that gets me in knots not infinity. No two ways about it...

I have an ex-friend who is clearly a troll online. The weirdest part was the disconnect between his online and offline behaviour. Offline, he was polite, a 'gentleman' almost, with any strangers he met. A real 'nice guy'. Online, he seemed to spend his life creating problems both with his friends on FB, and I imagine with strangers on comments elsewhere - for no obvious reason. The disconnect between the two personalities was alarming to see. Perhaps his offline persona was heavily filtered for social norms, and he just felt free of all of that online, even on FB where his identity wasn't hidden. I don't know. I don't pretend to know how these guys tick...

The untouchable cowardice of these guys. You just can't give somebody a slap for being an obnoxious bastard anymore. Maybe a rambling story, but my father once knocked out a zookeeper at the Lisbon zoo in the 70s, who in front of me was battering an elephant across the face with a cane. That kind of justice no longer available to us. But I can dream just the same, can't I?

It's been a pleasure being a reader of your blog. With so much online crap, one of these days I'm gonna call it quits...

Book Stooge disse...

I know you have commentmod on, so I can't tell, but it sounds like you've been trolled recently?

Dreams are what keep us going sometimes. As for calling it quits, I know what you mean. I think that limiting my social sphere to WP and a tiny bit on Librarything has saved me. I quit facebook, quit booklikes, don't have any social interaction blogspot and do nothing on tumblr. Every little bit helps.

Thankfully, no one I know has had that big a difference that you've seen in your old friend. I'd be very worried. Now, I've got some friends who are trolls in real life as well as online :-D But that's a different matter.

Manuel Antão disse...

Online trolling is the main reason why I've got my blogger site protected in terms of commenting. You wouldn't believe the crap I have to deal with...

Manuel Antão disse...

If I'm feeling a bit mardy and I get one of those nasty comments on my blogger, sometimes I do crazy stuff to those people...Mum's the word...:)

Book Stooge disse...

What I would like to know is why you get trolled at all. Don't take this the wrong way, but you don't seem to have a lot of followers [of course, without a "like" function on blogspot, you can't see those who just read], or at least many people who comment. I see one or two other people here and then Troy occasionally on WP.

So any trolls aren't being drawn by the chance of 60seconds of fame by the hordes of other people here. Does that make it your content in your reviews or the books themselves? I find it hard to believe that someone would troll you over books on cybersecurity, etc, but hey, you're obviously getting it for something.

Sorry to go on like this, but I find it fascinating how these things work out. As long as they're not happening to me that is.

Manuel Antão disse...

An example: http://manuelaantao.blogspot.pt/2016/10/im-getting-stick-from-grs-staff-and.html

This is the only one I bothered to answer. From that moment on, no more comments without my saying so.

I get stick from authors, publishers, and even from some bloggers...