Infinite streams of 0s and 1s A = 000000000000000000000000000000000000000000000000000000000000... B = 101010101010101010101010101010101010101010101010101010101010... C = 001101010001010001010001000001010000010001010001000001000001... D = 000000010000000000000000000000000000000000000000000000000000... E = 111111101111111111111111111111111111111111111111111111111111... F = 010100000110110010111101110110100111001111000011100000001110... G = 111111111111111110000000000000000000000000000000000000000000... H = 101100000000000000000000000000000000000000000000000000000000... What do they represent? It is a matter of interpretation. * See them as binary numbers, and they represent integers. Except only zero and infinite numbers are possible, and we're still deciding on the status of infinite numbers. * See them as binary numbers written backwards (e.g. H is 13, G is 131071, D is 128) and they represent all positive integers, even including infinite ones. * See them as bitmaps and they represent sets of integers H = 101100000000000000000000000000000000000000000000000000000000... B = 101010101010101010101010101010101010101010101010101010101010... C = 001101010001010001010001000001010000010001010001000001000001... H is { 0, 2, 3 } B is all the even numbers C is all the prime numbers * Related to that, they represent properties of integers B = 101010101010101010101010101010101010101010101010101010101010... C = 001101010001010001010001000001010000010001010001000001000001... G = 111111111111111110000000000000000000000000000000000000000000... B is the evenness property C is the primeness property G is the being-less-than-seventeen property * Seen as tables of results, they represent "Integer Decision Functions" (IDF). That is, functions which given any positive integer will decide something about that integer, and deliver true or false as the answer. B = 101010101010101010101010101010101010101010101010101010101010... G = 111111111111111110000000000000000000000000000000000000000000... H = 101100000000000000000000000000000000000000000000000000000000... bool B(int n) { return n%2 == 0; } bool G(int n) { return n < 17; } bool H(int n) { return n==0 || n==2 || n==3; } * By assuming a "decimal" point before the digit, they represent real numbers greater than or equal to 0 and less than 1. Because they are infinite, they represent all real numbers in that range, not just rationals. B = 101010101010101010101010101010101010101010101010101010101010... F = 010100000110110010111101110110100111001111000011100000001110... H = 101100000000000000000000000000000000000000000000000000000000... B is 2.0/3.0 F is pi/10 H is 11.0/16.0 If you know how something is to be interpreted, those six things are exactly the same, but in some cases some of them may be harder to write than others. * If I tell someone 13, I have given them exactly the same information as if I had written out 1011000000000000000000000000... infinitely, but with a lot less fuss. * If I tell someone bool D(int N) { return N==7; } [except #] I have given them exactly the same information as if I had told them 128 or written out 000000010000000000000000000000000000... for ever. * If I tell someone bool C(int N) { if (N<2) return false; for (int i=2; ib; } I can always convert it into an ordinary integer decision function like this: bool IDFisbigger(int n) { int (a, b) = anticantor(n); return a>b; } I just have to remember to call it in the correct way. isbigger(x, y) has to be rewritten as IDFisbigger(cantor(x, y)). So functions of multiple parameters are also brought under the umbrella of completely-the-sameness. * If I have a function that produces something more than just true/false as its answer, even that can be written as an integer decision function. Let's say I've got a calculation that produces ints in the range 0 to 7, like this int calculate(int n) { /* who knows what it does in here */ return x % 8; } The IDF version would be like this: bool IDFcalculate(int x) { int (d, n) = anticantor(x); int a = calculate(n); if (d==0) return (a & 1)==1; else if (d==1) return (a & 2)==2; else if (d==2) return (a & 4)==4; } The idea is that IDFcalculate is given a single number that encodes both the value of n that you want to do the calculation on, and which digit d of the binary result you want to see. To get the whole result, you would have to call IDFcalculate three times and recombine the results into the original number: To get the result of calculate(n) you say: int answer = 0; if (IDFcalculate(cantor(0, n)) answer += 1; if (IDFcalculate(cantor(1, n)) answer += 2; if (IDFcalculate(cantor(2, n)) answer += 4; The point is that any function no matter how many arguments it takes, or how big its result, can be written as an IDF. So all numeric functions are equivalent to infinite sequences of 0s and 1s and all the other things. Now remember all the other enumerations. We have created enumerations of all strings, programs, rational numbers, all sorts of things. The existence of an enumeration (of strings for example) means we can line up all the strings one-to-one against all the positive integers, like this: 0: "", 1: "a", 2: "b", 3: "c", 4: "d", 5: "e", 6: "f", 7: "g" 8: "h", 9: "i", 10: "j", 11: "k", 12: "l", 13: "m", 14: "n", 15: "o" 16: "p", 17: "q", 18: "r", 19: "s", 20: "t", 21: "u", 22: "v", 23: "w" 24: "x", 25: "y", 26: "z", 27: "aa", 28: "ab", 29: "ac", 30: "ad", 31: "ae" 32: "af", 33: "ag", 34: "ah", 35: "ai", 36: "aj", 37: "ak", ...... so strings can be used to represent integers and integers can be used to represent strings, and also with all the other enumerable things. So all the kinds of functions we've thought of can be written as simple bool f(int) integer decision functions, and so they all convey no more information than would a set of numbers, a real number between 0 and 1, or an infinite stream of 0s and 1s. we'll just work in terms of IDFs then. Suppose I have an enumeration of IDFs. Without having to know what order I'm going to put them in, I know there will be an IDF0, an IDF1, and IDF2, and so on, where every possible IDF will appear somewhere in that list. A boring way to look at it is: IDF0 IDF1 IDF2 IDF3 IDF4 IDF5 IDF6 IDF7 IDF8 IDF9 IDF10 IDF11 IDF12 IDF13 ... For short, I'll write it differently. F(3) means the third integer decision function in my enumeration, IDF3 F(3,7) means IDF3(7), the result (0 or 1) of giving the third integer decision function 7 as its parameter. I could even think about their infinite digit streams F(0,0) F(0,1) F(0,2) F(0,3) F(0,4) F(0,5) F(0,6) F(0,7) F(0,8) F(0,9) ... F(1,0) F(1,1) F(1,2) F(1,3) F(1,4) F(1,5) F(1,6) F(1,7) F(1,8) F(1,9) ... F(2,0) F(2,1) F(2,2) F(2,3) F(2,4) F(2,5) F(2,6) F(2,7) F(2,8) F(2,9) ... F(3,0) F(3,1) F(3,2) F(3,3) F(3,4) F(3,5) F(3,6) F(3,7) F(3,8) F(3,9) ... F(4,0) F(4,1) F(4,2) F(4,3) F(4,4) F(4,5) F(4,6) F(4,7) F(4,8) F(4,9) ... F(5,0) F(5,1) F(5,2) F(5,3) F(5,4) F(5,5) F(5,6) F(5,7) F(5,8) F(5,9) ... F(6,0) F(6,1) F(6,2) F(6,3) F(6,4) F(6,5) F(6,6) F(6,7) F(6,8) F(6,9) ... F(7,0) F(7,1) F(7,2) F(7,3) F(7,4) F(7,5) F(7,6) F(7,7) F(7,8) F(7,9) ... F(8,0) F(8,1) F(8,2) F(8,3) F(8,4) F(8,5) F(8,6) F(8,7) F(8,8) F(8,9) ... F(9,0) F(9,1) F(9,2) F(9,3) F(9,4) F(9,5) F(9,6) F(9,7) F(9,8) F(9,9) ... ... ...