János Geier: Truth value gap in the sky of Cantor's Garden of Eden… 2009.09.23

Phil. Seminar, BTK, Budapest

HANDOUT

Truth value gap in the sky of Cantor's Paradise - or what is it that Hilbert saved?

C: János Geier, 2009-09-18

See also: http://www.geier.hu/Cantor/Cantor_rovid.htm

The original has been slightly supplemented and typographical errors corrected: 16.10.2009

Translated to English: 12.05.20025.

All rights reserved. This article may not be copied, reproduced, or distributed,
either in part or in whole, without the written consent of the author.
The page may be linked. In the event of citation, compliance
with the rules of literary references is a strict requirement.

This article is identical to the text of the Handout distributed during my 20-minute lecture (+10 minutes of discussion) at the Imre Ruzsa Memorial Conference (http://phil.elte.hu/ruzsaconf/) on 18.09.2009, and the 1-hour lecture (+half an hour of discussion) at the Philosophical Seminar (http://phil.elte.hu/tpf) 5 days later on 23.09.2009, apart from the correction of some printing errors.

The abstract submitted to the Philosophical Seminar can be found here http://phil.elte.hu/tpf/2009-2010/September/#5.

Cantor's power set Theorem

Theorem: (Cantor's Theorem) For every set M, M is not equivalent to its own power set 2^M.

Proof: (reconstruction of the well-known textbook versions)

Suppose indirectly that M is equivalent to 2^M, i.e. that

(1) there exists a bijective mapping B: M → 2^M.

Consider the element T of the power set 2^M whose elements are exactly those elements of the set x in the set M, which are assigned to the set B(x) that does not contain x as an element, i.e.

consider the set T∈ 2^M that satisfies the requirement

(2) ∀x∈M [x∈T ⟺ ¬ x∈B(x)].

(*)

Because of condition (1) there exists t =B^-1(T), i.e.

(3) ∃t∈M [B(t) = T].

By using (2) and (3) twice:

(4) if [t∈T] then [¬t∈B(t)] i.e. [¬t∈T], and if [¬t∈T] then [t∈B(t)] i.e. [t∈T].

This is a contradiction, which refuted our initial indirect assumption (1). qed

We will refer to this as the ‘Cantor proof’.

* * *

My assertion: This derivation is incorrect: it does not refute the indirect hypothesis (1), so it does not prove the theorem.

The essence of the error is: it has not been proven that the set T satisfying requirement (2) necessarily exists. In fact, the converse is true: when we reach (2) in the derivation, it can already be proven there (without referring to the continuation of the derivation!), that given the condition (1), T∈ 2^M satisfying the requirement (2) does not exist. For this reason, the expressions (3) is meaningless. (There is no t∈T for which B(t) is equal to a non-existent object.) Therefore the derivation cannot reach the point of proving the contradiction in (4). ([t∈T] in (4) is also meaningless.)

Definition: Let U ⊆ V and R be the relation on the pair (U,V).

I define the diagonalization property derived from the relation R by the following formula

D(v) := ∀x∈U [R(x,v) ⟺ ¬ R(x,x)] , v∈V.

Theorem (Diagonalization Theorem) Let U=V. Then the diagonalization property derived from R is unsatisfiable on the set V, i.e. ∀v∈V [D(v) = false], i.e. ∀v∈V [¬ D(v)].

Proof

Let e∈V be an arbitrary fixed element, and let

Φ_e(x) := [R(x,e) ⟺ ¬ R(x,x)].

By substituting x:=e in Φ_e(x), we obtain

Φ_e(e) = [R(e,e) ⟺ ¬ R(e,e)] = false.

Thus, there exists an x∈V for which Φ_e(x)=false, therefore the statement that “Φ_e(x) is true for all x∈V” is false, i.e.
[∀x∈V Φ_e(x) ] = false, so D(e) = false.

Since we chose e∈V arbitrarily, we have proved the theorem. qed

Theorem_2 If the condition (1) holds, then there is no set T ∈ 2^M satisfying the requirement (2).

Proof

For now, let us use the fact that B is injective and denote the codomain of B with K ⊆2^M. Introducing the notation X=B(x) (where x ∈M), then (2) is equivalent to:

(5) ∀X∈K [B^-1(X)∈T ⟺ ¬ B^-1(X)∈X]; T∈ 2^M .

Let us define the relation R(X,Y) as follows:

(6) R(X,Y) := [B^-1(X) ∈ Y]; X ∈ K, Y ∈ 2^M.

Using this, (5) is equivalent to:

(7) D(T) = ∀X∈K [R(X,T) ⟺ ¬ R(X,X)]; T ∈ 2^M .

This (7) is equivalent to (2). And (7) is nothing other than the diagonalization property D(T) derived from the relation R defined in (6).

Condition (1) is equivalent to the existence of an injective mapping B: M → 2^M that is also surjective, i.e. K=2^M. Let U:=K and V:=2^M , thus this satisfies the condition U=V of the Diagonalization Theorem, so by applying it, we get that
for every x∈ 2^M

(8) D(x) = false.

Thus, when (1) holds, there is no T∈ 2^M that satisfies the requirement (2).

qed

Consequence

Cantor proof gets stuck at point (*), since the further steps of the proof refer to an object T that has already been proven not to exist. (The sign ’T’ has no refedence, here is a turth value gap.) The fact that there is no such set T, has been proven regardless of the continuation beyond point (*). Since the Cantor proof gets stuck before the contradiction is demonstrated by (4), this is an incorrect proof.

The ZFC separation axiom scheme (restricted comprehensin)

For any given ϕ property and any set M,

∃T ∀x (x ∈ T ⟺ (x ∈ M & ϕ (x))).

i.e.: if ϕ is a property, then for any set M there exists the set
T := { x ∈ M | ϕ(x) }, which contains exactly those x elements of the set M that have the property ϕ.

Application to the Cantor proof

Let ϕ(x) := [ ¬ x ∈ B(x)], then, as a particular case of the separation scheme, there must exists an element T of the power set 2^M for that

(**) ∀x∈M (x ∈ T ⟺ ¬ x ∈ B(x)).

You can see that (**) is identical to requirement (2).

So, based on the ZFC subset axiom scheme, we have found a concrete axiom that states exactly the opposite of what the Theorem_2. So, by this formal aid, the Cantor power set theorem can be proved in ZFC.

This is thought-provoking.

PS. (2025-12-07)

First of all, you must accept that the Cantor proof is definitely faulty, since references are made to a non-existent object T in the steps after the (*) point.

It is another question whether you can find an alternative proof by referring to the Subset axiom scheme. This proof is based on the fact that a secondary contradiction arises here: according to Theorem_2, the set T cannot exist, but according to the Separation Axiom Scheme, it must exist. It is a philosophical question which is stronger: a proven theorem or a goal-oriented axiom.

Parallelism with Russell's antinomy.

The above reasoning can also be carried out for the Russell antinomy in Cantor's naive set theory, where the principle of unconstrainted comprehension is (implicitly) accepted. But it is not an axiom, just a naive principle that was not sufficiently thought out by Cantor, and so needs to be modified because of the Russell antinomy. (The barber did not lie intentionally either, he just did not think enough about what he said, since such a relation that he talks about does not exist, so, maybe he is a barber, but he is not a such barber what he states.)

Consider the set b that satisfies the requirement [(x∈b) ⟺ ¬ (x∈x)], and let R be the relation R(x,y) := (x ∈ y). (y shaves x). Then
D(b)= ∀x∈V [R(x,b) ⟺ ¬R(x,x)], and by the Diagonal theorem D(b) = false.

So the Russellian diagonal set b={x | ¬ x∈x} does not exis. The current literature also claims this, with a slightly different argument.

In the case of the assumption of the bijectivity of B, (8) says the same thing about T: the diagonal set T does not exist.

What is thought-provoking?

Remember: the Diagonal theorem is a universal, proven theorem. In itself, it is not a contradiction that the set T does not exist, nor that the Russell set does not exist. There is a contradiction only because the axiom about the set T states the negation of the Theorem.

In the case of Russellian antinomy, current authors easily consider the Russell set be non-existent, which entails a modification of the naive comprehension principle. In the case of Zeremelo’s theorem, why don’t they say the same thing about restricted comprehension? Maybe just because there is another way out of the contradiction?

It is certainly true that the secondary contradiction mentioned above can be resolved in two ways: (i) B is not bijective, or (ii) the set T does not exist. (ii) is also a possibility, since there is a precedent for it, see the “standard” resolution of Russell’s antinomy mentioned above.

However, Zermelo – like Cantor – also left an axiom in his theory, namely a particular case of the subset scheme, which is equivalent to the negation of a proven theorem, and which excludes the (ii) possibility.

The particular axiom that ensures the existence of the Russell set was excluded from the unrestricted comprehension scheme. However, the particular axiom that ensures the existence of the set T was retained in Zermelo's restricted comprehension scheme.

The subset axiom scheme was accepted by posterity. The resolution of the Russell antinomy and, at the same time, the existence of the “aleph” series is based on this consensus.

Zermelo's axiom system is a goal-oriented, conceptual axiom system in which the negation of a proven theorem is stated as an axiom for the sole purpose of making Cantor's theorem provable.

© 2009: Geier János, www.geier.hu, janos@geier.hu

All righs reserved

Ennek a lapnak Ön a . látogatója 2025. december 09. óta.

Utolsó módosítás: 2025-12-09