Choice versus randomness

Theorems follow from axioms (and definitions); axioms formalize our intuition. Nowadays, axioms of mathematics are axioms of set theory. Which intuitive idea is thus formalized?

The idea is, infinite mind (called also "ideal thinker", "ideal mathematician", "omnipotent mathematician", "infinite intelligence" etc.) Every mathematical statement is either true or false (even if neither follows from our poor axioms), since the infinite mind can check all special cases at once, no matter how many cases, – finitely many, countably many or even uncountably many. I prefer to say "infinite machine", but it is still the same idea.

We humans are able to write down all subsets of a 10-element set, surely not of a 1000-element set. Nevertheless we human mathematicians feel pretty sure that the idea of a finite machine (or mind), able to write down not only 21000 but also 221000 objects, does not lead to any contradiction, in other words, is consistent.

About the infinite machine (or mind) we are less sure. Otherwise Hilbert would not ask for an arithmetical proof of consistency of the set theory, and Goedel would not reveal that arithmetic cannot prove even its own consistency.

The infinite machine is able to form (and store in its infinite memory) not only a list of all subsets of the real line, but also a list of pairs (A,x) where A runs over all nonempty sets of reals, and x is an element of A chosen by the machine. This ability is the idea of the famous choice axiom. We cannot instruct the machine how to choose, but still, it can choose. Free will? Not necessarily; maybe the internal representation (of these sets, and whatever) makes it possible.

Being a probabilist, I wonder, what about a random generator? Can the infinite machine produce an infinite array of random bits? A countably infinite array would satisfy me. Alas, this is impossible!

Before proving this negative answer, let me comment on it. For me, our idea of the infinite machine is thus questionable. We want to endow the machine with all our basic abilities, extended to the infinite; but we cannot. Either the choice ability, or the random generator, but not both. The set theory stipulates the choice and sacrifices the randomness. This fact bothers me.

Here is why the choice and the randomness fail to coexist.

Let the infinite machine do the following.

It considers all infinite sequences of bits (not a harder job than all reals...) and groups them into equivalence classes; here two sequences are called equivalent if they differ only in finitely many positions (that is, xn=yn for all n large enough). (Only a continuum of equivalence classes, – much less than all sets of reals...)

It chooses (and stores in memory) one sequence in each equivalence class, – call it the representative of this class.

Now it generates at random an infinite sequence of bits, finds its equivalence class, picks up the representative of this class, and compares the random sequence and the representative via the bit-wise XOR ("exclusive OR") operation. It gets a random element of the zero equivalence class (a sequence with only finitely many "one" bits).

Mind it: a random element of a countably infinite set! Distributed uniformly, that is, with equal probabilities for all elements! This is incompatible with any reasonable probability theory for many reasons. Here is my favorite reason. If X and Y are two independent, uniformly distributed random integers, then X > Y with probability 1, since for every y we have X > y with probability 1. But similarly, Y > X with probability 1, – a contradiction.

This is why the choice and the randomness fail to coexist.