A Transfinite Shave

Russell’s Barber: paradox or (else) pseudoparadox?

Some axioms can be “unprovable truths” of Godel’s incompleteness theorem. Today, we show that Godel’s theorem can be easy to understand in general terms, but hard to understand beyond a typical contradiction, as per Russell’s barber (pseudo) paradox.

Consider the classical Russell’s gedankenexperiment wherein, all the men that live in a village are cleanly shaven. They either shave themselves or they do not. If they do not shave themselves, the village’s only barber must shave them.

Hence there exist two sets: the set of all men who shave themselves and the set of all men who have the barber do it for them.

But, who shaves the barber?

Let us analyze this problem based on Zermelo-Fraenkel’s set theory and Cantor’s set theory.

Zermelo-Fraenkel’s set theory

Take a male barber that lives in the village. He is clean-shaven. Then, either he shaves himself or else he does not shave himself.

Suppose the barber shaves himself. But he shaves only villagers who do not shave themselves. Therefore, the supposition is wrong.

Suppose, now, he does not shave himself. But he does shave all villagers who do not shave themselves. Therefore, this supposition is also wrong.

Hence, Russell’s gedankenexperiment is a pseudoparadox because such a barber cannot exist, since if he existed, he both shaves himself and he does not shave himself. The Zermelo–Fraenkel set theory  does not permit the barber membership of the group; “all men that live in the village”, as allowing this condition causes a contradiction which renders the theory inconsistent.

Cantor’s set theory

The disjunction “either he shaves himself or else he does not shave himself” is true if only one, but not both, of its arguments are true. We can represent such a logical operation as the exclusive disjunction X⊕NOT(X) , where X={0 = he(barber) does not shave himself, 1 = he(barber)shaves himself }.

In a finite field of two elements, X={0,1}, the inverter operation corresponds to the polynomial X+1(mod2), where the addition is computed using the mod2 operation (“exclusive or” operation), and every element X satisfies the property X²=X. Thus, the logical negation, NOT(X), can also be represented by the polynomial X²+1(mod2).

As the addition modulo (commutative) of polynomials and the XOR operation (“exclusive or” operation) are identical, X⊕NOT(X)=X⊕X²+1(mod2)=X²+X+1(mod2).

The polynomial X²+X+1(mod2) is not invertible in a finite field of two elements because it always outputs 1 for X={0,1}.

Then, either X²+1(mod2)=1 or X=1, so that X²+X+1(mod2)=1.
X²+1(mod2)=1, implies that the one-to-one correspondence NOT(X) always outputs 1 for X={0,1}, which is “false”. If X=1, then this implies that the one-to-one correspondence X(=X) always outputs 1 for X={0,1}, which is “false”.

But, X⊕X²+1(mod2)=X²+X+1(mod2)=1,  which is “true”, and, in an exclusive disjunction, the output is “true” only if one of the inputs are “true”.

Then, the exclusive disjunction “either he shaves himself or else he does not shave himself” leads to a result wherein either NOT(X) is a not invertible one-to-one correspondence or X(=X) is a not invertible one-to-one correspondence. As this result is untenable in Zermelo-Fraenkel set theory, the inference by reductio ad absurdum implies the denial of the supposition that the barber exists.

Nevertheless, the baber lives in the village, therefore, the barber is one of the group of “all men”, and, according to Cantor’s set theory, there is a one-to-one correspondence that is not invertible between the set of all men, and its powerset.

Hence, the supposition that the barber exists cannot be denied. Therefore, Russell’s gedankenexperiment leads to a paradox because  there is a true contradiction wherein the barber both shaves himself and does not shave himself.

Such a barber exists, or (else) not exists?

Alexandre de Castro

PS; I’ve changed the title from ‘infinestimal’ here as Alex points out that transfinite is in fact the correct term applicable to Cantor’s theory. I hope to expand upon matters infinestimal & transfinite as they relate to this blog in the next post… Ed.