Another Calculational Proof of Cantor’s Theorem
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.
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.