Introduction to Proofs

Proofs are, indeed, a difficult thing in mathematics. But mathematics is at its core just proofs, and less importantly calculations.

To prove requires a certain ingenuity to construct the right object or synthesize ideas in the right order and then show that that proves what you think it does.

For example, prove that the interval \([0,1]\) and \([0,1)\) have the same number of elements. This means you can find a one-to-one function (a bijection) between them. Try it, see if you can figure it out.

I wrestled with this problem for a long time. I tried drawing graphs but they all had a curve, meaning they fail the horizontal line test.

It turns out, that you have to construct a clever object:

\(f:[0,1]\to [0,1)\) by the following:

For all fractions \(\frac{1}{n}, n\in\mathbb{N}\):

\(f:\frac{1}{n}\mapsto \frac{1}{n+1}\)

for all else:

\(f:x\mapsto x\)

You may have heard of this, it’s commonly called Gilbert’s Hotel. In order to map between infinities where one of them has “extra” elements. You shift \(1\) to \(\frac{1}{2}\), \(\frac{1}{2}\) to \(\frac{1}{3}\), and so on. This is indeed a bijection.

Being exposed to problems and solutions like this increases your ability to solve similar problems. Especially in fields like analysis, we require increasingly more and more machinery and ingenuity to solve difficult problems. To prove something new requires even more of the same.

Intro to Real Analysis, Cauchy sequences, and the definition of the Real Numbers

In order to any kind of analysis we create a metric space. A metric space is a set equipped with a distance function \(d(a,b)\to [0,\infty)\). We read this as “the distance between \(a\) and \(b\)”. This must satisfy \(d(a,b)=0 \Longleftrightarrow a=b\) and \(d(a,b)=d(b,a)\) as well as \(d(a,b)\leq d(a,c)+d(c,b)\). The first two conditions must clearly be true if we are to call this a distance function, but the last is less obvious. This is called the triangle inequality and it is used a lot. It basically means that our distance function finds the shortest path, and it must be the same length or more to go through a third point. This is obviously true if you think about it in 2d space:

We will now define what makes a sequence converge. Consider the sequence \(\{p_n\}\) which is the set \(\{p_1,p_2,p_3,\cdots\}\). We claim that this sequence converges to \(L\) (limit). Then for any \(\epsilon >0\), there exists an \(N\) such that for any \(n\geq N\), \(d(p_n,L)<\epsilon\).

This formalizes the idea of getting closer and closer to a value \(L\). Any distance \(\epsilon\) I give you, you can give me an index \(N\) after which everything is closer than \(\epsilon\). If I tell you \(\epsilon = 0.001\), you have to be able to give me a number \(N\), perhaps \(N=1000\), so that everything after that is closer than \(0.001\), meaning \(d(p_{1000},L)<.001\) and \(d(p_{45001}, L)0\), there exists \(N\) such that for any \(n,m\geq N\), \(d(p_n,p_m)<\epsilon\). It is important to distinguish this from the definition of convergence. Cauchy sequences have a special relationship with convergent sequences.

It can be proved that convergent sequences are Cauchy. This makes sense, since if elements of the sequence are getting closer to some limit, then they must get closer to each other. However, it is not true that Cauchy sequences all converge. How can this be? Well, I showed an example before, where the “limit” was not in the metric space. In a sense, the metric space is “missing” the value where the limit should be.

In some metric spaces, every Cauchy sequence converges. This is called “the Cauchy Criterion”. For example, in the metric space \([0,1]\), every Cauchy sequence converges. You’ve patched the holes where the limits should be by putting a limit there. In a sense, you’ve completed it. If a metric space passes the Cauchy Criterion, then it is complete. There are no fake limits which are missing from the space.

This concept is very powerful. Consider \(\mathbb{Q}\), the rational numbers. Are they complete? Consider the sequence \(\{3,3.1,3.14,3.141,3.1415,\cdots\}\) which only has rational elements. We know that this will eventually “converge” to \(\pi\), but \(\pi\) is not in \(\mathbb{Q}\) so the sequence does not converge at all.

In a sense we can define \(\mathbb{R}\), the real numbers, as the completion of the rationals. We can define it as the smallest metric space containing \(\mathbb{Q}\) for which the Cauchy Criterion is satisfied. We add in all the points which are the limit of some rational sequence. There are different ways to define the real numbers which I may discuss in the future, but this is a particularly neat one, I think.

Bigger Infinities Than Infinity

Can you get a room in an infinitely large, yet fully booked, hotel? There are a lot of rooms to count in Hilbert’s Grand Hotel, an infinite number of them to be exact. A common understanding of infinity is that it is at the end of counting, the last room. Start at one and end at infinity after a long walk down the hall. There are, however, many more numbers than just 1, 2, 3, etc; so how many of those are there? This is where the notion of thinking of “infinity” as the end of counting becomes complicated. Infinity is specifically bigger than any number you can count to, meaning regular intuition of math stops working. If there were a million rooms in a hotel and all were full, you couldn’t get a room; not a billion or even a trillion. But with infinite rooms, you can certainly get a room in the hotel, just tell everyone to move down by one, and you take the first room.

Now imagine a rather large group of new guests comes, infinitely large actually; how could anyone possibly give all these guests a room? Unlike when you got a room, Hilbert can’t just shift everyone over by infinite rooms. How about another, not hotel related, question, “how many even numbers are there? Odd?” It may be clear that there are the same number of evens as odds, because each make up half of the natural numbers. What if I told you that there are the same number of even numbers as natural numbers. I can hear you thinking, “How can this be?! It’s obviously half as many!” This can be explained by taking each counting number and doubling it; there will be only even numbers and you’ll never run out of numbers because there is no last counting number to double. This idea can be used to fit infinitely more guests into the hotel; scale the room numbers and fit an infinite number of guests between all the current guests. So now Hilbert knows how to add an infinite number of guests into the hotel. He should be done now, right? Wrong.

Word of Hilbert’s extremely spacious hotel has now attracted even more guests than before, an infinite number of buses, each carrying an infinite number of guests, arrive. Once again, the previous methods fail as the room numbers cannot scale by infinity. To fit this many guests, it requires some clever mathematical tricks. One possible solution is to send guests to powers of prime numbers; for example, the guests in room i go to room 2i and those in the first bus in seat n go to 3n, continued for infinite prime numbers for each bus. Another creative solution is to interweave the numbers representing the bus and the seat with the first digit of each, the second digit of each, etc to assign the new room numbers. Each of these methods is able to send any guest represented by a pair of natural numbers (a,b) to a single natural number in the hotel. There are many more possible solutions to this particular section of the problem, an interesting question for the reader’s consideration.

There was a single bus left over after Hilbert somehow found rooms for the infinite busses of infinite guests; however, the guests on this last bus don’t have seat numbers, rather they are all identified by an infinitely long name. It may, at first, seem like a doable task for the expert room arranger; however, this is an impossible task. Unlike the buses of guests, you cannot count these named guests. Since previous groups had a first and second guest, it was possible to fit them into the hotel using the clever tricks explained previously. The group of named guests is simply too large to fit into the hotel. Consider an infinite list of these infinitely long names of the guests. If you generate a new name by changing the first letter of the first name, second letter of the second name, and continue for all the names, you will get a new infinitely long name that is not in the list. You can always “find” new names that make the list even longer. Even if you arranged the names in alphabetical order, you could simply “make” more names in between those names, making it impossible to order and number the new group. Since the members of the group cannot be properly assigned natural numbers, none of the previously explored tricks can fit them into the hotel. Defeated, the hotel manager resigns on the spot, having made all the money he could need from the admission of the previous infinite guests.

Hilbert’s hotel is an example of the difference in cardinality, or size, of sets. Groups with the same or less cardinality as the room numbers could fit, but even then there was an infinite group too large for the infinite hotel. This is illustrated by numbered guests being able to fit into numbered rooms, but named guests could not fit because infinitely more names could always be generated from any infinite list. The number of rooms is considered to be infinite, but “countably’’ infinite, meaning it corresponds in a one-to-one relationship with the counting numbers. As touched on when covering the named guests, the group of guests could not be counted, and therefore could not be admitted. This larger, continually generated infinity, is referred to as “uncountably” infinite, since it cannot be in a one-to-one relationship with counting numbers. The notion of different size infinities is crucial in the study of different sets of numbers.

The technique used to fit guests into Hilbert’s hotel is a valid approach to other, arguably more mathematical, questions. For example, does there exist a function that sends the interval [0,1) to (0,1) with everything in the latter interval being “hit” by a unique number in the previous interval. It turns out that there is. The function exists by “shifting” all the numbers that can be represented by 1/n over to 1/(n+1), sending 0 to ½, and sending the rest of the numbers to themselves.

The existence of a function that sends any set to any other set given by every element of the second set being “hit” by a unique element in the previous set means that the sets have the same cardinality. These functions can be used to compare the sizes of different sets; many of these comparisons require interesting tricks of grouping and moving infinitely large sets around, like those presented in both problems.