Another Calculational Proof of Cantor’s Theorem

  • Márcia R. Cerioli UFRJ
  • Renata de Freitas UFF
  • Petrucio Viana UFF


E. Dijkstra and J. Misra [American Mathematical Monthly, 108:440–443 (2001)] presented a calculational proof of Cantor's Theorem. Their proof is based essentially on the Axiom of Choice. In this note, we present another calculational proof which does not appeal, at least directly, to the Axiom of Choice. Our proof is based only on logical steps and a heuristic guidance analogous to the one used by Dijkstra and Misra in their proof.

Palavras-chave: Calculational Proofs, Allegories, Axiom of Choice, Cantor's Theorem


Bernays, P. (1941). A system of axiomatic set theory–part II. The Journal of Symbolic Logic, 6(1):1–17.

Bohórquez, J. A. (2008). Intuitionistic logic according to Dijkstra’s calculus of equational deduction. Notre Dame Journal of Formal Logic, 49(4):361–384.

Cantor, G. (1891). Über eine elementare Frage der Mannigfaltigskeitslehre. Jahresbericht der Deutschen Mathematiker-Vereinigung, 1(1):75–78.

Diaconescu, R. (1975). Axiom of choice and complementation. Proceedings of the American Mathematical Society, 51(1):175–178.

Dijkstra, E. and Misra, J. (2001). Designing a calculational proof of Cantor’s theorem. The American Mathematical Monthly, 108(5):555–566.

Freyd, P. and Scedrov, A. (1990). Categories, Allegories. Elsevier, 1st edition.

Maguolo, D. and Valentini, S. (1996). An intuitionistic version of Cantor’s theorem. Mathematical Logic Quarterly, 42(1):446–448.

Zermelo, E. (2010). Ernst Zermelo-Collected Works/Gesammelte Werke: Volume I/Band I-Set Theory, Miscellanea/Mengenlehre, Varia. Springer, 1st edition.
Como Citar

Selecione um Formato
CERIOLI, Márcia R.; FREITAS, Renata de; VIANA, Petrucio. Another Calculational Proof of Cantor’s Theorem. In: WORKSHOP BRASILEIRO DE LÓGICA (WBL), 3. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 9-16. ISSN 2763-8731. DOI: