God Exists Just Have Faith (And Unequal Infinite Sets)

(important preface: I am an agnostic/atheist, but think this is a very cool argument)

What if I told you God exists? That you can’t argue that he doesn’t, because you’re not capable of understanding him. Furthermore, what if I told you I can prove it? Would you believe me? In this blog post, I’ll do exactly that. Oh, and while we’re at it, why not show how you can compare the sizes of two infinite sets. Because, as we all know, not all infinities were created equal…right? But that is not ambition enough. Let us also explore its impacts on language and the theory of computation. Furthermore, I am attempting to ensure everyone, regardless of mathematically or theoretical ability, can follow the construction of this argument.

So put your believer hats on, whip out your calculator, and read carefully. We’re about to explore the depth of an argument that was not only used long ago as proof God exists, but also is the foundation of modern computers.

Computers can do anything. Except what they cannot do.

In theoretical computer science, there is a very real problem known as the halting problem. Superficially, this problem asks the question “Given a particular input, can a machine ever determine whether it is going to stop what it is currently doing?”

For example, lets say we have some machine called U. Lets say U’s purpose is to simulate other machines on given inputs. That is, we can hand U another machine and say “Hey, U, act exactly like this machine would act on this input.”

So now that we’re all buddy buddy with U, lets abuse our friendship a little. Construct a new machine called M. Being the asshole you are, you make M loop. That is, M never completes what it’s doing. Remember riding the school bus and kids singing “This is the song that never ends…”, yeah, you made a machine that does exactly what that song does.

Sidebar: In theoretical computer science, U is known as a universal Turing machine. That is, it is a machine capable of running other machines. Universal Turing machine’s played a very important role in stimulating development of store-program computers. That is, you have U to thank for your ability to double click a button and log onto Facebook, or any other multitude of things. Without it, you’d need a lot of wires and a punchcard.

Next, we encode the machine M and its input in such a way that U can simulate it. In order to do this, we encode M and its input as what is known as a language. The precise definition is not important, but sufficient to say it has the same definition as spoken languages. We’ll call this new language A.

Now we return to U, with language A in hand, and say “Hey, U, I want you to run A and let me know when it’s done, ok?” Well, wait, there is a rather obvious problem. U wont ever let you know anything. U wont ever tell you it’s done. Nor will it ever tell you “I’m looping”. That’s because, as far as U knows, there is still work left to be done, so do it. U does not know if it is almost done, or if it has an infinite amount of work remaining.

But what if there was a way for us to tell if there was work left to be done? What if, say, we could tell we were looping forever, and not halting. What if we could somehow look at a set of problems and recognize if it goes on forever or not.

This problem, is known as the halting problem. It is undecidable. To “prove God exists” we must first prove that this problem is undecidable.

In 1873 the decision about undecidability was decided

In 1873, a mathematician, George Cantor, discovered a technique for comparing the size of infinite sets. This method, incidentally, can be used to prove the halting problem is undecidable, and that “God exists”. So, lets examine how we can compare the size of two infinite sets, which will give us key insight into whether we can recognize the halting problem.

“Just count them!” some of you (likely the less mathematical ones) are yelling. Well, I challenge you to count to infinity. Hint, you can’t. If you could, the halting problem would be trivial. Thus, if two sets of numbers are of infinite size, how could you ever compare the two of them? You certainly cannot count them to decide which is bigger, but you can still compare their sizes.

Lets start off with an interesting question:

Which is the following two is larger: The set of numbers natural numbers — called N — (that is: 1, 2, 3…all the way to infinity), or the set of even numbers — called E — (that is: 2, 4, 6…all the way to infinity)?

The natural numbers must obviously be larger! After all, there are only half as many numbers in E as there are in N! Not so. It turns out they are of equal size. In order to prove it, we need to get our hands a little dirty.

A quick proof

Lets assume that we have the two sets, N and E, as defined above, and some function f. f takes one input and provides one output. For example, f(1) = 2, where 1 is known as the input and 2 is known as the output. Now lets setup a few tools we’ll need for this proof:

• f is a one-to-one function: That’s a fancy way of saying that for any unique input for f its output will be a unique value. For example, if we have f(1) = 2 then no other input could ever output 2. As an example, f(3) = 2 would be impossible given our previous input/output of f(1) = 2.
• f is an onto function: That’s another way of saying that for every element in E, there is some element in N that will, when input into f, output that element from E. Formally: For every e \in E, there is an a \in A such that f(a) = b.
• Finally, Cantor defined sets to be the same size if there exists a one-to-one, onto function f for those two sets.

So lets quickly show that N and E are of equal size. Let us construct a table of their inputs and outputs. In the below table, n is a number from N which is fed into f, and f(n) is the output of our function f. Notice that, if we define f(n) = 2n, then the output just so happens to always be a number in E.

We can see that this function is one-to-one and onto, thus, N and E are the same size!. Go figure…

Cantor further says that a set is countable if it is either finite, or has the same size as N. That is, if some set if of at most N, then we can recognize it. This is trivially true because we can either count all the numbers in a non-infinite set, or simply compare its size to N and recognize if they are equal.

But, wait. A you insinuating that there are numerical sets / languages that we cannot recognize?

Well if I were, that’d have quite powerful implications, wouldn’t it. Perhaps someone could argue, then, that we cannot recognize the language of God…

On the 7th day, he hid within unequal infinite sets

Lets try and prove languages exists that cannot be recognized by the machines we created above. Perhaps, they are not capable of recognizing languages that’ll run forever.

For the sake of brevity, a complete proof will not be provided (also because it is quite rigorous and will detract from our ultimate goal). But I will provide a quick overview.

Consider the two infinite sets, N and R. N was previously defined (1, 2, 3…). For R, we will define it to be the infinite set of real numbers (that is, a number with decimals — ex: 3.14159…). Construct the table again:

Now, lets just say somehow you managed to construct the entire table. I can then construct a number that will be guarenteed not to be in the table. The construction of this devilish number is created in the following way:

1. Look at the first mapping, f(1) = 0.14159…. In order to make sure my number does not match, I’ll just look at the underlined decimal place, and pick any other number, say 2. Now, I’ve guarenteed that it is not possible for my number to match f(1).
2. Repeat with the second number: f(2) = 0.555…again we change the underlined number to be something different. Say, 3. We have now guarenteed that it is not possible for my number to match f(2) (and f(1)).
3. In the third one, 0.12345…change the underlined number to anything other than 3, say 4.
4. Repeat for all remaining numbers

The results? 0.234…, a number which has no mapping. Because it has no mapping — and given our previous definition that equal infinite sets must have a mapping for all possible inputs — these two infinite sets are not of equal size. That is, one infinity is larger than the other infinity!

WTF?!

So, what did all that mean? Well, by showing that R is larger than N, we have shown that it is, by definition, uncountable. Ok, big deal? Well, actually yes. Since R is uncountable, how can you ever recognize when I have given you the set R? How, for example, can you tell it is not some other arbitrary set Q? Or Z? Or the language spoken on planet Romulan? You can’t.

We have just mathematically shown that there exist languages that our machines are not capable of recognizing. Seeing the “God exists” argument yet?

Bringing it all home

We were interested in the halting problem. We question if you could ever recognize a given language loops forever. To identify infinite loops, we needed to verify we can recognize all possible languages. Unfortunately, we proved that we cannot recognize such languages. That is, we are not able to construct machines capable of recognizing all possible languages. Now, lets finish this off.

Lets say the human brain is like the machines we defined earlier. Then, using the mathematically arguments we constructed, there exists languages/things, that we cannot recognize/understand. Thus, we may not be able to understand if a God exists, but instead need to just have faith.

You believe me, don’t you?

Just have faith…