We started with a generally tame discussion of intractable problems, meaning problems that strictly speaking can be solved, but the only (so far known) algorithm is so slow that it can only be used on trivially small problems. The big-O would be exponential or worse. Boolean satisfiability is the fundamental example. Think of a large digital circuit with N inputs and no feedback, that is just a simple combinatoric logic circuit. Consider when N is 1000: bool f(bool x[1000]) // I know the 1000 doesn't belong there { bool and1 = x[983] && ! x[1] && ! x[27] && x[352]; bool and2 = ! x[77] && x[423] && x[26] && ! x[851]; bool or1 = and1 || and2 || x[442]; ... ... return ! and998 && and832 && and305; } The question is can we find input values that will result in this circuit/ function returning true? bool inputs[1001] = { 0, 0, 0, 0, ..., 0 }; while (inputs[1000] == false) { if (f(inputs) == true) { // the answer is yes, print inputs or something break; } int pos = 0; while (true) { inputs[pos] = ! inputs[pos]; if (inputs[pos] == 1) break; pos += 1; } } // the answer is no It is clear that the time for this is at least exponential. There are two to the power of 1000 combinations of inputs to try. If the answer is going to be no, we have to try them all before we can know that. 2^1000 is almost exactly 10^301 (within 8% of it) and that is very close to the maximum value a double can take. Assume a futuristic computer that can compute one "step" is a nanosecond. That's still 10^292 seconds, which is over 3*10^286 years. There isn't a good way of saying that number. So for any reasonably large circuit, Boolean Satisfiability can't really be solved. It turns out that there are a lot of other problems of seemingly completely different types, that are in a way equivalent. That equivalence is through a transformation. You can take an instance of another problem, Knapsack or Subset Sum are good examples, somehow transform it into an instance of Boolean Satisfiability, then somehow transform the result back into a result for the original knapsack problem. They are all intractable problems as far as we know now, but because of this equivalence, they are in what some people consider a precarious state. If someone comes up with a good solution for any one of them, it will automatically provide a good solution for all of them. These problems are called the NP-complete set and we'll spend some time looking at them and related things. Then we went on to matters of decidability and Computability. At the beginning of 20th century it was widely believed that knowledge, at least in a logical or mathematical domain, if not a scientific domain of experimental learning, could be complete. That is complete in the sense that people often get from studying calculus: if I knew all the tricks (substitutions etc) I could determine the formula that results from integrating any other formula, and we expect it to be possible to discover all the tricks. There should be a "theory of everything" that is available to us. In the realm of mathematics and logic, the theory of everything would mean that it would be possible to prove the truth of every true assertion and the falsity of every false assertion (that is completeness), and it would be impossible to produce a proof of anything that is false (consistency). And of course every assertion is either true true or false, so there is nothing else. Finding that theory of everything became a Big Thing. Bertrand Russell (a very famous philosopher) and Alfred North (just as famous at the time) set out to do that in their book Principia Mathematica. It was to produce a perfectly complete definition of everything and how to prove or disprove anything in a way that is called mechanical: the steps are precise and unambiguous and fully defined. A machine would be able to do anything, no intelligence required, if only a machine capable of manipulating symbols could be imagined at the time. (Actually it could, Charles Babbage and Ada Lovelacehad already developed the principles). They started from the absolute minimum, even finding the need to define exactly what it means for two things to be the same, working through boolean logic and a lot of things. But the task proved much bigger than they had expected. Very near the end of the large and almost unreadable book they managed to define exactly what 1 + 1 = 2 means, and to prove that it is true. A few years later, Godel (should be an umlaut on the o, but my keyboard can't manage that. It is usually rendered as Goedel in English, so that the pronunication will be close to correct) showed with his Incompleteness Theorem that there couldn't possibly be a theory of everything. Simplified a bit, it says that in any useful system of logic (that is and system that is capable of describing simple arithmetic of whole numbers, and what use would logic be if numbers were too complicated for it) there must be things, let's call them assertions, that can not be proven to be true but also can not be proven to be false. It was a lot like constructing an assertion that says "this assertion is false", but constructed entirely from formal logic, no woolly things like words. The assertion is saying that it itself is false, so if it is correct (true), it must be false because that is exactly what it is claiming. But if it is false, that means that it is an untrue claim. It is claiming to be false, therefore it must be true. If it is false it must be true, if it is true it must be false. It should be pointed out that that description isn't much more than just playing with words. A well known pointless paradox. Almost without meaning. What Godel produced was absolutely precise, allowing no quesions of what exactly the words mean. Words were just peripheral to it, just there so that the reader can see what is going on. It is all just symbolic logic, completely defined. In fact, his work demonstrated two different but closely related things, completeness and consistency. They are properties of systems of logic. If your logic is complete, then (more-or-less) it provides some way to either prove or disprove everything. Consistency means that it is not possible to both prove and disprove one thing. He showed that any sytem of logical reasoning that is powerful enough to be useful must either be incomplete or inconsitent, or of course both. The powerful enough to be useful phrase just means, as said earlier, that it can handle simple arithmetic, a very basic requirement. We will not be looking further at Principia Mathematica, but there is some value to be derived from a closer look at Godel's theorems. That has said a lot about there being problems that can't be solved. We also investigated another direction that will eventually lead to important and interesting conclusions. The initial question was "how many numbers are there". The conventional answer "infinity" is only viable if the word "infinity" actually describes a number. In its usual sense it doesn't. The familiar infinity symbol, an 8 lying on its side, also not on keyboards, is only meaningful in limits (as in calculus) it doesn't represent a number, just a direction for unlimited growth. The other common claim that infinity is one divided by zero also has no real meaning, it is either a misuse of words or a lack of understanding of arithmetic. We know that even if the conventional idea of infinity doesn't work as a number, there are still infinite things. There is definitely an infinite number of numbers. But what about different kinds of numbers? There are definitely an infinite number of "natural numbers", that is positive whole numbers, there are definitely an infinite number of "rational numbers", i.e. fractions, and there are definitely an infinite number of "real numbers", numbers with a decimal point that may or may not also be expressible as fractions. But are there the same number of natural numbers as there are rationals or reals? We need to establish a way to make the comparison of ininite quantities meaningful, and that comes from thinking of extremely primitive cave- man times when people had not developed a concept of numbers at all. Such a caveman can tell that one thing isn't as many as two things, and may even have had words for one and two. But if two rival cavemen, perhaps one who fams small dinosaurs and one who farms coloured pens, have a dispute about who is the most successful, they are not capable of counting the herd of small dinosaurs and seeing that there are 34 of them, then counting the number of colured pens and seeing that there are 37 of them, and therefore knowing the answer. If you assume that having a lot of dinosaurs around is some sort of success. But there is still a way they can settle their dispute. It is by pairing their herds off. They repeatedly pick one small dinosaur and one coloured pen and tie them together. Eventually one of three things will happen. Possibly every coloured pen will be tied to a small dinosaur but there are still some unpaired small dinosaurs. Or every small dinosaur will be tied to a coloured pen, but there are still some unpaired coloured pens around. Or they will end up with every coloured pen and small dinosaur tied up with none of either left unpaired. In each of those cases they know which there is more of, even though they still can't describe the hred sizes in terms of numbers. This one-to-one pairing of coloured pens and small dinosaurs as a bijection. A thing from set theory. A bijection can be viewed as a function from one collection of things (its domain) to another collection of things (its range). Give the function something from its domain as a parameter and it delivers something from its range as the result. If the function is indeed a bijection, then everything in its domain will result in a different thing from its range, and everything in its range will be delivered as the result from a different thing is its domain. If you can come up with a bijection between two groups of things they must have the same size. The same applies to infinite collections of things, like numbers. Take the natrual numbers and the even numbers: N = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...... E = 0, 2, 4, 6, 8, 10, 12, 14, 16, ...... At first sight N is obviously twice the size of E. Everything in E is also in N, but there is an equal number of thins in N that are not in E, the odd numbers. N must be twice the size, twice the infiniteness, of E. But first sight is wrong. There is a bijection that is very easy to see. Treating N as the domain and E as the range, our bijection function just returns two times its parameter f(n) = 2*n. It works the other way round too. If E is the domain and N the range, f(e) = n/2. Clearly every possible parameter will produce a different result. A perfect pairing between natural numbers and even numbers. The two collections must be the same size. What about natural numbers and integers (whole numbers that can be negative)? Integers can grow infintely two directions, naturals only in one. There must be more integers than naturals. But there aren't. This requires a slightly more complex trick, but not by much. We fold the integers over, starting with 0 and then alternating between positives and negatives, I can make the bijection clear just by writing the beginnings of the two sequences neatly: N = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..... I = 0 -1 1 -2 2 -3 3 -4 4 -5 5 -6 6 -7 7 ..... Just seeing the pattern you know immediately that everyhing in N is paired with something in I and vice-versa. Nothing ever gets paired with two different things. We don't even need to work out what the formula is. But for completeness we can: int nat_to_int(int n) { return (n + 1) / 2 * (1 - n % 2 * 2); } int int_to_nat(int i) { return i * sgn(i) + (sgn(i) - 1) * abs(sgn(i)) / 2; } Odd looking expressions but they work. Both rely on using integer division. sgn is the signum function: negatives give -1, 0 gives 0, positives give +1. It is included in most programming languages, but not C or C++. It has a clever little definition which is very obscure: int sgn(int n) { return (n > 0) - (n < 0); } At this stage, I want to make everything explicit so I'm producing the formulas for the bijections. All you really have to do is establish that a bijection exists. Before tackling rationals, we'll work on something closely related, but a little easier: pairs of natural numbers. Every rational number comes from two natural numbers, the numerator and the denominator, but they can also be negative, the denominator must never be zero, and unless we are careful they have repeats - whereas (5, 2) and (10, 4) are clearly different number pairs, 5/2 and 10/4 are the same rational number. Pairs of numbers seem to have the potential to give us something bigger, they are infinite in two dimensions. There has been nothing like that yet. If we can look at a sample, it will be easier to work through this: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . (9, 0) (9, 1) (9, 2) (9, 3) (9, 4) (9, 5) (9, 6) (9, 7) (9, 8) (9, 9) ... ... (8, 0) (8, 1) (8, 2) (8, 3) (8, 4) (8, 5) (8, 6) (8, 7) (8, 8) (8, 9) ... ... (7, 0) (7, 1) (7, 2) (7, 3) (7, 4) (7, 5) (7, 6) (7, 7) (7, 8) (7, 9) ... ... (6, 0) (6, 1) (6, 2) (6, 3) (6, 4) (6, 5) (6, 6) (6, 7) (6, 8) (6, 9) ... ... (5, 0) (5, 1) (5, 2) (5, 3) (5, 4) (5, 5) (5, 6) (5, 7) (5, 8) (5, 9) ... ... (4, 0) (4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (4, 6) (4, 7) (4, 8) (4, 9) ... ... (3, 0) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (3, 6) (3, 7) (3, 8) (3, 9) ... ... (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6) (2, 7) (2, 8) (2, 9) ... ... (1, 0) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (1, 7) (1, 8) (1, 9) ... ... (0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) (0, 6) (0, 7) (0, 8) (0, 9) ... ... At first sight it is hard to imagine an orderly scheme that will produce all of them. We could imagine going a little bit along the (0, x) row, then moving back and doing a few of the (1, x), then a few of the (2, x), but we'd eventually have to come back and do some more (0, x) and so on. It seems as though it could be done, but seeming isn't enough. Georg Cantor (no E at the end of George as he's another German) in the 19th century came up with a very easy way of handling the problem. It involves enumerating the set in a diagonal way. I'll start counting the diagonals from zero. It will become apparent why very soon. Diagonal 0 consists of just (0, 0) Diagonal 1 consists of (1, 0) (0, 1) Diagonal 2 consists of (2, 0) (1, 1) (0, 2) Diagonal 3 consists of (3, 0) (2, 1) (1, 2) (0, 3) Diagonal 4 consists of (4, 0) (3, 1) (2, 2) (1, 3) (0, 4) Diagonal 5 consists of (5, 0) (4, 1) (3, 2) (2, 3) (1, 4) (0, 5) I hope you've seen the pattern by now. Along any diagonal, the two numbers in each pair add up to the same thing, and that thing is the diagonal's name. You can always tell exactly where any pair is to be found. (A, B) is the Bth item (again counting from 0) in the (A + B)th diagonal. The Nth diagonal always has N+1 pairs in it. The enumeration just runs completely through each of the diagonals in turn, so we get (0, 0) (1, 0) (0, 1) (2, 0) (1, 1) (0, 2) (3, 0) (2, 1) (1, 2) (0, 3) (4, 0) ... It is still infinite of course, but this ordering means that every pair will be reached at some point, and none will be reached twice. These two functions implement the bijection: int pair_to_natural(int a, int b) { return (a + b) * (a + b + 1) / 2 + b; } void natural_to_pair(int n, int & a, int & b) { int d = ((int) sqrt(8 * n + 1) - 1) / 2; int s = pair_to_natural(d, 0); b = n - s; a = d - b; } We have a bijection between pairs of natural numbers and natural numbers, so those two collections must have the same size. Even adding a dimension didn't result in a bigger infinity. There is no need to consider rational numbers any further. We know that (ignoring negatives) every rational number corresponds directly with a pair of natural numbers. 3 / 7 -> (3, 7) so the collection of pairs can not possibly be smaller than the numbre of rationals. Or the other way around, the number of rationals is no bigger than the number of pairs. So of course its size can not be a bigger infinity. If you really want to produce an enumeration of the positive natural numbers, just run through the enumeration of pairs and simply skip all those whose denominator is zero and all those whose numerator and denominator have a common divisor. Just to be sure, 3/7 is a proper fraction that our enumeration must reach, 24/56 (multiply numerator and denominator by 8) is the same thing so it should not be reached. Any fraction that is not in its simplest form (like 24/56) must be made of bigger numbers than the same rational number in its simplest form (3/7). So the simplest form will be on an earlier diagonal than any of the others, and as (by definition) the simplest form's numerator and denominator have no common divisor, so the proposed enumeration will produce it. All the other forms that represent the same value will have a common divisor, so they will be ignored. Given a natural number N, run through that enumeration until N rationals have been produced and stop, the last rational number you saw is the one that under the bijection corresponds with N. Given a rational number, reduce it to its simplest form A/B (by dividing numerator and denominator by their greatest common divisor if they have one) Then just run through that same enumeration, counting how many rationals are produced until A/B comes up. The count will be the natural number that under the bijection the original fraction corresponds with. A bijection only has to exist, it doesn't have to be efficient to calculate it. What about the real numbers? No trick like that will work here because there is no possibility of finding a "next" real number. Between evry two real numbers, another (could be their average) is guaranteed to exist. The method that works for real is reductio ad absurdum. Assume that an enumeration does indeed exist, and then show that that assumprion leads to a contradiction, something that we know must be false. If you only made one assumption and did everything else by the rules and concluded that a false thing is true (or that a true thing is false) then the assumption must have been false. Also, we deal with a subset of the real numbers first, those that are >= 0 and strictly < 1. For them, we know the decimal point is right at the left, so we can just ignore it and the numbers just become unending streams of digits. If a real number doen't go on for ever, like any one that you could actually write down, it still does go on for ever, just with an unending stream of zero digits. We could not write this enumeration down. Even the first thing in it has an unending stream of digits. We couldn't even write down the first number in the enumeration. That doesn't matter. We are only assuming that an enumeration exists, we don't need to know anything more about it. Every natural number definitely corresponds to a unique real number, just put .0 at the end of it, so we know that there can not be fewer real numbers than natural numbers. Therefore for any natural numbre N, our supposed enumeration must have an Nth element, a real number x >= 0 and < 1. And given a real number R in that range, for any natural number N, R will have an Nth digit, even if it is just one of the endless zeros in an R that doesn't go on for ever. And that Nth digit is one of 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9. That may bring up a worry: why are we assuming a decimal representation? It doesn't matter. The same argument works regardless of what base we use, any real numbre can be represented equally well in any proper base. Proper means a natural number >= 2. In fact things would be slightly easier if we used binary. So to recap, an enumeration that exists must have an Nth real number in it, and every one of those real numbers must have an Nth digit (or Mth, they don't have to be the same). Also observe that for any possible digit value, nine minus it is also a proper digit value, which is guaranteed to be different. If we used an odd numbered base that guarantee wouldn't be there. For base 5 the digits are 0, 1, 2, 3, and 4. For one of them, 2, four minus it is the same as it. That doesn't matter. All we need is a way to produce a different digit from any one we are presented with. For any base B and any valid digit D, (D + 1) modulo B is always a valid digit that is different from D itself. Now we can provide a way to construct a number that is guaranteed not to be in any given enumeration without us having to know anything about that enumeration. The number we construct will be described one digit at a time. The Nth digit of our new number is simply nine minus the Nth digit of the Nth number in the alleged enumeration. To actually construct that number you would have to have access to the alleged enumeration, but that is no problem. The method just described clearly what the number will be for any enumeration. We don't need to be able to say whayt the number actually is, we have guaranteed that it will exist, and that is all we need. Where is the contradiction? We can be absolutely sure that the number we have described is in the range of the enumeration, >= 0 and < 1, but does not appear anywhere in that enumeration. If an enumeration is missing a value, it is dy definition not an enumeration. How do we know that our number is not in the alleged enumeration? Well, what position could it possibly be at? For any potential position P (that would be the natural number that our number is mapped to by the bijection) we know that the Pth digit of the Pth number in the enumeration must be different fom the Pth diit of our new number. That is exactly how the new number was made. If the Pth digit of one number is not the same as the Pth digit of another number, they are certainly different numbers. The number we constructed with the nine-minussing is guaranteed to be different from every number in the alleged enumeration. Therefore it is not in the enumeration. Therefore the enumeration is missing a value, therefore it is not an enumeration. The only assumption was that an enumeration exists, therefore no enumeration can exist. Now we know that this size of the collection of real numbers between zero and one is not the same as the numbre of natural numbers. We already knew that it can't be smaller, so it must be bigger. A larger infinity at last. We have shown that a very limited subset of the real numbers, just those between zreo and one is bigger then the set of all natural numbers. So it is perfectly clear that the set of all real numbers is also bigger. The number of natural numbers is called aleph-zero (the zero is written as a subscript to the hebrew letter), and the number of real numbers is called aleph-one. Here is an ASCII-art aleph so you know what they are supposed to look like. Usually when I see them they are a bit more disconnected. xxxx xxx xxxxx xxxxxx xxxxxxx xxxxxxx xxxxxxxxx xxxxxxxxxxxx xxxxxxxxxx xxxxxxxxxxxxxxxxxxx xxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxx xxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxx xxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxx xxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxx xxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxx xxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxx xxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxx xxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxx xxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxx xxxxxxxxx xxxxxxxxxxxxxxxxxxxxxx xxxxxxxx xxxxxxxxxxxxxxxxxxxxxx xxxxxx xxxx