A negation-free proof of Cantor's theorem

DOI10.1305/NDJFL/1117755152MaRDI QIDQ2565993zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 28 September 2005

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1305/ndjfl/1117755152

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) Other classical set theory (including functions, relations, and set algebra) (03E20) Complexity of proofs (03F20)

Review text

The author gives a proof of Cantor's theorem according to which the power set \(P(X)\) of a set \(X\) exceeds the cardinality of \(X\). Assume that there is a bijective mapping \(M:X\to P(X)\). Then a sequence \(s_0,s_1, \dots\) is called a trace if \(s_0\in X\) is arbitrary, and if \(s_j\in M (s_{j-1})\) for \(j>0\). An element \(t\in X\) is said to be simple if all possible traces beginning with \(t\) terminate. Then it is shown that the set of simple elements cannot lie in the range of \(M\). So the proof constructs the leftover subset without explicitly invoking the negation operation.

Recommendations

• Constructing Cantorian counterexamples
• Cantor theorem and friends, in logical form
• Generalizations of Cantor's theorem in \(\mathsf{ZF}\)
• scientific article; zbMATH DE number 7065729
• The Cantor-Bernstein theorem: how many proofs?

Cites work

• A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points
• Paradox without Self-Reference
• Truth and reflection

Cited in

(4)

• Constructing Cantorian counterexamples
• Cantor theorem and friends, in logical form
• scientific article; zbMATH DE number 6963653 (Why is no real title available?)
• scientific article; zbMATH DE number 6277825 (Why is no real title available?)

This page was built for publication: A negation-free proof of Cantor's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2565993)