How Mathematicians View Infinity

[kevinatilusa]

This is in response to a post in VSP which gave some equations like the ones at the end of the post and asked about a couple more equations. I decided I might as well just expand on everything and put it here. If you have any questions or additions, or even want to proudly trumpet that you actually read all the way through this overly long post, feel free to

When mathematicians encounter infinite sets, there's really two different situations they can be in.

Sometimes the question of which elements are/aren't in the set under consideration is critical to the situation at hand. For example, they might want to show that every element in this one infinite set is also in this other infinite set. I'm not really going to focus on that here.

Other times, their main concern is with the size of the set they are working with. It's okay if there are infinitely many points where there is a problem, so long as the infinity isn't that big. Unfortunately, this is a rather vague concept, so in the 19th century the mathematician Georg Cantor tried to make things rigorous. The description of "size" below, and many of the arguments given, are due to him.

Suppose we have two infinite sets A and B and we want to compare their sizes. We say A is at least as big as B (which I will write as A>B) if we can find a map which sends every element of B to one in A, without sending two things to the same place. For example, a cube is at least as big as one of its faces, since we can just map an element of its face to the point at the same location on the cube.

Another way of putting this is that A>B if we can find a map which sends everything in A to exactly one thing in B, and such that everything in B gets mapped onto. Depending on the situation, either description may prove easier to use.

We say that A is the same size as B (I will write A=B) if we have both A>B and B>A. We can show them both in one swoop if we find a map from A to B which is both one to one (no two things in A go to the same thing in B) and onto (everything in B gets mapped to something). At times, however, it is easier to show the two separately.
Examples:
If A and B are finite sets, A>B whenever A has larger size than B (just pair off stuff until you run out of things in B). A=B would mean that both A and B have the same size

If A is the even numbers, and B is the integers. A=B, since we can pair them up 1<->2, 2<->4, 3<->6, 4<->8, ...

If A is the positive integers, and B is the positive rational numbers, B>A since the rational numbers contain the integers. On the other hand, A>B since we have the map 1->1/1, 2->2/1, 3->1/2, 4->3/1, 5->2/2, 6->1/3, 7->4/1, 8->3/2, 9->2/3, 10->1/4, 11->5/1... Therefore A=B. Another way people describe this is that the rational numbers are "countable"


It is usually easier to show that A>B than to show that A is not at least as large as B. The former just requires showing one map, while the latter requires showing that every possible map fails in some fashion. It can be done however:

Fact: Let A be the positive integers. Let B be the set of all subsets of the positive integers. Then it is not true that A>B
(elements of B would be things like the set of all primes, or the set {1,2,3}).
(Proof in spoilers below in case you want to try it out before looking at it)

How do you go about proving something like this? The way to do so is to assume that A>B and reach a contradiction. Suppose we have A>B. Then we must have some map which takes A to B and covers every single element of B. Suppose we sent 1->B ₁ , 2->B ₂ , 3->B ₃ , etc.
For each number a, we either have that B _a contains a, or it doesn't contain a (remember, B _a is an element of B, that is to say a subset of the positive integers).

Let S be a subset such that a is in S exactly when a is not in B _a . By assumption some number in A (call it s) got mapped to S. We have two possibilities.

1. s is contained in S. But by definition S has only those numbers which are not contained in the sets they are mapped to, and we are assuming that s is contained in the set it is mapped to (S). contradiction.
2. s is not contained in S. But by definition S contains all numbers which are not contained in the set they are mapped to, so S should contain s as well. Again we reach a contradiction.

Since we reached a contradiction, one of our assumptions must have been wrong, and the only one we made was that A>B.

If you're familiar with it, this is basically a reworking of what is known as Russell's paradox. In nonmathematical terms, suppose you have a male barber who only shaves those men who do not shave themselves, and shaves every such man. Doe he shave himself?



The exact same proof works to show that for any set A, the set of subsets of A is always strictly larger than A itself. This gives a hierarchy of infinite sets, which may or may not be complete. Namely,

Let A ₀ be the natural numbers (0,1,2,...)
Let A ₁ be the set of all subsets of A ₀ (things like the primes, or {0,1,2})
Let A ₂ be the set of all subsets of A ₁ (for example, the set of all infinite sets, or the set of all subsets of the integers which contain 42).
.
.

We know that A ₁ is strictly larger than A ₀ , but could there be something in between, a set which is strictly larger than A ₀ and strictly smaller than A ₁ ? The assumption that there was nothing in between is known as the Continuum hypothesis, and was considered one of the greatest open problems at the turn of the 20th century. Unfortunately, it has been shown to be unsolvable, in the sense that there is a perfectly consistent system of mathematics where the hypothesis is true, and another perfectly consistent system where it is false.

Most of the infinite sets we encounter, on the other hand, can be matched up with one of the above sets.

The integers, for example, are the same size as A ₀ , because we can pair them up by sending
0<->0 1<->2, 2<->4, 3<->6, 4<->8,..., -1<->1, -2<->3, -3-<>5, ...

The interval [0,1] of real numbers is the same size as A ₁ . Suppose we have a set S of the positive integers. For each x which in S, we take (1/2) to the xth power, then the result up over the whole set to get a real number. (In effect, writing out a number in binary). This isn't quite showing equality, since things like {1} and {2,3,4,5...} get mapped to the same place, but with a bit of wriggling we can check it.

The function tan(pi*(x-1/2)) gives a mapping from (0,1) (the interval minus its endpoints) onto the whole real line, so (0,1)>the real line. The map sending a number to itself gives a 1-1 map, so the other direction holds to and (0,1)=(the real line). Again, wriggling gives that we can include the endpoints too.

The unit square is also the same size as A ₁ . To show the square is at least as big as (0,1), we just project down onto the x axis, which certainly covers everything. To go the other way, we map the number 0.abcdefghi... to the ordered pair (0.acegi..., 0.bdfhj...), giving a map which is onto the inside of the unit square.

Usually when we write "infinity" without saying anything else, we are referring to A ₀ . If we want, we can try to come up with set theoretic meanings of the ordinary arithmetic functions. For example:

If we have two disjoint finite sets of size A and B, the size of their union is A+B. Letting A be the odd integers and B be the even integers (both of which are size A_0), we get infinity+infinity=infinity. (The only meaning this equation has is that the two sides represent sets of the same size)

If we have sets of size A and B, the number of ordered pairs (a,b) with a in the first set and b in the second is A x B. Viewing the rational numbers as ordered pairs of integers (or something at most as large, since (2,4)=(1,2)), we showed above that infinity x infinity=infinity.

If we have two finite sets of size A and B, A^B counts the number of maps which send B to A (each element of B can go to any of A different places in A). infinity ^infinity , then, is the number of maps from the positive integers to itself. We can match those up with subsets of the integers as follows: The map 1->f(1), 2->f(2), 3->f(3), etc. corresponds to the subset {f(1), f(1)+f(2), f(1)+f(2)+f(3),...}. Therefore infinity ^infinity is of size A ₁ , the same as that of the real numbers.

Since infinity ^infinity is the real numbers, infinity ^infinity + infinity ^infinity would be the union of two lines, say the x and y axis. But this is smaller than the whole plane, which is in turn the same size as the real axis (use the same alternation of digits trick), so infinity ^infinity +infinity ^infinity =A ₁ still and isn't any larger. If you want, you can call this the complex numbers, but sizewise (which is the only comparison we can really make here), the complex numbers are the same size as the reals.

I believe that infinity ^{infinity^(infinity^infinity)} (another one that deathstream asked about) would be the same size as A ₃ , but this might be a bit trickier to prove, if it is true at all.

[Leptonn]

That was very good, Kevin. (Thank you) ^infinity

[pikachamp]

*proudly trumpets that he actually read all the way through this overly long post*

What are complex numbers?

[mith]

Yum, infinity.

pika, I'll answer if no one has by the time I get back. I have to go now though.

[Dread Pirate Westley]

From very far away. Infinitely far, really, otherwise, they're just seeing part of it.

[Lucky Wizard]

Complex numbers are the sums of real numbers and imaginary numbers. (An imaginary number is a number that is the square root of a negative number; it can also be viewed as the sine of a number greater than 1.)

Imaginary numbers take the form ai, where a is the square root of the absolute value of the negative number that has this imaginary number as its square root, so an imaginary number line can be imagined. The complex numbers take the form a+bi, and one can visualize a complex number plane where each complex number is at (a,b).

Back to the subject, John Allen Paulos' book Beyond Numeracy gives a great, fairly elementary introduction to infinity (in the chapter titled "Infinite Sets"). It includes a proof that the set of all reals is bigger than the set of all positive integers.

[Guest]

And you were alluding to...what now?

I'm infinitly bored. I scrolled over it earlier but I think I'll go read Antrax's sig now. Perhaps I'll find some wisdom therein.

[lostdummy]

interesting post kevin :)

That is interesting definition for "size" of infinite sets, but I must say that it seems too ..er... broad definition of size for my expectation, at least from two reasons:

1) First, it seems that most if not all logic problems/paradoxes related to infinity all use infinite sets that would go in your A0 classification. So it appears we would need more 'refined' definition of "size" if we want to use it to solve such problems.

2) Second, I have some intuitive problem to accept that set of all integers is same size as set of even integers, or even more that set of all rational numbers is same size as set of integers. Or, to relate to #1, it seems to me that it is possible to differenciate in size among those infinite sets that belong to A0

Examples for my second reason:

a) A=set of all integers, B=set of even integers

it seems intuitive for me that A>B and not B>A. It further seems intuitive to me that there is double number of elements in set A, compared to set B. Or, to use example that could arise in some puzzle, it seems to me that there is about 50% chance to pick even number out of integer numbers, regardless of size of integer numbers set

In this case I would say (intuitively) that size of A is some constant (2) times size of set B. IF B = set of all integers divisible by 5, then Size(A)=5*Size(B)

So, if O(set) is approximation of set size, and const

O(A) = 2 * O(B) ---> A>B


b) A=set of all integers, B=set of rational numbers

Here, it seems intuitive to me that A<B. In other words, for each element a in A, we have lot of elements in B: a/1, a/2, a/..n. Actually, for each element of A, we have around O(A) elements in B, so size of B is approximate to:

O(B) = O(A)*O(A) --> A<B

Or, in our shady probablility area, it seems to me that if we randomly pick one rational number, chance for it to be integer number approach 0%

c) A=set of all integers, B=set of those that contain number 3

this is again familiar problem. In this case I would say that A>B since there are some numbers that exist in A while not existing in B (for example 8), while there is no number that exist in B which also does not exist in A.

but difference to #b is in fact that number of integers containing 3 is rising, so that in reality size of B approaches size of A, so

O(B) ~ O(A)

Or, in our shady probablility area, it seems to me that if we randomly pick one integer number, chance for it to contain 3 approach 100%

---------------------------

I used word "intuitive" a lot above, so this reasoning may not be valid, but it seems acceptable for me that if we are able to find ratio of "sizes" for two sets A and B for limited number of elements N, and if we can get meaningful result even if N approach infinity, then such result shows relative size of sets.

So, if p= SizeA(n)/SizeB(n), and p is meaningful number when n-> inf, I would consider p to represent how much set A is bigger/smaller than set B.

For previous examples,

a) sizeA / sizeB = 2 (for any n)

b) sizeA / sizeB = 0 (when n-> inf)

c) sizeA / sizeB = 1 (when n-> inf)

maybe some of this reasonings are wrong, but i do believe that there is difference in size of sets that would all go into A0 classification from original post.

[eruonna]

lostdummy: The main flaw I can see with your intuitive argument that some of the A0 sets have different sizes is that it uses limits and the limits depend on the path used to approach them.

If I understand your argument correctly, you are saying that if we let P(n) be the probability that a number picked from the first n natural numbers is even then P(n) --> 1/2 as n --> infinity, and that we should conclude from this that there are somehow twice as many natural numbers as even numbers.

What this fails to consider is the possibility of taking the numbers in a different order. For example, we could arrange the natural numbers in the order 0, 1, 3, 2, 5, 7, 4, 9, 11, .... This sequence eventually includes any number you want, so it is a valid reordering of the natural numbers, but if we now let P(n) be the probability that a number selected from among the first n of this sequence is even, then P(n) --> 1/3 as n --> infinity, so we could just as well conclude that there are three times as many natural numbers as even numbers. Similarly we can find orderings so that P(n) goes to any value from 0 to 1, so this way of defining a size for the sets is not consistent.

There is a valid way, as you suggest, to say that the set of even numbers contains only elements of the set of natural numbers but the set of natural numbers contains elements that are not even, and that way is to say that the even numbers are a proper subset of the natural numbers. One of the counterintuitive properties of an infinite set is that it can have proper subsets the same size as the set itself. (Indeed, this is one definition of an infinite set.)

Anyway, I hope this explanation makes some kind of sense to people who aren't already familiar with this kind of thing.

--
Eruonna

[CrystyB]

This reminds me of the How Many Threes? puzzle... Too bad the GLP thread is no more

[Doc Borodog]

[CrystyB]

He probably meant arcsine. Though i could be mistaken, my intuition tells me it's gotta be about the e^ix=cosx+isinx...

[Lucky Wizard]

What CrystyB said.

Let sin x=a.

cos x = sqrt(1-sin ² x) = sqrt(1-a ² ) = i*sqrt(a ² -1)

e ^ix = cos x + i sin x
e ^ix = i*(a+sqrt(a ² -1))
ix = ln(i*(a+sqrt(a ² -1)))
ix = ln i + ln(a+sqrt(a ² -1))
ix = (ln (-1))/2 + ln(a+sqrt(a ² -1))
ix = pi*i/2 + ln(a+sqrt(a ² -1))
x = pi/2 + ln(a+sqrt(a ² -1))/i
x = pi/2 - i*ln(a+sqrt(a ² -1))

[CrystyB]

Addressing lostdummy's post, i'd like to point out the way we compare sets.

For finite sets, people who can't count can still compare them by looking for a 1-to-1 correspondance between the elements of the two sets. For two finite piles that each contain identical objects (e.g., a pile of manatees and a pile of aardvarks), the order of selecting objects out of the piles does not matter. All that matters is that there will at each step be exactly one object selected from each pile.

Turning to infinite sets, mathematicians continued to ignore the order of selecting objects from each set. If at each and every single step both sets still have elements in them, then there won't be a smaller one and a bigger one. Writing this down, it seems less substantial. I'll go for the more accurate description.

For the finite sets, when every element of one set can be paired up with some element from the other set, then clearly the first set is smaller than or equal to the second (after finishing up all the elements in the first set there just might be some elements left over in the second set, making it bigger). This can be extended to infinite sets: if every element of the first infinite set can be paired up with some element from the second set, then the first set is considered smaller than or equal to the second. But what if both sets have this property? Both are smaller than or equal to the other. Then they should be considered equally infinite, since labelling any of them as bigger would disagree with the fact that it was paired up with a subset of the other...

To Be Continued... I need to look deeper into this! I feel like my arguments are not solid enough.

[Bicho the Inhaler]

lostdummy,

Measure theory is one branch of mathematics that at least partially realizes your intuition. Measure theory can compare infinite sets in a way that is often more intuitive than comparing cardinalities (which is what kevinatilusa was talking about). For example, you can turn the Euclidean plane into a measure space via the Lebesgue measure. In this system, a filled circle of radius 3 is strictly bigger than a filled circle of radius 2, no questions asked, although both have A ₁ cardinality in kevinatilusa's notation. The Lebesgue measure of a set, intuitively, is just its area. There are still some things you won't like, such as that a straight line is the same size as the empty set (both have measure 0). You can even resolve some of these issues by switching to the Hausdorff measure, which is more "detailed" than the Lebesgue measure. These measures also can't really compare sets with infinite area. There are such things as non-measurable sets, which can't be given a size, but you really have to go out of your way to make them.

All of that is just one example. When dealing with abstract objects, like infinite sets, a lot of the time mathematicians invent (or discover, depending on your philosophy) constructions that have non-intuitive aspects, but whatever your intuition is, as long as it's logically consistent, there's a way to make it work by the right construction.

This thread is about "how mathematicians view infinity," so it seems wrong to omit an important angle that is quite different from the preceding discussion. What if infinity were a complex number? Where would it fit on the complex plane? To deal with this, we don't think of infinity as a number describing the size of anything; instead, we want some geometric intuition. Imagine the complex plane as the xy plane in 3-dimensional space, and put a sphere of radius 1 centered at the origin. You can connect the "north pole" of the sphere (the point (0,0,1)) to any point s in the complex plane by a straight line segment, and this segment will intersect the sphere in exactly one point (not including the north pole), which we call f(s). The function s -> f(s) maps the complex plane to the sphere in one-to-one fashion. (Examples: f(0) = (0,0,-1) (the "south pole"); f(2i) = (0,4/5,3/5).) Notice that the north pole itself is not f(s) for any s, but every other point of the sphere is. So you can think of f as taking the complex plane and shrinking it down and covering a sphere with it, missing a single point, our north pole. But as s gets farther and farther from the origin, f(s) gets closer and closer to the north pole. So you could say that f(s) approaches the north pole as s approaches infinity. It seems reasonable to posit then that f(infinity) = north pole. We can see "infinity" as a number that doesn't quite belong on the complex plane, but that completes it to make a sphere.

In this view, there aren't different sizes of infinity or anything; infinity is just a point like any other. Neither view is wrong; they just have different applications. When we speak of "views of infinity," these views are nothing like political opinions. A single mathematician can see infinity differently depending on the context.

[Guest]

[Jack_Ian]

I've always thought of Cantor numbers as describing the size class of a particular infinity rather than the actual size and I therefore have a difficulty believing proofs that cancel infinities out when they have the same Cantor number.
Somehow it just seems wrong to me.
Is there some criteria that says when such cancellations are allowable and when not?

Also, how do you go about answering a question like the following:
How many positive integers have an infinite number of digits when expressed in base 10 with no leading zeros?
a) None. All integers have a finite number of digits.
b) One. The final integer.
c) Infinite. 111..., 222..., 333..., ..., 999..., 101010..., 121212..., 131313..., ...
d) Invalid question.
It seems to me that any of the above answers could be correct depending upon how you view the question.

^{(BTW Thanks for starting this thread, I love trying to wrap my head around such concepts)}

[extro...]

All positive integers are finite, by definition. a) None.

[Chuck]

a) None.

There is no last integer and an infinite string of digits doesn't represent an integer because you can't count to it.

[old grey mare]

If
sum(k = 1 to infinity) (9 * 10^k) can't be a number, does that mean that
sum(k = 1 to infinity) (9 * 10^-k) isn't a number either?

[Guest]

no

[Bicho the Inhaler]

[old grey mare]