A Non-Constructive Proof of Cantor's Theorem

Basic Information

• Paper ID: 2510.14534
• Title: A Non-Constructive Proof of Cantor's Theorem
• Author: Saeed Salehi (Plaksha University)
• Classification: math.LO (Mathematical Logic)
• Publication Date: October 16, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.14534

Abstract

This paper provides a novel proof of Cantor's power set theorem (1891) and reviews several known proof methods. The theorem concerns the non-existence of surjective functions from a set to its power set.

Research Background and Motivation

Importance of the Problem

Cantor's theorem is a fundamental theorem in set theory and mathematical foundations, revealing the hierarchical structure of infinity. The theorem demonstrates the existence of infinities of different magnitudes, bringing the concept of infinity from philosophical discourse into the rigorous framework of mathematics.

Review of Existing Methods

The author reviews several known proof approaches:

1. Cantor's Original Proof: Uses the famous diagonal argument, constructing the anti-diagonal set $D_0 = \{a \in A | a \notin f(a)\}$
2. Constructive Proof: Constructs sets $D_n$ and $D_∞$ by defining a binary relation $R \subseteq A^2$
3. Non-Constructive Proof: Proves the non-existence of an injection $h : P(A) → A$, but requires the axiom of choice

Research Motivation

Although multiple proof methods exist, the author argues that the proposed new non-constructive proof method has not yet appeared in the known list of "various proofs," thus providing supplementary value.

Core Contributions

1. Proposes a novel non-constructive proof method: Proves Cantor's theorem by partitioning sets into finite subsets
2. Explicitly identifies the use of the axiom of choice: Specifies its concrete application in the partitioning and subset selection processes
3. Establishes connections with Cantor's original proof: Demonstrates how the classical diagonal argument emerges when subsets are singletons
4. Provides comprehensive theoretical analysis: Covers both finite and infinite set cases

Detailed Methodology

Problem Definition

Prove Cantor's theorem: For any set $A$, there does not exist a surjection from $A$ to its power set $P(A)$.

Proof Architecture

Finite Set Case

For finite sets, the pigeonhole principle is employed:

• If $A$ has $n$ elements, then $P(A)$ has $2^n$ elements
• Proof by induction that $2^n > n$ always holds

Infinite Set Case

This represents the core innovation of the paper:

1. Set Partition: Partition $A$ into finite subsets: $A = \bigcup_{i \in I} A_i$, where $A_i$ are non-empty and pairwise disjoint
2. Local Function Construction: For each $i \in I$, define $f_i : A_i → P(A_i)$ as $f_i(x) = f(x) ∩ A_i$
3. Local Counterexample Construction: Since each $A_i$ is finite, there exists a subset $B_i ⊆ A_i$ not in the range of $f_i$
4. Global Counterexample Construction: Let $B = \bigcup_{i \in I} B_i$
5. Contradiction Argument: Assume $B = f(α)$ for some $α ∈ A$. Then there exists a unique $κ ∈ I$ such that $α ∈ A_κ$. In this case: $B_κ = B ∩ A_κ = f(α) ∩ A_κ = f_κ(α)$ This contradicts the choice that $B_κ$ is not in the range of $f_κ$.

Technical Innovations

1. Divide-and-Conquer Strategy: Decomposes the infinite set problem into finite set problems
2. Explicit Use of the Axiom of Choice:
   • First use: Partitioning $A$ into a finite subset family $\{A_i\}_{i \in I}$
   • Second use: Selecting subset $B_i$ for each $i$
3. Unification with Classical Proof: When $A_i$ are singletons, we obtain $D_0 = \bigcup_{a \in A}[\{a\} \setminus f(a)]$, which is Cantor's anti-diagonal set

Theoretical Analysis

Constructive vs. Non-Constructive

• Constructive Proof: Explicitly describes the set not in the function's range
• Non-Constructive Proof: Proves the existence of such a set without explicitly describing its form
• The present proof is non-constructive because it relies on the axiom of choice for partitioning and selection operations

Necessity of the Axiom of Choice

The author explicitly identifies that the axiom of choice is required in the following two steps:

1. Partitioning the infinite set $A$ into a finite subset family
2. Selecting for each finite subset a subset not in the corresponding local function's range

Relationship with Known Methods

• When $A_i$ are chosen as singletons, the method reduces to Cantor's classical diagonal argument
• When larger finite subsets are chosen, a genuinely non-constructive proof is obtained

Related Work

Historical Development

1. Georg Cantor (1891): Original diagonal argument
2. W. Quine: Constructive alternative proof methods
3. N. Raja: Negation-free proofs and other variants
4. G. Boolos: Non-constructive proof via the injection version
5. A. Karimi & S. Salehi: Relationship between diagonal arguments and fixed points

Positioning of This Work

This paper provides a new non-constructive proof perspective, enriching the diversity of existing proof methods, particularly offering new insights into the application of the axiom of choice.

Conclusions and Discussion

Main Conclusions

1. Provides a novel non-constructive proof of Cantor's theorem
2. Clarifies the role and necessity of the axiom of choice in the proof
3. Establishes a bridge between constructive and non-constructive methods

Theoretical Significance

• Foundational Mathematics: Offers a new proof perspective for Cantor's theorem
• Axiom of Choice Research: Demonstrates concrete applications of the axiom of choice in set-theoretic proofs
• Proof Methodology: Illustrates how to extend results from finite cases to infinite cases

Limitations

1. Dependence on the Axiom of Choice: The non-constructive nature of the proof limits its applicability in constructive mathematics
2. Limited Novelty: While a new proof method, the core ideas are relatively straightforward
3. Practical Application: Primarily of theoretical interest with limited practical application value

In-Depth Evaluation

Strengths

1. Clarity: The proof strategy is clear with explicit logical structure
2. Completeness: Covers both finite and infinite cases
3. Pedagogical Value: Aids in understanding the role of the axiom of choice
4. Unification: Incorporates different proof methods into a unified framework

Weaknesses

1. Limited Innovation: While a new proof, the technical difficulty is not high
2. Limited Theoretical Depth: Relative to frontier research in the field, theoretical depth is limited
3. Limited Application Value: Primarily of academic interest with limited practical scenarios

Impact Assessment

• Academic Value: Adds a new option to the library of proof methods for Cantor's theorem
• Pedagogical Value: Facilitates teaching of mathematical logic and set theory
• Theoretical Contribution: Contributes to proof methodology

Applicable Scenarios

1. Mathematical Education: As an alternative proof method for Cantor's theorem
2. Logic Research: Studying philosophical implications of different proof methods
3. Set Theory Foundations: Understanding the role of the axiom of choice in foundational mathematics

References

The paper cites the following key references:

1. G. Boolos - Methods for constructing Cantor-style counterexamples
2. A. Karimi & S. Salehi - Diagonal arguments and fixed points
3. W. Quine - Mathematical logic
4. N. Raja - Negation-free proofs of Cantor's theorem and other variants

Overall Assessment: This is a concise and clear mathematical paper that provides a novel proof perspective for the classical Cantor's theorem. While technical innovation is relatively limited, it has certain value in proof methodology and the application of the axiom of choice, making it particularly suitable for teaching and research in mathematical logic and set theory.